Module 2 — Pattern matching & String: tổng quan

TL;DR: Module 2 dạy năm thuật toán tìm kiếm chuỗi — từ naive O(n·m) dễ cài nhưng chậm, KMP O(n+m) không bao giờ lùi con trỏ text, Rabin-Karp dùng rolling hash để mở rộng sang đa mẫu, Z-function một lần duyệt cho tiền tố-hậu tố, đến Aho-Corasick quét đồng thời cả triệu pattern trong một lần đọc file. Đây là nền tảng của search engine, antivirus, trình biên dịch và bioinformatics — những hệ thống không thể chờ naive matching hoàn thành.

Vì sao module này tồn tại

Mỗi ngày bạn dùng grep để tìm chuỗi trong file source code, trình antivirus ClamAV quét file tải về của bạn đối chiếu với hơn 8 triệu chữ ký virus, và Elasticsearch trả về kết quả tìm kiếm cho hàng triệu document trong vài millisecond. Tất cả đều giải quyết cùng một bài toán cơ bản: tìm pattern P trong text T, nhưng ở quy mô mà naive matching O(n·m) không thể đáp ứng.

Với ClamAV: nếu dùng KMP chạy từng chữ ký một, mỗi file cần 8 triệu lần duyệt — hoàn toàn không khả thi khi quét real-time. Aho-Corasick xây một automaton duy nhất từ toàn bộ chữ ký rồi duyệt file một lần duy nhất, phát hiện mọi chữ ký khớp đồng thời.

Với bioinformatics: chuỗi DNA người dài 3 tỷ base pair (A/T/C/G). Tìm một đoạn gene dài 100 bp trong toàn bộ genome với naive matching — tệ nhất mất 3 × 10¹¹ phép so sánh. KMP cắt xuống còn 3 tỷ + 100 = O(n+m).

Module này không chỉ dạy thuật toán — nó dạy cách thoát khỏi worst-case bằng thông tin bạn đã biết: KMP tận dụng prefix-suffix của pattern, Rabin-Karp tận dụng tính chất sliding window của hash, Aho-Corasick tận dụng cấu trúc trie để chia sẻ prefix giữa các pattern.

Sau module này bạn sẽ

• Explain 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.
• Implement KMP failure function (lps) trong O(m) và matching trong O(n) không lùi con trỏ text.
• Compare KMP, Rabin-Karp và Aho-Corasick theo preprocessing, matching, single/multi-pattern, tất định/xác suất để chọn đúng thuật toán.
• Choose thuật toán string matching phù hợp dựa trên bài toán: số lượng pattern, kích thước alphabet, yêu cầu xác suất hay tất định.
• Trace cơ chế Aho-Corasick (trie + failure link) để hiểu vì sao quét đồng thời nhiều pattern trong O(n + tổng_m + k).

Ba nhóm tiếp cận

Năm thuật toán trong module rơi vào ba nhóm tư tưởng — nắm được nhóm nào giải bài toán nào là chìa khoá chọn đúng công cụ:

Naive, KMP, Z-function — trượt con trỏ trên text, tận dụng cấu trúc pattern

Rabin-Karp — so hash của cửa sổ thay vì từng ký tự, mở sang đa mẫu

Aho-Corasick — trie nhiều pattern + failure link, quét tất cả trong một lần

Lộ trình module

flowchart LR
    OV["00\nTổng quan"] --> N1["01\nNaive\nO(n·m)"]
    N1 --> KMP["02\nKMP\nO(n+m)"]
    KMP --> RK["03\nRabin-Karp\nRolling hash"]
    RK --> ZF["04\nZ-function\nZ-box"]
    ZF --> AC["05\nAho-Corasick\nTrie+failure"]
    AC --> MC["06\nMini-challenge\ngrep bằng KMP"]
    MC --> CS["07\nCase study\nLucene & ClamAV"]
    CS --> REC["08\nTổng kết"]

Thứ tự bài — vì sao thiết kế như vậy

Bài 01 — Naive là điểm xuất phát bắt buộc vì nó đặt đúng câu hỏi: tại sao lùi con trỏ text lại lãng phí? Không thấy worst-case O(n·m) của naive, bạn sẽ không hiểu KMP giải quyết vấn đề gì.

Bài 02 — KMP là thuật toán nền tảng của module. Failure function (prefix function, lps) là khái niệm cốt lõi — mọi bài sau đều dùng hoặc tổng quát hoá tư tưởng này. KMP xứng đáng đọc kỹ nhất trong module.

