Giới thiệu vấn đề
Đối sánh xâu (String matching) là một chủ đề quan trọng trong lĩnh vực xử lý văn bản. Các thuật toán đối sánh xâu được xem là những thành phần cơ sở được cài đặt cho các hệ thống thực tế đang tồn tại trong hầu hết các hệ điều hành. Hơn thế nữa, các thuật toán đối sánh xâu cung cấp các mô hình cho nhiều lĩnh vực khác nhau của khoa học máy tính: xử lý ảnh, xử lý ngôn ngữ tự nhiên, tin sinh học và thiết kế phần mềm.
String-matching được hiểu là việc tìm một hoặc nhiều xâu mẫu (pattern) xuất hiện trong một văn bản (có thể là rất dài). Ký hiệu xâu mẫu hay xâu cần tìm là X =(x
0, x
1,..,x
m-1) có độ dài m. Văn bản Y =(y
0, y
1,..,y
n-1) có độ dài n. Cả hai xâu được xây dựng từ một tập hữu hạn các ký tự Alphabet ký hiệu là S với kích cỡ là s. Như vậy một xâu nhị phân có độ dài n ứng dụng trong mật mã học cũng được xem là một mẫu. Một chuỗi các ký tự ABD độ dài m biểu diễn các chuỗi AND cũng là một mẫu.
Input:
- Xâu mẫu X =(x0, x1,.., xm-1), độ dài m.
- Văn bản Y =(y0, x1,.., yn-1), độ dài n.
Output:
- Tất cả vị trí xuất hiện của X trong Y.
Các thuật toán tìm kiếm mẫu, string.
Chính vì sự cần thiết và quan trọng của chủ đề này dẫn tới sự xuất hiện của hàng chục, hàng trăm thuật toán liên quan nhằm cải thiện tốc độ so sánh xâu, cải thiện độ phức tạp…
Ở bài này mình sẽ giới thiệu 1 số thuật toán tìm kiếm mẫu khác sau:
