Module 2 — Tổng kết & cheat sheet

TL;DR: Module 2 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 đa mẫu, Z-function O(n+m) nhìn cùng lớp bài từ góc độ z-box, và Aho-Corasick O(n+tổng_m+k) quét đồng thời triệu pattern trong một lần duyệt. Trang này là cheat sheet để bookmark: bảng chọn thuật toán, glossary 11 thuật ngữ, 6 pitfall 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 — phần đã biết bị bỏ qua hoàn toàn.

Bài 02 — KMP hỏi câu sắc bén: 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) mã hóa 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 → O(n). Build lps trong O(m) bằng cách áp chính ý tưởng KMP lên pattern so 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 sánh hash trước, nếu trùng mới so ký tự (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 kỹ thuật z-box để tính trong O(n) bằng cách tái dùng thông tin từ z-box hiện đang mở. Z-function và failure function (lps) giải cùng lớp bài — chuyển đổi được cho nhau — nhưng cú pháp và trực giác khác nhau.

Bài 05 — Aho-Corasick tổng quát hóa failure function của KMP lên trie nhiều pattern. Failure link trên cây là lps đa mẫu: khi không có transition hợp lệ, follow failure link (giống j <- lps[j-1]). Build O(tổng_m × |alphabet|), search O(n + tổng_m + k). ClamAV dùng để quét đồng thời 8 triệu chữ ký virus trong một lần đọc file.

Bài 06 — Mini-challenge cho bạn tự implement grep bằng KMP: computeLPS trong O(m), kmpSearchAll với con trỏ text không lùi, xử lý overlapping bằng reset j <- lps[j-1] sau khi tìm thấy.

Bài 07 — Case study cho thấy hai hệ thống production dùng hai cấu trúc khác nhau cho hai bài toán khác nhau: ClamAV dùng Aho-Corasick cho multi-pattern scanning, Lucene dùng FST (Finite State Transducer) cho term dictionary lookup với prefix search.

🗺️ Cheat sheet

Bảng chọn thuật toán

Quyết định chọn thuật toán

graph TD
    START["Bài toán\nstring matching"] --> Q1{"Số pattern?"}
    Q1 -- "1 pattern" --> Q2{"Cần tất định\n100%?"}
    Q2 -- "Có" --> KMP2["KMP — O(n+m)\nhoặc Z-function"]
    Q2 -- "OK xác suất" --> RK["Rabin-Karp — O(n+m) kỳ vọng"]
    Q1 -- "Vài chục đến\nvài nghìn" --> Q3{"Pattern cố định\nhay thay đổi?"}
    Q3 -- "Thay đổi" --> RK2["Rabin-Karp multi\nhoặc Bloom filter"]
    Q3 -- "Cố định" --> Q4{"Có cần build\nlại thường xuyên?"}
    Q4 -- "Không" --> AC["Aho-Corasick\nO(n + tổng_m + k)"]
    Q4 -- "Có" --> RK2
    Q1 -- "Hàng triệu\npattern" --> AC

KMP vs Rabin-Karp vs Aho-Corasick — so sánh nhanh

📖 Glossary module

⚠️ Pitfall tổng hợp

Pitfall 1 — Nhầm lps[i] là "đã khớp tới đâu" thay vì "prefix = suffix". lps[i] là thuộc tính nội tại của pattern, không phải số ký tự đã khớp với text. Lẫn lộn dẫn đến dịch pattern sai khi lệch — matching sẽ bỏ sót lần xuất hiện hoặc báo nhầm.

-- SAI: tưởng lps[i] = số ký tự đã khớp với text tại vị trí i
-- ĐÚNG: lps[i] = độ dài prefix-suffix dài nhất của pattern[0..i]
-- Tính trước 1 lần, dùng lại cho mọi text

Pitfall 2 — Lùi len rồi tăng i trong computeLPS.

-- SAI: trong nhánh lệch vẫn tăng i
else if len > 0:
    len <- lps[len-1]
    i <- i + 1      -- BUG: bỏ qua cơ hội so pattern[i] với prefix ngắn hơn

-- ĐÚNG: chỉ lùi len, giữ i để so lại
else if len > 0:
    len <- lps[len-1]

Tăng i ở nhánh lệch làm mất cơ hội thử prefix-suffix ngắn hơn — bảng lps sai, kéo theo matching sai.

Pitfall 3 — Reset j về 0 thay vì lps[j-1] sau khi tìm thấy.

-- SAI: bỏ sót overlapping
if j = m:
    báo tìm thấy
    j <- 0          -- BUG: P="AA", T="AAAA" chỉ báo [0, 2] thay vì [0, 1, 2]

-- ĐÚNG: reset về lps[j-1] để bắt được overlap
if j = m:
    báo tìm thấy tại i - j
    j <- lps[j-1]

Pitfall 4 — Rabin-Karp không verify khi hash trùng. Hash trùng (spurious hit) xảy ra với xác suất nhỏ nhưng hữu hạn. Nếu bỏ qua bước verify ký tự, thuật toán sẽ báo nhầm.

-- SAI: chỉ so hash, không verify
if hash(T[i..i+m-1]) = hash(P): báo tìm thấy

-- ĐÚNG: verify sau khi hash trùng
if hash(T[i..i+m-1]) = hash(P):
    if T[i..i+m-1] = P: báo tìm thấy  -- O(m) nhưng hiếm khi xảy ra

Pitfall 5 — Xây Aho-Corasick từ pattern thay đổi liên tục. Aho-Corasick phải rebuild toàn bộ khi thêm pattern mới — O(tổng_m × |alphabet|). Nếu tập pattern thay đổi thường xuyên, chi phí rebuild có thể vượt lợi ích. Trong trường hợp này, Rabin-Karp multi-pattern hoặc Bloom filter phù hợp hơn.

Pitfall 6 — Quên failure link propagate output trong Aho-Corasick. Khi automaton dừng tại node u, không chỉ pattern của node u khớp mà còn tất cả pattern của các node trên failure chain của u. Nếu chỉ báo output của node hiện tại mà bỏ qua failure chain, sẽ bỏ sót pattern ngắn hơn là suffix của pattern vừa tìm thấy.

-- SAI: chỉ báo output tại node hiện tại
if state.isOutput: report state.patterns

-- ĐÚNG: duyệt output link chain
node <- state
while node != null:
    if node.isOutput: report node.patterns
    node <- node.outputLink

✅ Self-assessment

Bạn đã đạt module này nếu trả lời được:

• Giải thích được vì sao naive matching lãng phí O(n·m) trên đầu vào nhiều lặp và con trỏ text phải lùi — cho ví dụ cụ thể với T = "AAAAAB" và P = "AAAAB".
  • Nếu chưa: đọc lại bài 01 — Naive matching mục phân tích worst-case.
• Implement được KMP failure function lps trong O(m) và matching trong O(n) không lùi con trỏ text — bao gồm xử lý đúng trường hợp overlapping bằng j <- lps[j-1].
  • Nếu chưa: làm lại bài 06 — Mini-challenge từ đầu không xem lời giải; đọc lại bài 02 — KMP mục computeLPS và trace.
• Compare được KMP, Rabin-Karp và Aho-Corasick theo preprocessing, matching complexity, single/multi-pattern và tất định/xác suất — và chọn đúng thuật toán cho từng kịch bản.
  • Nếu chưa: đọc lại bảng cheat sheet phần trên và bài 07 — Case study mục "Vì sao chọn thuật toán nào".
• Choose được thuật toán phù hợp khi cho bài toán cụ thể — phân biệt được: single pattern tất định (KMP), multi-pattern cố định quy mô lớn (Aho-Corasick), multi-pattern thay đổi liên tục (Rabin-Karp), lookup có prefix search (FST/Trie).
  • Nếu chưa: đọc lại sơ đồ quyết định trong cheat sheet và so sánh ClamAV vs Lucene trong bài 07.
• Trace được cơ chế Aho-Corasick (trie + failure link + output link) — giải thích được vì sao search phase là O(n + tổng_m + k) thay vì O(n × số_pattern).
  • Nếu chưa: đọc lại bài 05 — Aho-Corasick mục failure link và search phase, so sánh với cách KMP dùng j <- lps[j-1].

🚀 What's next

Module 2 hoàn thành bức tranh về tìm kiếm chuỗi — từ single pattern đến multi-pattern đến hệ thống production. Module 3 — Big data & Streaming đưa những kỹ thuật này vào môi trường phân tán: khi text không vừa một máy, khi pattern streaming liên tục, khi cần approximate matching thay vì exact. Các thuật toán như Bloom filter (xấp xỉ multi-pattern membership), Count-Min Sketch (tần suất xấp xỉ) và sliding window trên data stream đều xây trên nền tảng của module này.

Bài tiếp theo: Module 3 — Big data & Streaming

📚 Tài liệu mở rộng

• Introduction to Algorithms (CLRS), Chapter 32 — String Matching: Trình bày đầy đủ cả 4 thuật toán (naive, Rabin-Karp, finite automaton, KMP) với chứng minh độ phức tạp. Section 32.4 KMP dùng bất biến vòng lặp để chứng minh tính đúng của prefix function.
• Aho & Corasick (1975) — "Efficient string matching: An aid to bibliographic search": Bài báo gốc 12 trang, vẫn readable. Giới thiệu trie + failure function + output function. ACM Digital Library.
• Competitive Programmer's Handbook (Laaksonen), Chapter 26 — String algorithms: Trình bày Z-function, KMP, Aho-Corasick gọn cho competitive programming. Miễn phí tại cses.fi.
• Lucene FST — Mike McCandless blog: Giải thích chi tiết cách Lucene implement FST cho term dictionary, bao gồm memory layout và performance benchmark. Tìm kiếm "lucene fst mike mccandless".
• ClamAV source — libclamav/matcher-ac.c: File C implement Aho-Corasick trong ClamAV. Xem cách signature database được load, trie được xây, và scan được thực hiện trên real file. GitHub clamav.