Bài 03 — Rabin-Karp giới thiệu hướng tiếp cận hoàn toàn khác: thay vì phân tích cấu trúc pattern, dùng rolling hash để so sánh hash của cửa sổ trượt. Rabin-Karp O(n+m) kỳ vọng — không tất định như KMP, nhưng mở rộng tự nhiên sang đa pattern, và là cầu nối sang cấu trúc dữ liệu hash.

Bài 04 — Z-function là một cách nhìn khác về cùng lớp bài toán prefix: mảng z[i] cho biết đoạn bắt đầu từ vị trí i trùng bao nhiêu ký tự với prefix của chuỗi. Z-function và failure function (lps) đều giải cùng lớp bài — học cả hai giúp thấy bài toán từ hai góc độ và chuyển đổi linh hoạt.

Bài 05 — Aho-Corasick là đỉnh của module: tổng quát hoá KMP failure function lên một trie nhiều pattern. Failure link trên cây chính là lps đa mẫu. Đây là thuật toán được ClamAV, nhiều IDS/IPS và bioinformatics tools dùng để quét đồng thời hàng triệu pattern.

Bài 06 — Mini-challenge áp dụng KMP vào bài toán grep cụ thể: tìm tất cả vị trí xuất hiện của pattern trong file, kể cả chồng lấn. Cầu nối từ hiểu lý thuyết sang tự implement.

Bài 07 — Case study đọc cơ chế thật của ClamAV (Aho-Corasick cho multi-signature) và Lucene (FST cho term lookup, inverted index cho ranked search). Bài này không dạy kỹ thuật mới — nó cho thấy bạn đã có đủ nền để đọc source code của production tools.

Bài 08 — Tổng kết gom cheat sheet, glossary và self-assessment.

Bản đồ khái niệm

graph TD
    PROB["Tìm pattern P trong text T"] --> Q1{"Số pattern?"}
    Q1 -- "1 pattern" --> Q2{"Cần tất định?"}
    Q2 -- "Có" --> Q3{"Cần prefix/Z info?"}
    Q3 -- "Failure function" --> KMP2["KMP — O(n+m)"]
    Q3 -- "Z-box" --> ZF2["Z-function — O(n+m)"]
    Q2 -- "OK xác suất" --> RK2["Rabin-Karp — O(n+m) kỳ vọng"]
    Q1 -- "Nhiều pattern" --> Q4{"Pattern cố định\nhay thay đổi?"}
    Q4 -- "Cố định, build 1 lần" --> AC2["Aho-Corasick — O(n + tổng_m + k)"]
    Q4 -- "Pattern thay đổi liên tục" --> RK3["Rabin-Karp multi-pattern\nhoặc Bloom filter"]

Yêu cầu trước

Module này xây trên hai nền tảng từ các module trước:

• Big-O và amortized analysis — từ Thuật toán Căn bản — Big-O và Amortized analysis: phân tích tại sao O(n) matching có nhánh "giảm j mà không tăng i" vẫn tổng O(n).
• Hash table và trie — từ Thuật toán Cốt lõi — Hash function và Trie: Rabin-Karp dùng polynomial hash với modular arithmetic; Aho-Corasick xây trên trie.

Nếu bạn chưa quen với trie (cây prefix), đọc bài trie trong Thuật toán Cốt lõi — Module 1 trước khi học Aho-Corasick.

Time budget

Cách học module này hiệu quả

Đọc theo thứ tự, đừng bỏ bài 01. Naive matching có vẻ tầm thường, nhưng bài đó xây đúng intuition về "lùi con trỏ text" — nếu bỏ qua, failure function của KMP sẽ chỉ là công thức, không phải cơ chế.

Với KMP, trace tay trước khi đọc code. Lấy P = "ABABC", T = "ABABABABC", vẽ bảng lps tay rồi mô phỏng matching từng bước. Cảm giác "i không bao giờ lùi" chỉ đến sau khi trace tay ít nhất một ví dụ.

Với Rabin-Karp, để ý modular arithmetic. Hash polynomial dùng mod prime — hiểu tại sao cần mod và tại sao spurious hit (hash trùng nhưng chuỗi khác) có thể xảy ra là cốt lõi của bài.

Với Aho-Corasick, đọc sau khi đã vững KMP. Failure link trên trie là failure function của KMP mở rộng — nếu KMP chưa rõ, Aho-Corasick sẽ không có chỗ bám.

Làm mini-challenge trước khi đọc case study. Tự implement grep bằng KMP một lần — sau đó case study về ClamAV/Lucene sẽ rõ hơn nhiều vì bạn đã cảm nhận các edge case.

Bài tiếp theo: Naive string matching — vì sao O(n·m) chậm