So khớp chuỗi chính xác (exact string matching) là một trong những bài toán nền tảng của khoa học máy tính. Cho trước một mẫu (pattern) x có độ dài m và một văn bản (text) y có độ dài n, cả hai được viết trên cùng một bảng chữ cái (alphabet) Σ có kích thước σ. Nhiệm vụ là tìm tất cả các vị trí mà mẫu x xuất hiện trong văn bản y.
Nói chính xác hơn, ta cần tìm mọi chỉ số j (với 0 ≤ j ≤ n - m) sao cho:
y[j .. j + m - 1] = x[0 .. m - 1]nghĩa là y[j + i] = x[i] với mọi i từ 0 đến m - 1. Khi điều kiện này thỏa mãn, ta nói mẫu xuất hiện tại vị trí j.
Bài toán này xuất hiện ở khắp nơi: tìm kiếm trong trình soạn thảo văn bản, lọc gói tin trong mạng, tra cứu ADN trong tin sinh học, công cụ tìm kiếm, chống virus dựa trên chữ ký, v.v. Vì dữ liệu có thể rất lớn, hiệu năng của thuật toán so khớp chuỗi có ý nghĩa thực tiễn quan trọng.
Trong toàn bộ tài liệu này, ta thống nhất các ký hiệu sau:
x — mẫu cần tìm, độ dài m, các ký tự đánh chỉ số từ x[0] đến x[m-1].y — văn bản, độ dài n, các ký tự từ y[0] đến y[n-1].Σ — bảng chữ cái; σ = |Σ| là số ký tự phân biệt.0 (theo phong cách ngôn ngữ C).y là một đoạn liên tiếp y[i .. j].x là đoạn x[0 .. i]; một hậu tố (suffix) là đoạn x[i .. m-1].Thông thường ta giả định m ≤ n, vì nếu mẫu dài hơn văn bản thì hiển nhiên không có xuất hiện nào.
Hầu hết các thuật toán so khớp chuỗi hoạt động theo mô hình cửa sổ trượt (sliding window). Ta hình dung một cửa sổ có độ dài m đúng bằng độ dài mẫu, đặt chồng lên văn bản. Ban đầu cửa sổ nằm ở đầu văn bản, canh thẳng với y[0 .. m-1].
Tại mỗi vị trí của cửa sổ, thuật toán thực hiện một phép thử (attempt): so sánh các ký tự của mẫu với các ký tự văn bản nằm trong cửa sổ, theo một thứ tự nào đó. Phép thử có thể kết thúc thành công (tìm thấy một xuất hiện) hoặc thất bại (gặp một cặp ký tự không khớp, gọi là điểm sai lệch — mismatch).
Sau mỗi phép thử, thuật toán dịch cửa sổ sang phải một khoảng gọi là bước dịch (shift). Điểm mấu chốt phân biệt các thuật toán chính là: chúng dịch cửa sổ bao xa và dựa trên thông tin gì. Thuật toán ngây thơ nhất luôn dịch đúng một vị trí; các thuật toán tinh vi hơn tận dụng thông tin thu được trong phép thử để dịch xa hơn mà vẫn không bỏ sót xuất hiện nào.
Một cách phân loại hữu ích là dựa trên thứ tự mà thuật toán so sánh các ký tự bên trong cửa sổ:
m và đôi khi σ.n, m.2n - 1 với Morris-Pratt).| Thuật toán | Tiền xử lý | Tìm kiếm | Bộ nhớ phụ | Hướng so sánh |
|---|---|---|---|---|
| Brute Force | không | O(mn) | O(1) | trái → phải |
| Morris-Pratt | O(m) | O(n+m) | O(m) | trái → phải |
| Knuth-Morris-Pratt | O(m) | O(n+m) | O(m) | trái → phải |
| Otomat hữu hạn đơn định | O(mσ) | O(n) | O(mσ) | trái → phải |
| Shift-Or | O(m+σ) | O(n) | O(σ) | trái → phải |
| Karp-Rabin | O(m) | O(mn) xấu nhất, O(n+m) kỳ vọng | O(1) | trái → phải |
| Boyer-Moore | O(m+σ) | O(mn) xấu nhất, dưới tuyến tính TB | O(m+σ) | phải → trái |
| Horspool | O(m+σ) | O(mn) xấu nhất, dưới tuyến tính TB | O(σ) | phải → trái |
Các mục tiếp theo trình bày chi tiết từng thuật toán: ý tưởng, cơ chế tiền xử lý, cài đặt bằng C, và ví dụ minh họa.