Aho-Corasick: automaton so khớp đa mẫu

TL;DR: Bài toán nhiều pattern (đa mẫu): cho tập k pattern, tìm tất cả lần xuất hiện của bất kỳ pattern nào trong text T. Chạy KMP k lần tốn O(k·n), quá chậm khi k lớn. Aho-Corasick xây một trie từ toàn bộ pattern (O(tổng độ dài)), rồi thêm failure link (mũi tên "nhảy về chỗ gần nhất còn hy vọng", mở rộng lps của KMP lên cây trie) bằng BFS một lần. Kết quả là một automaton (máy trạng thái: mỗi node là một trạng thái, mỗi ký tự đọc vào chuyển sang node khác) cho phép quét T một lần duy nhất O(n), thu thập mọi lần khớp. Tổng thể O(Σ|Pᵢ| + n + z) với z là số lần khớp. Đây là nền tảng của ClamAV (antivirus), Snort (IDS), và các hệ thống quét chữ ký song song.

Ở bài trước bạn thấy Z-function giải bài đơn pattern bằng cách ghép P + '#' + T. Với k = 10.000 pattern (như cơ sở dữ liệu chữ ký virus), ghép và quét 10.000 lần là không thực tế. Aho-Corasick (1975, Bell Labs) dồn toàn bộ pattern vào một cấu trúc và quét text đúng một lần.

1. Bài toán và tại sao cần Aho-Corasick

Đầu vào: tập pattern {P₁, P₂, ..., Pₖ} và text T độ dài n. Tổng độ dài pattern M = Σ|Pᵢ|.

Đầu ra: mọi cặp (i, j) sao cho pattern Pᵢ kết thúc tại vị trí j trong T.

So sánh chi phí:

Σ là kích thước bảng chữ cái. O(M·Σ) là khi dựng đầy đủ bảng chuyển cho mọi (node, ký tự). Bài này lưu cạnh con theo dạng dictionary và đi theo failure link lúc quét, nên build chỉ O(M) (amortized, xem mục 5), quét O(n + z): tuyến tính trên cả hai pha. Với Σ cố định (ASCII = 256), hai cách chênh nhau một hằng số. Ứng dụng thực tế (ClamAV, Snort) nằm ở bài case study.