Tổng kết module Pattern matching và cheat sheet

TL;DR: Module này trang bị năm thuật toán tìm kiếm chuỗi theo thứ tự tăng dần về độ phức tạp và khả năng: naive O(n·m) làm nền để thấy vấn đề, KMP O(n+m) loại bỏ lãng phí bằng failure function, Rabin-Karp O(n+m) kỳ vọng dùng rolling hash để mở rộng sang nhiều pattern, Z-function O(n+m) nhìn cùng lớp bài từ góc độ z-box, và Aho-Corasick quét đồng thời triệu pattern trong một lần duyệt O(n+z) sau khi dựng automaton. Trang này là cheat sheet để bookmark: bảng chọn thuật toán, glossary 11 thuật ngữ, 7 bẫy hay gặp, và self-assessment 5 câu khớp learning outcomes.

Đã đi qua những gì

Bạn bắt đầu từ bài 01, Naive matching: so sánh từng vị trí trong text, worst-case O(n·m) khi text và pattern nhiều ký tự lặp (ví dụ "AAAA...A" và "AAA...AB"). Naive lãng phí vì mỗi lần lệch nó lùi con trỏ text về và so lại từ đầu, bỏ qua hoàn toàn phần đã biết.

Bài 02, KMP hỏi một câu: khi đã khớp được j ký tự rồi mới lệch, tại sao phải so lại? Failure function lps[i] (longest proper prefix = suffix) ghi lại thông tin này: khi lệch tại j, nhảy j <- lps[j-1] thay vì lùi text. Con trỏ text không bao giờ lùi nên matching O(n). Xây lps trong O(m) bằng cách chạy KMP lên pattern, tức so pattern với chính nó.

Bài 03, Rabin-Karp tiếp cận theo hướng khác: thay vì phân tích cấu trúc pattern, dùng rolling hash: hash của cửa sổ trượt tính được từ hash cửa sổ trước trong O(1). So hash trước, nếu trùng mới so ký tự để xác nhận (verify). Worst-case O(n·m) nếu hash collision nhiều, nhưng O(n+m) kỳ vọng. Mở rộng tự nhiên sang tìm đồng thời k pattern bằng cách lưu hash của tất cả pattern vào hash set.

Bài 04, Z-function tính mảng z[i] = độ dài của đoạn bắt đầu từ i trùng với prefix của chuỗi. Dùng z-box để tính trong O(n), bằng cách tái dùng thông tin từ z-box đang mở. Z-function và failure function (lps) giải cùng lớp bài và chuyển đổi được cho nhau, nhưng cách viết và trực giác khác nhau.

Bài 05, Aho-Corasick mở rộng failure function của KMP lên trie nhiều pattern. Failure link trên cây là lps cho nhiều pattern: khi không có transition hợp lệ, đi theo failure link (giống j <- lps[j-1]). Dựng automaton mất O(tổng_m × |alphabet|) một lần (hoặc O(tổng_m) nếu cạnh con lưu dạng dictionary), quét text O(n + z). ClamAV dùng nó cho nhóm chữ ký có wildcard, quét nhiều chữ ký trong một lần đọc file (tài liệu ClamAV không công bố tổng số chữ ký, nên bài không lấy con số nào).

Bài 06, mini-challenge cho bạn cài naive và KMP kèm bộ đếm số phép so sánh: tìm mọi vị trí kể cả chồng lấn (reset j <- lps[m-1] sau khi khớp), rồi đối chiếu số đếm trên input adversarial với công thức (n - m + 1) · m của naive và chặn 2n của KMP.

Bài 07, case study cho thấy ba hệ thống production chọn ba cấu trúc cho ba bài toán: ClamAV dùng Aho-Corasick để quét nhiều chữ ký cùng lúc, GNU grep dùng họ Boyer-Moore (so từ phải sang trái, nhảy cóc) cho một pattern, Lucene dùng FST (Finite State Transducer) làm chỉ mục tiền tố cho term dictionary.