Tài liệu Một họ thuật toán đối sánh mẫu chính xác nhanh SSABS - TVSBS - FQS và thực nghiệm (Luận văn thạc sĩ)

ĐẠI HỌC THÁI NGUYÊN TRƯỜNG ĐẠI HỌC CÔNG NGHỆ THÔNG TIN&TRUYỀN THÔNG Nguyễn Thị Phương Thảo MỘT HỌ THUẬT TOÁN ĐỐI SÁNH MẪU CHÍNH XÁC NHANH SSABS - TVSBS - FQS VÀ THỰC NGHIỆM Chuyên ngành: Khoa học máy tính Mã số: 60. 48. 01. 01 LUẬN VĂN THẠC SĨ KHOA HỌC MÁY TÍNH NGƯỜI HƯỚNG DẪN KHOA HỌC: PGS.TS Hà Quang Thụy Thái Nguyên - 2015 i LỜI CAM ĐOAN Tôi xin cam đoan: Những nội dung trong luận văn này là do tôi thực hiện dưới sự hướng dẫn trực tiếp của thầy giáo hướng dẫn PGS TS. Hà Quang Thụy. Mọi tham khảo trong luận văn đều được trích dẫn rõ ràng tác giả, tên công trình, thời gian, địa điểm công bố. Tôi xin cam đoan luận văn không phải là sản phẩm sao chép của bất kỳ tài liệu khoa học nào. Học viên Nguyễn Thị Phương Thảo ii LỜI CẢM ƠN Đầu tiên tôi xin gửi lời cảm ơn sâu sắc nhất tới PGS. TS Hà Quang Thụy người hướng dẫn khoa học, đã tận tình chỉ bảo, giúp đỡ tôi thực hiện luận văn. Tôi cũng xin lời lời cám ơn trân thành tới PGS. TS. Nguyễn Trí Thành và các anh chị em Phòng Thí nghiệm Khoa học dữ liệu và Công nghệ Tri thức, Trường Đại học Công nghệ, Đại học Quốc gia Hà Nội đã giúp đỡ và tạo điều kiện hỗ trợ tôi. Tôi xin cảm ơn các thầy cô trường Đại học Công nghệ thông tin và Truyền thông - Đại học Thái Nguyên đã giảng dạy và truyền đạt kiến thức cho tôi. Tôi xin trân thành cảm ơn Ban giám hiệu trường Cao đẳng nghề Phú Thọ và các đồng nghiệp trong khoa Công nghệ thông tin đã tạo mọi điều kiện giúp đỡ tôi hoàn thành nhiệm vụ học tập. Cuối cùng, tôi xin cảm ơn những người thân và các bạn bè chia sẻ, giúp đỡ tôi hoàn thành luận văn này. Mặc dù đã hết sức cố gắng hoàn thành luận văn với tất cả sự nỗ lực của bản thân, nhưng luận văn vẫn còn những thiếu sót. Kính mong nhận được những ý kiến đóng góp của quý Thầy, Cô và bạn bè đồng nghiệp. Tôi xin chân thành cảm ơn! Việt Trì, ngày 10 tháng 09 năm 2015 Nguyễn Thị Phương Thảo iii MỤC LỤC LỜI CAM ĐOAN............................................................................................................. i LỜI CẢM ƠN ................................................................................................................. ii MỤC LỤC ..................................................................................................................... iii DANH MỤC CÁC KÝ HIỆU, CÁC CHỮ VIẾT TẮT .................................................... v DANH MỤC CÁC BẢNG ............................................................................................. vi DANH MỤC CÁC HÌNH VẼ ....................................................................................... vii MỞ ĐẦU ........................................................................................................................ 1 CHƯƠNG 1. GIỚI THIỆU CHUNG VỀ THUẬT TOÁN SÁNH MẪU.......................... 3 1.1. Bài toán sánh mẫu và phân loại ............................................................................ 3 1.1.1. Bài toán sánh mẫu .......................................................................................... 3 1.1.2. Phân loại bài toán sánh mẫu ........................................................................... 3 1.2. Một số ứng dụng của bài toán sánh mẫu ............................................................... 5 1.3. Một số thuật toán sánh mẫu truyền thống ............................................................. 5 1.3.1. Thuật toán Boyer–Moore ............................................................................... 6 1.3.2. Thuật toán Quick Search ................................................................................ 9 1.4. Khái quát về các thuật toán sánh mẫu chính xác ................................................. 10 1.5. Kết luận chương 1 .............................................................................................. 11 CHƯƠNG 2: HỌ THUẬT TOÁN SÁNH MẪU CHÍNH XÁC NHANH SSABS TVSBS – FQS ............................................................................................................... 13 2.1. Giới thiệu về các biến thể của thuật toán Quick Search....................................... 13 2.2. Thuật toán đối sánh mẫu nhanh SSABS ............................................................. 13 2.2.1. Giới thiệu ..................................................................................................... 13 2.2.2. Thuật toán .................................................................................................... 14 2.3. Thuật toán TVSBS ............................................................................................. 19 2.3.1. Giới thiệu ..................................................................................................... 19 2.3.2. Thuật toán .................................................................................................... 19 2.3.3. Ví dụ ............................................................................................................ 21 2.4. Thuật toán Faster Quick Search .......................................................................... 24 2.4.1. Giới thiệu ..................................................................................................... 24 2.4.2. Thuật toán .................................................................................................... 24 2.4.3. Ví dụ ............................................................................................................ 29 2.5. Kết luận chương 2 .............................................................................................. 32 iv CHƯƠNG 3: CHƯƠNG TRÌNH THỰC NGHIỆM HỌ THUẬT TOÁN ĐỐI SÁNH MẪU CHÍNH XÁC NHANH VỚI BỘ CÔNG CỤ SMART ............................. 33 3.1. Giới thiệu ........................................................................................................... 33 3.2. Bộ công cụ Smart ............................................................................................... 33 3.2.1. Các thành phần chính trong bộ công cụ SMART.......................................... 33 3.2.2. Sử dụng bộ công cụ Smart ........................................................................... 43 3.3. Bộ trung gian PUTTY ........................................................................................ 44 3.4. Kết quả thực nghiệm và nhận xét........................................................................ 45 3.4.1. Thực nghiệm đánh giá hiệu năng hai thuật toán SSABS và TVSBS ............. 45 3.4.2. Thực nghiệm về kết quả sánh mẫu của hai thuật toán SSABS và TVSBS..... 49 3.5. Kết luận chương 3 .............................................................................................. 51 KẾT LUẬN VÀ HƯỚNG NGHIÊN CỨU TIẾP THEO ............................................... 53 TÀI LIỆU THAM KHẢO ............................................................................................. 54 PHỤ LỤC v DANH MỤC CÁC KÝ HIỆU, CÁC CHỮ VIẾT TẮT MP70 Morris-Pratt BM Boyer-Moore CLRS01 CLRS01 BDM CR94 ACR99 Bakward-Oracle BDM BNDM QS Quick Search KMP Knuth-Morris-Pratt brBc Berry-Ravindran vi DANH MỤC CÁC BẢNG Bảng 2.1. Các giá trị dịch chuyển cho = 4 được đưa ra bởi hàm brBc ............ 22 Bảng 2.2. Các hàng ES, next và shift cho một mẫu ví dụ................................... 30 Bảng 3.1. Danh sách tất cả các thuật toán sánh xâu từ năm 1970 trên SMART . 34 Bảng 3.2. Bộ các kho ngữ liệu thử nghiệm ........................................................ 38 Bảng 3.3. Bảng kết quả thử nghiệm 1 ................................................................ 46 vii DANH MỤC CÁC HÌNH VẼ Hình 3.1. Đăng nhập bằng bộ trung gian PUTTY .............................................. 45 Hình 3.2. Kết quả thực nghiệm 1 ....................................................................... 46 Hình 3.3. Kết quả thực nghiệm 2 tìm mẫu trong chuỗi ...................................... 50 Hình 3.4. Kết quả thực nghiệm 2 tìm mẫu trong file ......................................... 51 1 MỞ ĐẦU Đối sánh xâu chính xác (exac string matching, sau đây gọi tắt là “sánh xâu chính xác”), còn được gọi là sánh mẫu chính xác (exac pattern matching) là bài toán tìm ra tất cả sự xuất hiện của một xâu p cho trước trong một văn bản t, trong đó p, t đều là các xâu văn bản theo một bảng chữ cái; p được gọi là “mẫu” (pattern) còn t là được gọi là “văn bản đích” (target text) [3, 8]. Một ví dụ gần gũi là cho một truy vấn p và một trang web t, kiểm tra xem p có xuất hiện trong nội dung của t hay không. Theo Simone Faro và Thierry Lecroq [8], trong 40 năm gần đây, đối sánh xâu là một trong những bài toán được nghiên cứu rộng rãi nhất trong khoa học máy tính, chủ yếu vì các ứng dụng trực tiếp của nó cho rất nhiều lĩnh vực khác nhau như xử lý văn bản - hình ảnh - tín hiệu (text, image and signal processing), phân tích và nhận dạng giọng nói (speech analysis and recognition), truy hồi thông tin (information retrieval), nén dữ liệu (data compression), sinh học và hóa học tính toán (computational biology and chemistry). Bài toán sánh xâu chính xác trực tuyến (onlineexac string matching) nhận được sự quan tâm rất lớn của cộng đồng nghiên cứu. Trong thập kỷ 2001-2010, hơn 50 thuật toán mới được đưa ra, mở rộng thêm số lượng khoảng 40 thuật toán đã có từ trước năm 2000 [2]. Hệ thống các thuật toán này đã được phân tích, đánh giá công phu [5, 6, 7]. Theo Simone Faro và Thierry Lecroq, nhóm các thuật toán sánh mẫu nhanh có nguồn gốc từ thuật toán QS [9] đã chứng tỏ được lợi thế, đặc biệt khi mẫu đối sánh có độ dài ngắn. Chính vì lý do đó, luận văn này định hướng nghiên cứu một số thuật toán sánh mẫu chính xác nhanh có nguồn gốc từ thuật toán QS, tập trung vào họ thuật toán SSABS [8] – TVSBS [4] - FQS [3] do các thuật toán này đã tỏ ra ưu việt trong bài toán sánh mẫu ngắn. Họ thuật toán này là ở nhánh thuật toán khác với các thuật toán trong [1], hơn nữa, thuật toán FQS là mới được công bố vào năm 2014. Nội dung chủ yếu của luận văn là nghiên cứu, phân tích chi tiết các thuật toán sánh mẫu SSABS – TVSBS - FQS, khai thác công cụ [11] để tiến hành thực nghiệm. Nội dung chính của luận văn gồm phần mở đầu, bốn chương nội dung, phần kết luận. Nội dung của bốn chương nội dung được giới thiệu sơ bộ như sau: Chương 1. Giới thiệu chung về thuật toán sánh mẫu trình bày các khái niệm và đặc trưng của bài toán sánh mẫu, các ứng dụng của sánh mẫu, khái quát về các thuật toán sánh mẫu chính xác nhanh. 2 Chương 2. Họ thuật toán sánh mẫu chính xác nhanh SSABS -TVSBS- FQS giới thiệu về một lớp thuật toán sánh mẫu chính xác nhanh, trình bày và phân tích họ thuật toán SSABS-TVSBS- FQS. Đồng thời, các bước tiến hóa và hiệu suất của ba thuật toán này cũng được giới thiệu. Chương 3. Chương trình thực nghiệm họ thuật toán đối sánh mẫu chính xác nhanh với bộ công cụ Smart. Phần kết luận tổng kết các kết quả chính cũng như các hạn chế của luận văn, đồng thời, ý tưởng về các nghiên cứu tiếp theo cũng được giới thiệu. 3 CHƯƠNG 1. GIỚI THIỆU CHUNG VỀ THUẬT TOÁN SÁNH MẪU 1.1. Bài toán sánh mẫu và phân loại 1.1.1. Bài toán sánh mẫu Theo Simone Faro và Thierry Lecroq [6, 7, 8], bài toán sánh mẫu được phát biểu như sau “Cho một bảng chữ cái S cỡ s, một văn bản T với độ dài n và một mẫu p với độ dài m, bài toán sánh mẫu là việc tìm ra tất cả các lần xuất hiện của mẫu p trong văn bản T đã cho’’. Như đã được giới thiệu, do được ứng dụng trực tiếp trong rất nhiều lĩnh vực như xử lý văn bản, hình ảnh và tín hiệu, phân tích giọng nói và nhận dạng, truy hồi thông tin, nén dữ liệu, sinh học tính toán và hóa học tính toán cho nên bài toán sánh mẫu được nghiên cứu rộng rãi trong khoa học máy tính. Từ năm 1970 tới nay đã có hơn 80 thuật toán sánh mẫu đã được đề xuất và hơn 50% các thuật toán này đã được đưa ra trong 10 năm qua [6, 7, 8]. 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 truy hồi thông tin (information retrieval) và các hệ thống tin - sinh học (bioinformatics). Một lý do nữa, con người ngày nay không chỉ đối mặt với một lượng tài nguyên 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à chỉ ra sự xuất hiện chính xác mẫu trong văn bản mà còn cho phép “một xấp xỉ” giữa mẫu và sự 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 pattern match/search) v.v. 1.1.2. Phân loại bài toán sánh mẫu 1.1.2.1. Sánh mẫu chính xác và sánh mẫu xấp xỉ Phát biểu về bài toán sánh mẫu được trình bày trong mục trên đây [5] thực chất là phát biểu cho bài toán sánh mẫu chính xác. Với bài toán sánh mẫu chính xác, việc tìm ra tất cả các lần xuất hiện của 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 đích T. Trong 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. Độ 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 P trong T là O (mn). 4 Trong bài toán tìm kiếm văn bản trên tập văn bản T, 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 tT. Trong trường hợp độ dài n của t rất lớn và số lượng văn bản trong T rất nhiều (|T|>>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 đề x`uấ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ó để nâng cao tốc độ sánh mẫu luôn là một chủ đề nghiên cứu được cộng đồng 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ỉ (Approximate Pattern Matching) được đặt ra, trong đó, hãy tìm ra 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 [11]. 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 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ẹ. 1.1.2.2. Sánh mẫu trực tuyến và sánh mẫu ngoại tuyến Sánh mẫu ngoại tuyến (offline pattern matching) là trường hợp bài toán sánh mẫu khi mà cả mẫu P và văn bản T đã có sẵn. Một trường hợp đặc biệt chính là cả mẫu P và văn bản T đã có trong bộ nhớ. Trong sánh mẫu ngoại tuyến, việc tiền xử lý dữ liệu đối với P và T có thể được tiến hành từ trước để tạo điều kiện tạo nên các cơ chế phù hợp (bao gồm các cấu trúc dữ liệu bổ sung thích hợp) để tăng tốc độ quá trình sánh mẫu. Thông tin cơ bản như độ dài của P và T được coi như một thông tin tiên liệu về quá trình sánh mẫu. Sánh mẫu trực tuyến (online pattern matching) là trường hợp bài toán sánh mẫu khi mà văn bản T chưa được biết toàn bộ, chẳng hạn như trường hợp tiến hành sánh một mẫu P đã cho với một văn bản T đang được đọc từ Internet. Tiền xử lý dữ liệu không cho phép tiền xử lý dữ liệu, khi đó nhiều thông tin liên quan chưa thể biết, chẳng hạn như độ dài của văn bản T. 5 1.2. Một số ứng dụng của bài toán sánh mẫu Bài toán sánh mẫu không chỉ được ứng dụng trong miền xử lý văn bản (text processing) mà còn được ứng dụng trong nhiều miền ứng dụng khác, chẳng hạn như, xử lý hình ảnh và tín hiệu (image and signal processing), phân tích và tổng hợp tiếng nói (speech analysis and recognition), nén dữ liệu (data compression), truy hồi thông tin (informationretrieval), sinh học và hóa học tính toán (computational biology and chemistry) [5, 6, 7]. 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 ... tìm kiếm một file theo tên file trong hệ điều hành UNIX), cơ chế kiểm tra một file có bị nhiễm virus hay không (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 tìm kiếm các trang web có chứa mẫu p là cụm từ khóa tìm kiếm, xác định mẫu gene bệnh xuất hiện trong đoạn gene của người (các xâu văn bản trong bảng chữ cái gồm bốn chữ cái A, C, G, T) ... 1.3. Một số thuật toán sánh mẫu truyền thống Tất cả các thuật toán sánh mẫu truyền thống đều quét văn bản T với sự trợ giúp của một cửa sổ có độ dài tương đương với độ dài của mẫu, trong đó, cửa sổ là một chuỗi m ký tự liên tiếp trên văn bản. Trong mỗi lần kiểm tra, chương trình sẽ xem xét sự giống nhau giữa mẫu với cửa sổ hiện thời, nếu kết quả đúng thì ghi nhận một lần xuất hiện của mẫu trong xâu. Sau đó, cửa sổ sẽ được dịch sang bên phải trên văn bản cho lần kiểm tra tiếp theo. Trong mỗi lần xem xét, quá trình được bắt đầu từ việc so sánh lần lượt từng phần tử từ trái sang phải của cửa sổ với phần tử tương ứng của mẫu. Nếu xuất hiện một sự không phù hợp có thể dừng việc xem xét cửa sổ hiện thời với mẫu, nếu ngược lại thì quá trình được tiếp tục cho tới phần tử cuối cùng trong cửa sổ. Các thuật toán sánh mẫu là khác nhau ở trật tự so sánh ký tự trên mẫu và khoảng cách mà cửa sổ được di chuyển trên văn bản sau mỗi lần kiểm tra. Nhiều thuật toán sánh mẫu đã được đề xuất mà mỗi thuật toán có những ưu, nhược điểm tùy theo độ dài mẫu, sự thiết lập chu kỳ và bảng chữ cái. Simone Faro và Thierry Lecroq [6] đã trình bày một phân tích đánh giá 85 thuật toán sánh mẫu chính xác, đưa ra mười lớp tình huống sánh mẫu chính xác và tương ứng là 10 thuật toán điển hình cho từng tình huống bài toán sánh mẫu. Các thuật toán sánh mẫu chính xác được phát triển dựa trên một số thuật toán sánh mẫu truyền thống mà điển hình là các Boyer–Moore và Quick Search như giới thiệu dưới đây. 6 1.3.1. Thuật toán Boyer–Moore Boyer–Moore (BM) là một thuật toán tìm kiếm xâu hiệu quả được Boyer và Moore đưa ra vào năm 1977 [6, 8]. Thuật toán BM được xếp là loại thuật toán đo lường đạt chuẩn trong tài liệu về sánh xâu chính xác kể từ khi nó được giới thiệu. Thuật toán BM xử lý trước mẫu P và sử dụng thông tin thu thập được trong suốt bước tiền xử lý để bỏ qua các khối văn bản trong khi đối sánh, kết quả đạt được nhanh hơn rất nhiều thuật toán sánh xâu khác. Nhìn chung, thuật toán BM chạy nhanh hơn khi chiều dài của mẫu tăng lên. Đầu tiên, BM xử lý trước mẫu P để xây dựng hàng dịch chuyển xuất hiện (được viết tắt là bad_shift) với độ dài |Σ|, được xác định bằng việc sử dụng công thức: bad_shift() = min (m-1-k: {0 k 256). Các tác giả tiến hành theo cùng một cách như vậy đối với việc chia mẫu đối sánh theo khổ chữ cái s: rất nhỏ (s<4), nhỏ (4 s<32), rộng (32  s < 128) và rất rộng (s>128). Theo các kết quả thử nghiệm, các tác giả kết luận rằng các thuật toán sau đạt hiệu quả nhất trong các tình huống sau đây: - SA: các mẫu đối sánh rất ngắn và bảng chữ cái rất nhỏ. - TVSBS: các mẫu đối sánh rất ngắn và bảng chữ cái nhỏ, và các mẫu đối sánh dài và bảng chữ cái rộng. - FJS: các mẫu rất ngắn và bảng chữ cái rộng và rất rộng. - EBOM: các mẫu ngắn và bảng chữ cái rộng và rất rộng. - SBNDM-BMH và BMH-SBNDM: mẫu ngắn và bảng chữ cái rất rộng. - HASHq: các mẫu rộng, ngắn và bảng chữ cái nhỏ. - FSBNDM: các mẫu dài và bảng chữ cái rộng và rất rộng. - SBNDMq : các mẫu dài và bảng chữ cái nhỏ. - LBNDM : các mẫu rất dài và bảng chữ cái rất rộng. - SSEF [7]: các mẫu rất dài. Nhưng trong số các thuật toán này chỉ có một thuật toán là SA được thiết kế trong suốt thập kỷ qua, 4 thuật toán khác được dựa trên sự so sánh các kí tự, một thuật toán dựa trên automata trong khi 6 thuật toán còn lại là những thuật toán bit song song. Để giảm thiểu các công việc phát triển các thuật toán đối sánh chuỗi chính xác, các tác giả phát triển một công cụ thông minh (công cụ nghiên cứu các thuật toán đối sánh chuỗi, tham khảo tại http://www.dmi.unict.it/~faro/smart/) cung cấp khung tiêu chuẩn cho các nhà nghiên cứu trong đối sánh chuỗi. Nó giúp cho người sử dụng kiểm tra, thiết kế, đánh giá và hiểu được các giải pháp hiện có để giải quyết vấn đề đối sánh chuỗi chính xác. Hơn nữa nó cung cấp bổ sung hầu hết tất cả các thuật toán đối sánh chuỗi và một dữ liệu vùng đệm văn bản mở rộng. 1.5. Kết luận chương 1 Chương 1 trình bày các nghiên cứu về các bài toán sánh mẫu. Bài toán sánh mẫu có thể chia làm 2 loại là: sánh mẫu chính xác và sánh mẫu xấp xỉ; hoặc sánh mẫu trực tuyến và sánh mẫu ngoại tuyến. Trong đó, bài toán sánh xâu chính xác bao gồm việc tìm ra tất cả những lần xuất hiện của một mẫu đối sánh (p) trong một văn bản (t). Đây là một trong những bài toán được nghiên cứu rộng rãi nhất trong khoa học máy tính, chủ yếu vì các ứng dụng trực tiếp của nó cho rất nhiều lĩnh vực khác 12 nhau như xử lý văn bản - hình ảnh - tín hiệu (text, image and signal processing), phân tích và nhận dạng giọng nói (speech analysis and recognition), truy hồi thông tin (information retrieval), nén dữ liệu (data compression), sinh học và hóa học tính toán (computational biology and chemistry). Chương này tập trung nghiên cứu và trình bày các thuật toán sánh mẫu truyền thống là thuật toán Boyer - Moore và thuật toán QuickSearch.