CHƯƠNG 1: BÀI TOÁN VÀ THUẬT TOÁN SÁNH MẪU 1. Giới thiệu về bài toán sánh mẫu Kiểu dữ liệu văn bản (Text) là dạng trình bày thông tin gần gũi nhất với con người, vì vậy, đây cũng là dạng trình bày thông tin số rất phổ biến. Chính vì lẽ đó, bài toán tìm kiếm văn bản (text searching) là một trong những bài toán quan trọng nhất trong hoạt động tìm kiếm thông tin của con người. Trong thời đại ngày nay, văn bản số hóa đang tăng trưởng "bùng nổ" trong các cơ sở dữ liệu trên Internet, dung lượng tăng gấp đôi sau mỗi chu kỳ 18 tháng [CL00].
Trong bối cảnh đó, vấn đề tìm kiếm văn bản một cách tự động đã rất quan trọng thì lại ngày càng quan trọng hơn. Dạng phổ biến nhất của bài toán tìm kiếm văn bản là: Cho trước nguồn tìm kiếm là một tập D các văn bản (hoặc là cơ sở dữ liệu văn bản, hoặc là tập các văn bản trên Internet). Cho một câu hỏi dạng văn bản q (thường là một từ, một xâu văn bản ngắn), hãy tìm tất cả các văn bản thuộc D mà có chứa q. Trong nhiều trường hợp (chẳng hạn, tìm kiếm thông qua máy tìm kiếm) thì q còn được gọi là "truy vấn" và bài toán còn có tên gọi là "tìm kiếm theo truy vấn".
Để tìm được các văn bản có chứa văn bản truy vấn q, hệ thống tìm kiếm cần phải kiểm tra văn bản truy vấn q có là một xâu con của các văn bản thuộc tập D hay không (sánh mẫu) và đưa ra các văn bản đáp ứng. Trong nhiều trường hợp, bài toán còn đòi hỏi tìm tất cả các vị trí của các xâu con trong văn bản trùng với q. Đồng thời, điều kiện tìm kiếm có thể được làm "xấp xỉ" theo nghĩa văn bản kết quả có thể không cần chứa q (không cần có một xâu con của văn bản trùng một cách hoàn toàn chính xác với q) mà chỉ cần "liên quan" tới q (có xâu con trong văn bản "xấp xỉ" q). Có thể thấy, các máy tìm kiếm sử dụng cả cơ chế tìm kiếm xấp xỉ khi mà văn bản kết quả tìm kiếm không chứa hoàn toàn chính xác văn bản truy vấn.
Thời gian gần đây, bài toán sánh mẫu càng trở nên quan trọng và được quan tâm nhiều do sự tăng trưởng nhanh chóng của các hệ thống tìm kiếm thông tin và các hệ thống sinh- tin học. Một lý do nữa, con người ngày nay không chỉ đối mặt với một lượng thông tin khổng lồ mà còn đòi hỏi những yêu cầu tìm kiếm ngày càng phức tạp. Các mẫu đưa vào không chỉ đơn thuần là một xâu ký tự mà còn có thể chứa các ký tự thay thế, các khoảng trống và các biểu thức chính quy. Sự “tìm thấy” không đơn giản là xuất hiện chính xác mẫu trong văn TIEU LUAN MOI download : skknchat@gmail.com 4 bản mà còn cho phép “một xấp xỉ” giữa mẫu và xuất hiện của nó trong văn bản.
Từ đó, bên cạnh vấn đề kinh điển là “tìm kiếm chính xác”, nảy sinh một hướng nghiên cứu là "sánh mẫu xấp xỉ / tìm kiếm xấp xỉ” (approximate matching / approximate searching). Phát biểu bài toán Như đã giới thiệu, đối sánh mẫu là một bài toán cơ bản trong xử lý văn bản; bài toán yêu cầu tìm ra một hoặc nhiều vị trí xuất hiện của mẫu P trên một văn bản S. Mẫu P và văn bản S là các chuỗi có độ dài M và N (M ≤ N); P và S là các xâu ký trên cùng một bảng chữ cái Σ có δ ký tự. Bài toán sánh mẫu (chính xác) tổng quát được phát biểu như sau [CL00]: "Cho mẫu P độ dài M và văn bản S độ dài N trên cùng bảng chữ A.
Tìm một (hoặc tất cả) các lần xuất hiện của mẫu P trong S". Sánh mẫu để tìm tất cả các lần xuất hiện của các chuỗi mẫu có thể được thi hành bằng một lần quét duy nhất, diễn ra với nhiều lần thử trên các đoạn khác nhau của văn bản. Mỗi lần thử chương trình sẽ kiểm tra sự giống nhau giữa mẫu với cửa sổ hiện thời. Theo Christian Charras và Thierry Lecroq [CL00], độ phức tạp của thuật toán tìm tất cả các lần xuất hiện của x trong y trong thời gian O (M×N).
Trong bài toán tìm kiếm văn bản trên tập văn bản D, bài toán sánh mẫu được thực hiện đối với mọi cặp gồm mẫu (truy vấn) q và mọi văn bản d ∈ D. Trong trường hợp độ dài N của d rất lớn và số lượng văn bản trong D rất nhiều (|D|>>1) thì thời gian tìm kiếm văn bản phù hợp với câu hỏi q sẽ là rất tốn kém. Chính vì lý do đó, nghiên cứu đề xuất các thuật toán sánh mẫu mới, cải tiến các thuật toán sánh mẫu sẵn có luôn là một chủ đề nghiên cứu được hết sức quan tâm. Thực tiễn cũng tồn tại nhiều tình huống tìm kiếm xấp xỉ trong đó cho phép có sự "sai khác không đáng kể" giữa mẫu P và xâu con S' của xâu S.
Cũng chính vì lý do đó, bài toán sánh mẫu xấp xỉ được đặt ra, trong đó, tìm một (hay tất cả) các xâu con S' của xâu S mà S' "sai khác không đáng kể" với mẫu P [WM92]. Tồn tại một số tiêu chí cho độ đo "sai khác không đáng kể", chẳng hạn như số lượng ký tự cùng vị trí trong hai xâu S' và P là khác nhau chiếm tỷ lệ rất nhỏ so với độ dài M của xâu P. Thông thường, các thuật toán sánh mẫu làm việc với mẫu có độ dài ngắn (M≤30), tuy nhiên trong thực tiễn, bài toán sánh mẫu có độ dài mẫu lên tới con TIEU LUAN MOI download : skknchat@gmail.com 5 số hàng chục ngàn. Người ta gọi các bài toán sánh mẫu với mẫu dài như vậy là bài toán sánh mẫu "nặng" để phân biệt với bài toán sánh mẫu "nhẹ" mà độ dài mẫu không quá 30.
Thực tiễn cũng chỉ ra rằng hầu hết các ứng dụng của sánh mẫu là sánh mẫu nhẹ. Luận văn này đề cập tới bài toán sánh mẫu chính xác và tập trung vào sánh mẫu nhẹ. Một số thuật toán sánh mẫu cơ bản Theo Christian Charras và Thierry Lecroq [CL00], bốn cách tiếp cận chủ yếu của các thuật toán sánh mẫu được phân loại theo thứ tự đối sánh các ký tự của mẫu với văn bản: (1) tuần tự từ trái sang phải; (2) tuần tự từ phải sang trái; (3) xác định giới hạn lý thuyết để đưa ra thứ tự đối sánh ký tự; (4) xác định thứ tự theo quá trình thực hiện. Các tác giả cũng cho nhận định rằng nhóm thuật toán sánh mẫu tiến hành theo thứ tự tuần tự từ phải sang trái thường cho hiệu quả sánh mẫu tốt nhất trong thực tế.
Trong thập niên 1970, thuật toán sánh mẫu của A. Corasick, 1975 [AC75] và thuật toán sánh mẫu của R. Moore, 1977 [AC77] là hai trong số thuật toán điển hình nhất mà nhiều phiên bản thuật toán sánh mẫu được phát triển dựa trên ý tưởng của các thuật toán này. Đặc biệt, thuật toán Boyer-Moore vẫn còn thường xuyên áp dụng hiện nay.
Dưới đây là một số giới thiệu về một số thuật toán sánh mẫu cơ bản nhất. Trong [CL00], Christian Charras và Thierry Lecroq giới thiệu khá cụ thể về các thuật toán này. Thuật toán Brute Force Đặc điểm chính thuật toán Brute Force là: không có giai đoạn tiền xử lý, liên tục thêm không gian cần thiết, dịch chuyển cửa sổ sánh mẫu sang bên phải 1 vị trí, so sánh được thực hiện theo thứ tự bất kỳ, giai đoạn tìm kiếm có độ phức tạp thời gian là O(M*N), số ký tự dự kiến cần so sánh là 2N. Thuật toán Brute Force kiểm tra tất cả các vị trí trên văn bản từ 0 cho đến N-M.
Sau mỗi lần thử thuật toán Brute Force dịch mẫu sang phải một ký tự cho đến khi kiểm tra hết văn bản. Thuật toán Brute Force không cần giai đoạn tiền xử lý cũng như các mảng phụ cho quá trình tìm kiếm. Độ phức tạp tính toán của thuật toán này là O(N*M). Cụ thể quá trình sánh mẫu diễn ra như sau: TIEU LUAN MOI download : skknchat@gmail.com 6 Lần kiểm tra thứ nhất y G C A T C G C A G A G T A T A C A G T A C G 1 2 3 4 x G C A G A G A G Dịch 1 Lần kiểm tra thứ hai y G C A T C G C A G A G T A T A C A G T A C G 1 x G C A G A G A G Dịch 1 Lần kiểm tra thứ ba y G C A T C G C A G A G T A T A C A G T A C G 1 x G C A G A G A G Dịch 1 Thuật toán Brute Force sẽ thực hiện 30 so sánh như vậy cho đến hết văn bản Ví dụ: TWO ROADS DIVERGED IN A YELLOW WOOD ROADS TWO ROADS DIVERGED IN A YELLOW WOOD ROADS TWO ROADS DIVERGED IN A YELLOW WOOD ROADS TWO ROADS DIVERGED IN A YELLOW WOOD ROADS TWO ROADS DIVERGED IN A YELLOW WOOD ROADS TIEU LUAN MOI download : skknchat@gmail.com 7 Việc tìm kiếm bằng Brute-Force có thể là rất chậm đối với một số mẫu nào đó, ví dụ nếu xâu cần xét là một xâu nhị phân chỉ gồm hai ký tự thường xuất hiện trong các ứng dụng xử lý ảnh và lập trình hệ thống.
Thuật toán Knuth-Morris-Pratt Thuật toán Knuth-Morris-Pratt [CL00] có những đặc điểm chính sau: thuật toán thực hiện so sánh từ trái qua phải, độ phức tạp về thời gian trong giai đoạn tiền xử lý là O(M), độ phức tạp thời gian trong giai đoạn tìm mẫu là O(M+N), trong quá trình sánh mẫu thuật toán thực hiện nhiều nhất 2N-1 lần so 1+ 5 sánh, giới hạn trì hoãn là logφ(M) với φ= 2 Thuật toán Knuth-Morris-Pratt là thuật toán có độ phức tạp tuyến tính đầu tiên được phát hiện ra, dựa trên thuật toán Brute Force với ý tưởng lợi dụng lại những thông tin của lần thử trước cho lần sau. Trong thuật toán brute force vì chỉ dịch cửa sổ đi một ký tự lên có đến M-1 ký tự của cửa sổ mới là những ký tự của cửa sổ vừa xét. Trong đó có thể có rất nhiều ký tự đã được so sánh giống với mẫu và bây giờ lại nằm trên cửa sổ mới nhưng được dịch đi về vị trí so sánh với mẫu. Việc xử lý những ký tự này có thể được tính toán trước rồi lưu lại kết quả.
Nhờ đó lần thử sau có thể dịch đi được nhiều hơn một ký tự, và giảm số ký tự phải so sánh lại.