Pattern matching & String: tổng quan module

TL;DR: Module này dạy năm thuật toán tìm chuỗi: 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 (băm một cửa sổ trượt, mỗi lần trượt chỉ cập nhật chứ không tính lại từ đầu) để mở sang đa mẫu, Z-function duyệt một lần để biết mỗi vị trí trùng bao nhiêu ký tự với phần đầu (tiền tố) của chuỗi, và 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 chạy xong.

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 đối chiếu file tải về của bạn với cơ sở dữ liệu chữ ký virus của nó, 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 phải duyệt lại một lượt cho từng chữ ký, không thể quét real-time nổi. Aho-Corasick xây một automaton (máy trạng thái: mỗi ký tự đọc vào chuyển sang một trạng thái kế) 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 dạy một ý chung hơn thuật toán: cách thoát khỏi worst-case bằng thông tin bạn đã biết. Cụ thể, KMP tận dụng quan hệ tiền tố-hậu tố của pattern, Rabin-Karp tận dụng cửa sổ trượt của hash, Aho-Corasick dùng trie để các pattern chung tiền tố.

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, Z-function, 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) để thấy vì sao quét đồng thời nhiều pattern trong O(n + z) sau khi dựng automaton.

Lộ trình module

Thứ tự bài và lý do

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 (lps, bảng ghi cách dịch pattern khi lệch) là khái niệm cốt lõi, mọi bài sau đều dùng hoặc mở rộng ý 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, ta dùng rolling hash để so hash của từng cửa sổ trượt. Rabin-Karp chạy O(n+m) theo kỳ vọng (trung bình, không đảm bảo chắc chắn như KMP), nhưng mở rộng tự nhiên sang nhiều 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 là lps cho nhiều pattern. ClamAV, nhiều IDS/IPS và bioinformatics tools dùng nó để quét đồng thời rất nhiề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 chỉ thêm một kỹ thuật mở rộng (Boyer-Moore/Horspool, so từ phải sang trái), còn lại cho thấy bạn đã đủ nền để đọc cơ chế của các công cụ chạy thật.

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

Bản đồ khái niệm

Hai câu hỏi là đủ. Trục thứ nhất luôn là số pattern; trục thứ hai đổi theo nhánh: một pattern thì hỏi có chấp nhận xác suất không, nhiều pattern thì hỏi tập pattern có cố định không. Chỉ nhánh Aho-Corasick có chi phí quét text không nhân với số pattern.

Yêu cầu trước

Module này dựa 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 module Tìm kiếm nhanh 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 đó tạo đúng trực giác về việc "lùi con trỏ text". Bỏ qua thì failure function của KMP chỉ còn là công thức, không còn là 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. Nếu chưa quen vẽ bảng trace, ôn lại Bảng trace trướ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. KMP chưa rõ thì Aho-Corasick sẽ không có chỗ bám.

Làm mini-challenge trước khi đọc case study. Tự viết grep bằng KMP một lần, sau đó case study về ClamAV/Lucene sẽ dễ hiểu hơn nhiều vì bạn đã tự vấp qua các edge case.

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