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 LUAN VAN CHAT LUONG download : add luanvanchat@agmail.com 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. LUAN VAN CHAT LUONG download : add luanvanchat@agmail.com 13 CHƯƠNG 2: HỌ THUẬT TOÁN SÁNH MẪU CHÍNH XÁC NHANH SSABS - TVSBS – FQS 2. Giới thiệu về các biến thể của thuật toán Quick Search Trong [7], Simone Faro và Thierry Lecroq cung cấp một khái quát về các thuật toán sánh mẫu được phát triển dựa trên thuật toán Quick Search. Một số thuật toán điển hình như sau: - Thuật toán SSABS được công bố năm 2004 [8] là một kết hợp chiến lược chuyển dịch của thuật toán QS và chiến lược kiểm thử nghiệm của thuật toán Raita.
Thuật toán TVSBS được công bố năm 2006 [4] là phiên bản cải tiến của SSABS. Hai thuật toán này có độ phức tạp thời gian trong trường hợp xấu nhất là O(nm) với n, m tương ứng là kích thước của mẫu và xâu văn bản. - Thuật toán Franek-Jennings-Smyth được công bố năm 2007 là một thuật toán kết hợp đơn giản các trường hợp độ phức tạp thời gian tồi nhất của thuật toán Knuth-Morris-Pratt với các hành vi trung bình tốt hơn của thuật toán QS. - Thuật toán Forward BOM (Forward-Backward-Oracle-Matching) được công bố năm 2008 là một thuật toán kết hợp các ý tưởng tiến bộ của thuật toán Extended-BOM và thuật toán QS.
Luận văn này tập trung vào một nhóm thuật toán biến thể của thuật toán Quick Search mà được kiểm định là có lợi thế khi mẫu ngắn với bảng chữ nhỏ hoặc mẫu dài với bảng chữ lớn [6] với đại diện là thuật toán TVSBS. Các mục dưới đây trình bày lần lượt ba thuật toán thuộc nhóm này là SSABS (Sheik-Sumit-Anindya- Balakrishnan-Seka) [8], TVSBS (Thathoo-Virmani-Sai-Balakrishnan-Sekar) [4] và FQS (faster quick search) [3]. Thuật toán đối sánh mẫu nhanh SSABS 2. Giới thiệu Thuật toán SSABS được S.
Sheik và cộng sự công bố vào năm 2004 [8] và được đặt tên theo tên năm tác giả S. Aggarwal - Anindya Poddar - N. Sheik và cộng sự, hầu hết các thuật toán sánh mẫu nổi tiếng làm việc theo hai giai đoạn: giai đoạn tiền xử lý và giai đoạn tìm kiếm. Trong giai đoạn tiền xử lý, các thuật toán này xử lý mẫu và sử dụng thông tin này trong giai đoạn tìm kiếm để giảm thiểu tổng số lượng so sánh ký tự và do đó giảm thời gian thực hiện tổng thể.
Hiệu quả của một thuật toán chủ yếu phụ thuộc vào giai đoạn tìm kiếm. Mục tiêu chính của các thuật toán đối sánh mẫu là để giảm thiểu số lượng so LUAN VAN CHAT LUONG download : add luanvanchat@agmail.com 14 sánh ký tự giữa mẫu và văn bản nhằm làm tăng hiệu quả tổng thể. Sự cải tiến trong hiệu quả của một tìm kiếm có thể đạt được bằng cách thay đổi trật tự các ký tự được so sánh mỗi lần thử nghiệm và bằng việc lựa chọn yếu tố dịch chuyển cho phép bước nhảy của một số ký tự được xác định trước trong văn bản sau mỗi lần thử nghiệm. Các thuật toán đối sánh mẫu quét văn bản với sự hỗ trợ của một cửa sổ, có kích thước tương đương với độ dài của mẫu.
Bước đầu tiên là gắn kết các phần cuối cùng bên trái của cửa sổ và văn bản, sau đó so sánh với các ký tự tương ứng của cửa sổ và mẫu. Sau mỗi một đối sánh hoặc lỗi đối sánh của mẫu, cửa sổ văn bản được dịch chuyển sang bên phải. Vấn đề đặt ra ra là có bao nhiêu ký tự được yêu cầu dịch chuyển cửa sổ trên văn bản. Các giá trị dịch chuyển này dựa trên phương pháp luận được sử dụng bởi các thuật toán khác nhau.
Quy trình đó được lặp đi lặp lại cho tới khi phần cuối cùng bên phải của cửa sổ nằm trong phần cuối cùng bên phải của văn bản. Thuật toán Trật tự các so sánh được thực hiện bằng việc so sánh ký tự cuối cùng của cửa sổ và mẫu, sau khi đối sánh, thuật toán tiếp tục so sánh ký tự đầu tiên của cửa sổ và mẫu. Như vậy, một sự tương đồng ban đầu có thể được thiết lập giữa mẫu và cửa sổ, các ký tự còn lại được so sánh từ phải qua trái cho tới khi đối sánh hoàn toàn hoặc lỗi đối sánh xảy ra. Sau mỗi lần thử nghiệm, bước nhảy của cửa sổ đạt được bằng giá trị dịch chuyển qsBc đối với ký tự được đặt ở vị trí liền kề với cửa sổ.
Do sự phụ thuộc của các ký tự lân cận mạnh hơn so với các ký tự khác nên cần so sánh ký tự cuối cùng trước tiên và ký tự đầu tiên thứ hai sau đó tiếp tục so sánh các ký tự theo trình tự từ phải sang trái của mẫu và cửa sổ. Vì vậy, sẽ tốt hơn nếu tạm dừng việc so sánh các ký tự lân cận nhau. Xác xuất việc đánh giá một đối sánh chính xác giữa mẫu với cửa sổ được tăng lên với một lượng tối thiểu so sánh bằng cách kết hợp sự tương đồng ban đầu. Thêm vào đó, sự tối đa hóa bước nhảy cho cửa sổ giúp giảm thiểu số lượng so sánh ký tự với ký tự và làm tăng hiệu suất.
Giai đoạn tiền xử lý: Giai đoạn này được thực hiện bằng việc sử dụng hàm dịch chuyển qsBc đối với tất cả các ký tự trong bảng chữ cái được thiết lập. Một bảng được hình thành với cỡ σ, chứa ký tự và giá trị bước nhảy tương ứng của nó. Giá trị qsBc cho một bảng chữ cái cụ thể được xác định như vị trí của ký tự trong mẫu từ phải sang trái, nếu điều đó không diễn ra trong mẫu thì giá trị sẽ bằng (m+1). Giá trị bước nhảy cho mỗi ký tự được lưu trữ trong bảng qsBc được sử dụng trong giai đoạn tìm kiếm.
Trong giai đoạn tìm kiếm, sau mỗi lần thử, bước nhảy của cửa sổ được tính toán LUAN VAN CHAT LUONG download : add luanvanchat@agmail.com 15 bằng việc đạt được giá trị dịch chuyển của ký tự ngay sau cửa sổ. Giá trị bước nhảy tối đa đối với cửa sổ được nhận ra khi ký tự (ký tự ngay sau cửa sổ) không có mặt ở trong mẫu. Xác suất của một ký tự xuất hiện trong mẫu ít hơn khi cỡ bảng chữ cái lớn điều đó giúp cho việc đạt được bước nhảy tối đa của cửa sổ. Trong thuật toán này ta xem xét hàm dịch chuyển qsBC của Quick-search vì những lí do sau: (1) Giá trị qsBc thường được xác định ≥ 1, do đó nó có thể làm việc một cách độc lập và ra một thuật toán nhanh.
Mặt khác, bmBc đôi khi mang lại giá trị dịch chuyển ≤ 0 và trong các trường hợp như vậy nó không được sử dụng một cách độc lập. Do vậy, nó phải làm việc cùng với bmGs (dịch chuyển khớp của Boyer-Moore) để tính toán bước nhảy của cửa sổ. (2) qsBC = bmBC, trừ các ký tự cuối cùng trong mẫu. Do đó, qsBc luôn luôn có giá trị dịch chuyển nhiều hơn bmBc trong thực tế.
(3) qsBc không phụ thuộc vào trật tự các so sánh giữa mẫu và cửa sổ. Vì qsBc được xác định liên quan tới một ký tự nằm ngoài phạm vi so sánh hiện tại của mẫu. Giai đoạn tìm kiếm: Bước 1 và bước 2 của giai đoạn này giải quyết trật tự so sánh ký tự với ký tự giữa cửa sổ và mẫu. Bước 1: Để tìm ra sự tương đồng ban đầu giữa mẫu và cửa sổ, trước tiên, ký tự cuối cùng của mẫu và cửa sổ được so sánh, trong trường hợp có đối sánh, ký tự đầu tiên của mẫu và ký tự tương ứng trong cửa sổ được so sánh.
Nếu những ký tự này đối sánh, thuật toán đi vào bước tiếp theo, nếu không nó sẽ đi tới bước cuối cùng. Bước 2: Sau khi tạo một sự tương đồng ban đầu giữa cửa sổ và mẫu, các ký tự còn lại được so sánh theo trật tự từ phải sang trái cho đến khi một lỗi đối sánh xảy ra hoặc tất cả các ký tự (m – 2) đối sánh. Nếu tất cả các ký tự đối sánh, thuật toán hiển thị vị trí tương ứng (j) của cửa sổ trên văn bản. Sau đó thuật toán đi vào bước cuối cùng.
Bước 3: Trong bước này, sự tính toán khoảng cách mà cửa sổ được dịch chuyển được tính toán sử dụng qsBc, đã được tạo ra trong suốt giai đoạn tiền xử lý, đối với ký tự đầu tiên ngay sau cửa sổ. Quy trình này lặp lại cho tới khi cửa sổ đạt được vị trí ngoài (n - m +1). Phân tích thuật toán: LUAN VAN CHAT LUONG download : add luanvanchat@agmail.com 16 Trong giai đoạn tiền xử lý: Thời gian tính toán của của thuật toán là O(m + σ) và độ phức tạp không gian là O(σ). Trong giai đoạn tìm kiếm: Trong trường hợp tốt nhất độ phức tạp thời gian là O([(n/(m + 1))]).
Các ký tự không xảy ra trong mẫu có giá trị dịch chuyển (m+1) được xác định bởi qsBc được tính toán trong suốt giai đoạn tiền xử lý. Việc xem xét trường hợp tốt nhất là các ký tự trong mẫu hoàn toàn khác so với các ký tự trong văn bản, đối sánh m ký tự của mẫu trong văn bản thu được giá trị dịch chuyển (m+1) tại mỗi lần thử nghiệm và do đó độ phức tạp thời gian là O([(n/(m + 1))]). Trong trường hợp xấu nhất độ phức tạp thời gian là O(m(n-m+1)). Thực tế tất cả các ký tự trong văn bản được đối sánh không hơn m thời gian, tổng số các so sánh ký tự đối với n ký tự của văn bản không thể nhiều hơn m(n+1); Sự dịch chuyển bằng 1 và các ký tự được đối sánh trong mỗi lần thử nghiệm.
Điều này được nhận ra khi các ký tự trong mẫu tương đồng chính xác với các ký tự trong văn bản.