Tài liệu Một họ thuật toán sánh mẫu Wu-Manber và thực nghiệm

ĐẠI HỌC QUỐC GIA HÀ NỘI TRƯỜNG ĐẠI HỌC CÔNG NGHỆ NGUYỄN THỊ THÚY MỘT HỌ THUẬT TOÁN SÁNH MẪU WU-MANBER VÀ THỰC NGHIỆM LUẬN VĂN THẠC SĨ CÔNG NGHỆ THÔNG TIN HÀ NỘI - 2012 ii ĐẠI HỌC QUỐC GIA HÀ NỘI TRƯỜNG ĐẠI HỌC CÔNG NGHỆ NGUYỄN THỊ THÚY MỘT HỌ THUẬT TOÁN SÁNH MẪU WU-MANBER VÀ THỰC NGHIỆM Ngành : Công nghệ thông tin Chuyên ngành : Hệ thống thông tin Mã số : 60 48 05 LUẬN VĂN THẠC SĨ CÔNG NGHỆ THÔNG TIN NGƯỜI HƯỚNG DẪN KHOA HỌC: PGS.TS Hà Quang Thụy HÀ NỘI - 2012 v MỤC LỤC MỞ ĐẦU ........................................................................................................... 1 CHƯƠNG 1: BÀI TOÁN VÀ THUẬT TOÁN SÁNH MẪU ............................ 3 1.1. Giới thiệu về bài toán sánh mẫu............................................................... 3 1.2. Phát biểu bài toán .................................................................................... 4 1.3. Một số thuật toán sánh mẫu cơ bản.......................................................... 5 1.3.1. Thuật toán Brute Force ..................................................................... 5 1.3.2. Thuật toán Knuth-Morris-Pratt ......................................................... 7 1.3.3. Thuật toán automat hữu hạn.............................................................. 9 1.3.4. Thuật toán Boyer-Moore ................................................................ 10 1.3.5. Thuật toán Karp-Rabin ................................................................... 13 1.3.6. Các thuật toán khác......................................................................... 14 CHƯƠNG 2: HỌ THUẬT TOÁN WM ........................................................... 16 2.1. Thuật toán WM ..................................................................................... 16 2.1.1. Tổng quan về thuật toán.................................................................. 16 2.1.2. Thuật toán....................................................................................... 17 2.1.2.1. Phác thảo của thuật toán........................................................... 17 2.1.2.2. Giai đoạn tiền xử lý.................................................................. 18 2.1.2.3. Giai đoạn tìm kiếm mẫu........................................................... 21 2.1.3. Phân tích thuật toán ........................................................................ 22 2.2. Một thuật toán WM với bảng băm cô đọng............................................ 25 2.2.1. Phác thảo của thuật toán ................................................................. 25 2.2.2. Cải tiến của thuật toán .................................................................... 26 2.3. Thuật toán WM đồng thời cao ............................................................... 28 2.3.1. Cải tiến của thuật toán .................................................................... 28 2.3.2. Giai đoạn tiền xử lý và tìm mẫu của HCWM .................................. 29 2.3.3. Ví dụ............................................................................................... 30 2.4. Thuật toán WM sử dụng bảng tiền tố..................................................... 34 2.4.1. Cải tiến của thuật toán .................................................................... 34 2.4.2. Giai đoạn tiền xử lý và tìm mẫu trong AFWM................................ 34 2.4.3.Ví dụ................................................................................................ 35 CHƯƠNG 3: THỰC NGHIỆM........................................................................ 38 3.1. Giới thiệu về agrep ................................................................................ 38 3.2. Các thuật toán sử dụng trong agrep........................................................ 39 3.2.1. Thuật toán WM trong AGREP........................................................ 39 3.2.2. Thuật toán sánh mẫu xấp xỉ ............................................................ 39 3.3. Cách sử dụng Agrep .............................................................................. 41 3.4. Kết quả thực nghiệm.............................................................................. 45 KẾT LUẬN...................................................................................................... 50 TÀI LIỆU THAM KHẢO ................................................................................ 51 vi DANH MỤC CÁC KÝ HIỆU, CÁC CHỮ VIẾT TẮT AC Aho-Corasick AFWM Address Filtering Based WM Ba Baeza-Yates BM Boyer-Moore CW Commentz-Walter DFA Deterministic Finite Automaton HCWM High Concurrence WM Ho Boyer-Moore-Horspool Hu Hume KMP Knuth-Morris-Pratt KR Karp-Rabin QS Quick Search WM Wu-Manber MỞ ĐẦU Hiện nay, tìm kiếm thông tin là một trong các vấn đề nghiên cứu được quan tâm nhiều nhất. Trong bối cảnh bùng nổ thông tin hiện nay, cần phải có các công cụ tìm kiếm thông tin tự động để hỗ trợ người dùng. Để xây dựng được các công cụ tìm kiếm tốt, chúng ta phải dựa vào các thuật toán tìm kiếm theo một câu hỏi dưới dạng một xâu ký tự. Các thuật toán tìm kiếm xâu ký tự được sử dụng rất nhiều trong các chương trình máy tính, đặt biệt là các thuật toán tìm kiếm mẫu giải quyết bài toán tìm kiếm một đoạn văn bản (mẫu) trong các văn bản (đích) thuộc một tập các văn bản của miền tìm kiếm. Bài toán nói trên được gọi là bài toán sánh mẫu (pattern matching, còn được gọi là so mẫu). Bài toán sánh mẫu không chỉ có trong miền dữ liệu văn bản mà còn có trong các miền dữ liệu đa phương tiện khác (ảnh, video, âm thanh,…). Trên thực tế có rất nhiều ứng dụng sánh mẫu như: cơ chế sánh mẫu của hệ điều hành (chẳng hạn, lệnh grep, fgrep ... trong hệ điều hành UNIX), cơ chế kiểm tra một file nhiễm virus (sánh mẫu – xâu đặc tả virus - với nội dung file), máy tìm kiếm (search engine) trên Internet, xác định mẫu gene bệnh xuất hiện trong đoạn gene của người ... Trong thời đại bùng nổ thông tin với tốc độ lượng thông tin tăng gấp đôi sau chu kỳ 18 tháng [CL00], dù cho tốc độ và khả năng lưu trữ của máy tính tăng nhanh thì vấn đề nghiên cứu, phát triển nâng cao hiệu quả của các thuật toán sánh mẫu luôn là chủ đề nghiên cứu thời sự. Nói riêng, thuật toán sánh mẫu Wu-Manber do S. Wu và U. Manber công bố vào năm 1994 [WM94] tiếp tục có nhiều phiên bản nâng cấp gần đây [SWG06, DX08, ZCP09, ZCP09a]. Chính vì thế, luận văn này định hướng nghiên cứu một số thuật toán sánh mẫu văn bản, tập trung vào họ thuật toán Wu-Manber do họ thuật toán này tỏ ra có nhiều ưu việt trong bài toán sánh mẫu. Nội dung chủ yếu của luận văn là nghiên cứu họ thuật toán sánh mẫu văn bản Wu-Manber, phân tích chi tiết một vài thuật toán trong họ nói trên [SWG06, DX08, ZCP09, ZCP09a], khai thác công cụ để thực nghiệm thuật toán Wu-Manber (trong một số trường hợp, luận văn sử dụng cách viết tắt là WM). 2 Nội dung luận văn gồm có phần mở đầu, 3 chương, phần kết luận, tài liệu tham khảo và phụ lục. Chương 1: Bài toán và thuật toán sánh mẫu Chương này cung cấp một giới thiệu chung về bài toán sánh mẫu, cho thấy một lượng lớn thuật toán sánh mẫu đã được đề xuất. Các thuật toán sánh mẫu được chia ra hai lớp chính là lớp thuật toán chính xác và lớp thuật toán tương tự. Luận văn giới thiệu một số thuật toán sánh mẫu điển hình nhất [CL00]. Chương 2: Họ thuật toán Wu - Manber Giới thiệu thuật toán sánh mẫu văn bản chính xác WM được Sun Wu và Udi Manber công bố vào năm 1994 [WM94] với ý tưởng kết hợp cách thức nhảy của thuật toán BM do R. S. Boyer và J. S. Moore [BM77] và hàm băm. Một số phiên bản nâng cấp thuật toán WM được phân tích trong chương này [SWG06, DX08, ZCP09, ZCP09a]. Chương 3: Thực nghiệm Luận văn sử dụng công cụ phần mềm Agrep để thi hành thực nghiệm thuật toán sánh mẫu WM. Trong phần đầu của chương, luận văn trình bày một số nội dung liên quan tới công cụ này, đặc biệt cách sử dụng Agrep thi hành thuật toán WM. Luận văn đã thực nghiệm sánh mẫu cho 60 cặp file (mẫu, văn bản). Thực nghiệm cho thấy công cụ Agrep thi hành thuật toán chính xác với thời gian nhanh. 3 CHƯƠNG 1: BÀI TOÁN VÀ THUẬT TOÁN SÁNH MẪU 1.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 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). 1.2. 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 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ẹ. 1.3. 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. V. Aho và M. J. Corasick, 1975 [AC75] và thuật toán sánh mẫu của R. S. Boyer và J. S. 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. 1.3.1. 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: 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 ROADS TWO ROADS ROADS TWO ROADS ROADS TWO ROADS ROADS TWO ROADS ROADS DIVERGED IN A YELLOW WOOD DIVERGED IN A YELLOW WOOD DIVERGED IN A YELLOW WOOD DIVERGED IN A YELLOW WOOD DIVERGED IN A YELLOW WOOD 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. 1.3.2. 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 sánh, giới hạn trì hoãn là logφ(M) với φ= 1+ 5 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. Xét lần thử tại vị trí j, khi đó cửa sổ đang xét bao gồm các ký tự y[j…j+m-1] giả sử sự khác biệt đầu tiên xảy ra giữa hai ký tự x[i] và y[j+i-1]. Khi đó x[1…i]=y[j…i+j-1]=u và a=x[i]≠y[i+j]=b. Với trường hợp này, dịch cửa sổ phải thỏa mãn v là phần đầu của xâu x khớp với phần đuôi của xâu u trên văn bản. Hơn nữa ký tự c ở ngay sau v trên mẫu phải khác với ký tự a. Trong những đoạn như v thoả mãn các tính chất trên ta chỉ quan tâm đến đoạn có độ dài lớn nhất. j i+j y x x u b u a v c Dịch cửa sổ sao cho v phải khớp với u và c ≠ a 8 Thuật toán Knuth-Morris-Pratt sử dụng mảng Next[i] để lưu trữ độ dài lớn nhất của xâu v trong trường hợp xâu u=x[1…i-1]. Mảng này có thể tính trước với chi phí về thời gian là O(M) (việc tính mảng Next thực chất là một bài toán qui hoạch động một chiều). Thuật toán Knuth-Morris-Pratt có chi phí về thời gian là O(M+N) với nhiều nhất là 2N-1 lần số lần so sánh ký tự trong quá trình tìm kiếm. Ví dụ 1: Tìm kiếm một ký tự ababac. Đầu tiên ta tiến hành tính mảng next: Result: 1:i=1,j=0:i:= 2;j:= 1;next[2] := 1; 2:i=2,j=1:j:=next[1] = 0; 3:i=2,j=0:i:= 3;j:= 1;next[3] := 1; 4:i=3,j=1:i:= 4;j:= 2;next[4] := 2; 5:i=4,j=2:i:= 5;j:= 3;next[5] := 3; 6:i=5,j=3:i:= 6;j:= 4;next[6] := 4; 7:i=6,j=4:j:=next[4] = 2; 8:i=6,j=2:j:=next[2] = 1; 9:i=6,j=1:j:=next[1] = 0; 10:i=6,j=0:i:= 7;j:= 1;next[7] := 1; Và khi quá trình tìm kiếm được thực hiện: 12345678910… 1: 2: 3: 4: 5: 6: 7: ababbabaa ababac ababac ababac ababac ababac ababac j=next[5]=3 j=next[3]=1 j=next[1]=0 j=next[4]=2 j=next[2]=1 Ví dụ 2: Một ví dụ khác của thuật toán sẽ cho ta thấy nếu như trong mẫu các ký tự từng đôi một khác nhau thì Knuth-Morris-Pratt sẽ không khác gì so với BruteForce. Khi đó next[1] = 0 còn next[j] = 1với mọi j >1 9 Tuy nhiên trong nhiều ứng dụng thực tế thuật toán Knuth-Morris-Pratt nhanh hơn không đáng kể so với thuật toán Brute-Force, do ít khi xảy ra trường hợp tìm kiếm các mẫu có tính tự lặp lại cao trong các văn bản cũng có tính lặp lại cao. Mặc dù vậy nhưng phương pháp này có một giá trị thực tế quan trọng là: ta có thể tiến hành tìm kiếm tuần tự trong văn bản và không bao giờ phải dự phòng trong văn bản đó. Điều này rất có ý nghĩa khi áp dụng trên một tệp tin lớn được đọc từ một thiết bị ngoại vi nào đó thì các thuật toán yêu cầu dự phòng sẽ tiêu tốn bộ đệm hơn. 1.3.3. Thuật toán automat hữu hạn Trong thuật toán này, quá trình tìm kiếm được đưa về một quá trình biến đổi trạng thái automat. Hệ thống automat trong thuật toán DFA sẽ được xây dựng dựa trên xâu mẫu. Mỗi trạng thái (nút) của automat lúc sẽ đại diện cho số ký tự đang khớp của mẫu với văn bản. Các ký tự của văn bản sẽ làm thay đổi các trạng thái. Và khi đạt được trạng cuối cùng có nghĩa là đã tìm được một vị trí xuất hiện ở mẫu. Thuật toán này có phần giống thuật toán Knuth-Morris-Pratt trong việc nhảy về trạng thái trước khi gặp một ký tự không khớp, nhưng thuật toán DFA 10 có sự đánh giá chính xác hơn vì việc xác định vị trí nhảy về dựa trên ký tự không khớp của văn bản (trong khi thuật toán KMP lùi về chỉ dựa trên vị trí không khớp). Việc xây dựng hệ automat khá đơn giản khi được cài đặt trên ma trận kề. Khi đó thuật toán có thời gian xử lý là O(N) và thời gian để tạo ra hệ automat là O(M*N) (tùy cách cài đặt) Nhưng ta nhận thấy rằng trong DFA chỉ có nhiều nhất M cung thuận và M cung nghịch, vì vậy việc lưu trữ các cung không cần thiết phải lưu trên ma trận kề mà có thể dùng cấu trúc danh sách kề Forward Star để lưu trữ. Như vậy thời gian chuẩn bị và lượng bộ nhớ chỉ là O(M). Tuy nhiên thời gian tìm kiếm có thể tăng lên một chút so với cách lưu ma trận kề. 1.3.4. Thuật toán Boyer-Moore Thuật toán Boyer Moore là thuật toán tìm kiếm chuỗi rất có hiệu quả trong thực tiễn, các dạng khác nhau của thuật toán này thường được cài đặt trong các chương trình soạn thảo văn bản. Đặc điểm chính của thuật toán là kiểm tra các ký tự của mẫu từ phải sang trái và khi phát hiện sự khác nhau đầu tiên thuật toán sẽ tiến hành dịch cửa sổ đi, độ phức tạp về thời gian ở giai đoạn tiền xử lý là O(M+δ), ở giai đoạn tìm mẫu là O(M*N), trong trường hợp tốt nhất là O(N/M). Trong thuật toán này có hai cách dịch cửa sổ: Cách thứ 1: gần giống như cách dịch trong thuật toán KMP, dịch sao cho những phần đã so sánh trong lần trước khớp với những phần giống nó trong lần sau. Trong lần thử tại vị trí j, khi so sánh đến ký tự i trên mẫu thì phát hiện ra sự khác nhau giữa ký tự x[i]=a của mẫu và ký tự y[i+j]=b của văn bản, lúc đó x[i+1…m-1]=y[i+j+1...j+m-1]=u và y[i+j-1]=b và x[i] ≠ y[i+j] khi đó thuật toán sẽ dịch cửa sổ sao cho đoạn u=y[i+j+1…j+m-1] giống với một đoạn mới trên mẫu (trong các phép dịch ta chọn phép dịch nhỏ nhất) y x x b u a u c u shift Dịch sao cho u xuất hiện lại và c ≠ a 11 Nếu không có một đoạn nguyên vẹn của u xuất hiện lại trong x, ta sẽ chọn sao cho phần đôi dài nhất của u xuất hiện trở lại ở đầu mẫu. y x b u b u x shift u Dịch để một phần đôi của u xuất hiện lại trên x Cách thứ 2: Coi ký tự đầu tiên không khớp trên văn bản là b=y[i+j] ta sẽ dịch sao cho có một ký tự giống b trên xâu mẫu khớp vào vị trí đó (nếu có nhiều vị trí xuất hiện b trên xâu mẫu ta chọn vị trí phải nhất). y x x b u a u b shift không chứa b Dịch để ký tự b ăn khớp với văn bản. Nếu không có ký tự b nào xuất hiện trên mẫu ta sẽ dịch cửa sổ sao cho ký tự trái nhất của cửa sổ vào vị trí ngay sau ký tự y[i+j-1]=b để đảm bảo sự ăn khớp y x b u a u x shift không chứa b Dịch khi b không xuất hiện trong x Trong hai cách dịch chuyển, thuật toán sẽ chọn cách dịch có lợi nhất. 12 Trong cài đặt ta dùng mảng bmGs để lưu cách dịch 1, mảng bmBc để lưu phép dịch thứ 2 (ký tự không khớp). Việc tính toán mảng bmBc thực sự không có gì nhiều để bàn. min{i : 1 ≤ i ≤ m −1, x[m −1 − i] = c} nếu c xuất hiện trong x bmBc[c]=  ngược lại m Nhưng việc tính trước mảng bmGs khá phức tạp, ta không tính trực tiếp mảng này mà tính gián tiếp thông qua mảng suff. suff[i]=max{k | x[i-k+1…i]=x[m-k…m-1]} Các mảng bmGs và bmBc có thể được tính toán trước trong thời gian tỉ lệ với O(M+δ). Thời gian tìm kiếm (độ phức tạp tính toán) của thuật toán BoyerMoore là O(M*N). Tuy nhiên với những bản chữ cái lớn thuật toán thực hiện rất nhanh. Trong trường hợp tốt chi phí thuật toán có thể xuống đến O(N/M) là chi phí thấp nhất của các thuật toán tìm kiếm hiện đại có thể đạt được. Thuật toán Boyer-Moore có thể đạt tới chi phí O(N/M) là nhờ có cách dịch thứ 2 “ký tự không khớp”. Cách chuyển cửa sổ khi gặp “ký tự không khớp” cài đặt vừa đơn giản lại rất hiệu quả trong các bảng chữ cái lớn nên có nhiều thuật toán khác cũng đã lợi dụng các quét mẫu từ phải sang trái để sử dụng cách dịch này. Tuy nhiên chi phí thuật toán của Boyer-Moore là O(M*N) vì cách dịch thứ nhất của thuật toán này không phân tích triệt để các thông tin của những lần thử trước, những đoạn đã so sánh rồi vẫn có thể bị so sánh lại. Có một vài thuật toán đã cải tiến cách dịch này để đưa đến chi phí tính toán của thuật toán BoyerMoore là tuyến tính. Ví dụ: Tìm kiếm chuỗi STING trong văn bản. Ta tiến hành so sánh từ phải sang trái, đầu tiên so sánh ký tự G trong mẫu với ký tự thứ 5 trong văn bản là R. Ta nhận thấy sự không khớp ở đây và có thêm được một nhận xét quan trọng là R không xuất hiện ở bất cứ chỗ nào trong mẫu, như vậy ta thể dịch mẫu qua R(dịch đi 6 vị trí). Ta so sánh tiếp G với S (ký tự thứ 10 trong mẫu), 13 lại xảy ra sự không khớp, nhưng S lại có xuất hiện trong mẫu vì vậy ta dịch mẫu đi 5 vị trí tức là cho đến khi ký tự S trong văn bản khớp với ký tự S trong mẫu. Quá trình trên tiếp diễn tương tự cho đến khi so sánh G với ký tự T trong CONSISTING. Có sự không trùng khớp, nhưng T lại có xuất hiện trong mẫu nên ta dịch mẫu đi 4 vị trí cho đến khi nó trùng với ký tự T trong mẫu. Và ở vị trí mới ta tìm được một sự trùng khớp hoàn toàn của mẫu trong văn bản. Với phương pháp này đưa ta đến kết quả chỉ sau 7 bước so sánh (và thêm 5 lần so sánh các ký tự trong STING với văn bản nữa để chỉ ra sự trùng khớp hoàn toàn). 1.3.5. Thuật toán Karp-Rabin Thuật toán Karp-Rabin là thuật toán sử dụng hàm băm, độ phức tạp về thời gian trong giai đoạn tiền xử lý là O(M), giai đoạn tìm mẫu là O(M*N). Đây là bài toán tìm kiếm mẫu không khác nhiều so với bài toán tìm kiếm chuẩn. Tại đây một hàm băm được dùng để tránh đi sự so sánh không cần thiết. Thay vì phải so sánh tất cả các vị trí của văn bản, ta chỉ cần so sánh những cửa sổ bao gồm những ký tự “có vẻ giống” mẫu. Trong thuật toán này hàm băm phải thỏa mãn một số tính chất như phải dễ dàng tính được trên mẫu, và đặc biệt công việc tính lại phải đơn giản để ít ảnh hưởng đến thời gian thực hiện của thuật toán. Và hàm băm được chọn ở đây là: hash(w[0…m-1]) = h = (w[0]*2m-1 + w[1]*2m-2 +… w[m-1]*20) mod q Việc tính lại hàm băm sau khi dịch cửa sổ đi một ký tự chỉ đơn giản như sau: Rehash(a,b,h)=h = ((h – a*2m-1)*2 + b)mod q Việc tiền xử lý trong thuật toán Karp-Rabin có độ phức tạp O(M). Tuy vậy thời gian tìm kiếm lại tỉ lệ với O(M*N) vì có thể có nhiều trường hợp hàm băm của chúng ta bị lừa và không phát huy tác dụng. Nhưng đó chỉ là những trường hợp đặc biệt, thời gian tính toán của thuật toán KR trong thực tế thường tỉ lệ với O(N+M). Hơn nữa thuật toán KR có thể dễ dàng mở rộng cho các mẫu, văn bản dạng 2 chiều, do đó khiến cho nó trở nên hữu ích hơn so với các thuật toán còn lại trong việc xử lý ảnh. 14 Ví dụ: Quá trình tìm kiếm diễn ra bằng cách so sánh giá trị băm của mỗi một dãy M kýtự trong văn bản với giá trị băm của mẫu, nếu không bằng nhau mẫu sẽ dịch sang phải một vị trí so với văn bản và tiếp tục so sánh. Kết quả là tìm thấy mẫu trong văn bản khi có hai giá trị băm là bằng nhau. 1.3.6. Các thuật toán khác Một số thuật toán nêu trên chưa phải là tất cả các thuật toán tìm kiếm chuỗi hiện có. Nhưng chúng đã đại diện cho đa số các tư tưởng dùng để giải bài toán tìm kiếm chuỗi. Các thuật toán sánh mẫu lần lượt từ trái sang phải thường là các dạng cải tiến (và cải lùi) của thuật toán Knuth-Morris-Pratt và thuật toán sử dụng Automat như: Forward Dawg Matching, Apostolico-Crochemore, Not So Naïve… Các thuật toán sánh mẫu từ phải sang trái đều là các dạng của thuật toán Boyer-Moore. Phải nói lại rằng thuật toán BM là thuật toán tìm kiếm rất hiệu quả trên thực tế nhưng độ phức tạp tính toán lý thuyết lại là O(M*N). Chính vì vậy những cải tiến của thuật toán này cho độ phức tạp tính toán lý thuyết tốt như: thuật toán Apostolico-Giancarlo đánh dấu lại những ký tự đã so sánh rồi để khỏi bị so sánh lặp lại, thuật toán Turbo-BM đánh giá chặt chẽ 15 hơn các thông tin trước để có thể dịch được xa hơn và ít bị lặp, … Còn có một số cải tiến khác của thuật toán BM không làm giảm độ phức tạp lý thuyết mà dựa trên kinh nghiệm để có tốc độ tìm kiếm nhanh hơn trong thực tế. Ngoài ra, một số thuật toán kết hợp quá trình tìm kiếm của BM vào hệ thống Automat mong đạt kết quả tốt hơn. Các thuật toán sánh mẫu theo thứ tự đặc biệt * Thuật toán Galil-Seiferas và Crochemore-Perrin chia mẫu thành hai đoạn, đầu tiên kiểm tra đoạn ở bên phải rồi mới kiểm tra đoạn bên trái với chiều từ trái sang phải. * Thuật toán Colussi và Galil-Giancarlo lại chia mẫu thành hai tập và tiến hành tìm kiếm trên mỗi tập với một chiều khác nhau. * Thuật toán Optimal Mismatch và Maximal Shift sắp xếp thứ tự mẫu dựa vào mật độ của ký tự và khoảng dịch được. * Thuật toán Skip Search, KMP Skip Search và Alpha Skip Search dựa vào sự phân bố các ký tự để quyết định vị trí bắt đầu của mẫu trên văn bản. Các thuật toán sánh mẫu theo thứ tự bất kỳ Đó là các thuật toán có thể tiến hành sánh mẫu với cửa sổ theo một thứ tự ngẫu nhiên. Những thuật toán này đều có cài đặt rất đơn giản và thường sử dụng chiêu ký tự không khớp của thuật toán Boyer-Moore. Có lẽ loại thuật toán này dựa trên ý tưởng càng so sánh loạn càng khó kiếm test chết. Vì dựa hoàn toàn trên vị trí được lấy ngẫu nhiên nên kết quả chỉ là mong đợi ngẫu nhiên chứ không có một cơ sở toán học nào để lấy vị trí ngẫu nhiên sao cho khả năng xuất hiện mẫu cần tìm là lớn. Họ thuật toán sánh mẫu văn bản Wu-Manbers (ký hiệu là WMs) được Sun Wu và Udi Manber công bố vào năm 1994 [WM94]. Các tác giả sử dụng ý tưởng nhảy của thuật toán BM do R. S. Boyer và J. S. Moore [BM77] và hàm băm. Trong thuật toán này, các thuật toán BM mở rộng cho đa mẫu. Trong WM, khối ký tự, bao gồm hai hoặc ba ký tự, được sử dụng như một đơn vị để xác định khả năng so sánh và khoảng cách dịch chuyển. Thuật toán sử dụng bảng băm để giải quyết va chạm. Với tính năng hiệu quả đó, WM được tích hợp trong lệnh "agrep" trong Linux. 16 CHƯƠNG 2: HỌ THUẬT TOÁN WM 2.1. Thuật toán WM 2.1.1. Tổng quan về thuật toán Các thuật toán sánh mẫu cổ điển bao gồm thuật toán Aho-Corasick (AC), thuật toán AC-BM và thuật toán Wu-Manber (WM) [CL00], trong đó, thuật toán WM có hiệu quả cao được sử dụng rộng rãi trong việc tìm kiếm. Aho và Corasick [AC75] trình bày một thuật toán tuyến tính thời gian cho bài toán sánh mẫu, dựa trên phương pháp tiếp cận thiết bị tự động. Thuật toán này là một cơ sở cho các công cụ UNIX fgrep. Thuật toán tuyến tính thời gian là tối ưu trong trường hợp xấu nhất (thuật toán BM) nhưng bị coi như một thuật toán tìm kiếm chuỗi thông thường được chứng minh bởi Boyer và Moore [BM77], nó bỏ qua một bộ phận lớn trong văn bản khi tìm kiếm, cho kết quả nhanh hơn so với thuật toán tuyến tính trong trường hợp trung bình. Commentz và Walter [CW79] trình bày thuật toán Commentz-Walter cho các vấn đề sánh mẫu kết hợp với kỹ thuật Boyer-Moore và các thuật toán Aho-Corasick. Trong thực tế, các thuật toán Commentz-Walter nhanh hơn đáng kể so với thuật toán AC. Hume [Hu91] thiết kế một công cụ gọi là gre dựa trên thuật toán này, và phiên bản 2.0 của fgrep đang được sử dụng trong dự án GNU [Ha93]. Baeza-Yates [Ba89] cũng đã đưa ra một thuật toán được kết hợp từ các thuật toán Boyer-Moore-Horspool [Ho80] (một biến thể của thuật toán Boyer-Moore cổ điển) với thuật toán Aho-Corasick. Như giới thiệu ở trên, thuật toán WM được Sun Wu và Udi Manber đề xuất vào năm 1994, sử dụng ý tưởng BM và băm. Thuật toán WM là một trong các thuật toán sánh mẫu thuộc loại nhanh nhất. Thuật toán WM dựa trên một ý tưởng tốt trong sánh mẫu, nhưng trong ứng dụng thực tế, nhiều vấn đề có thể được cải tiến hơn nữa. Hiện nay, có rất nhiều phiên bản thuật toán WM cải tiến. Thuật toán WM sửa đổi (MWM: Modified WM) được sử dụng trong Snort, sử dụng bảng SHIFT và bảng băm tiền tố. Thêm các chức năng của bộ lọc tiền tố để thuật toán WM có được hiệu quả tốt. Để sánh mẫu nhanh hơn, một bảng tiền tố được thêm vào. Ý tưởng của thuật toán QS (một thuật toán WM cải tiến) là tăng cường khoảng cách dịch chuyển. Bảng HASH được sửa đổi, và danh sách liên kết các mẫu hậu tố được thêm vào để tránh sự mất mát, vì vậy khi một mẫu trong danh sách liên kết xuất hiện, các mẫu sau đó không cần phải xuất hiện nữa. Người ta phân chia tất cả các mẫu thành hai nhóm, nhóm mẫu ngắn và nhóm mẫu dài, và sau đó đối sánh