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

TL;DR: Bài toán đ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 — tổng quát hoá lps của KMP lên cây trie — bằng BFS một lần. Kết quả là một automaton 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à mọi 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. Nếu có k = 10.000 pattern (như cơ sở dữ liệu chữ ký virus), ghép 10.000 lần và quét 10.000 lần là không thực tế. Aho-Corasick (1975, Bell Labs) hỏi: tại sao không 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í:

Với bảng chữ cái Σ cố định (ASCII = 256), O(M·Σ) = O(M) về hằng số. Trên thực tế, Aho-Corasick build O(M), quét O(n + z) — tuyến tính trên cả hai pha.

2. Bước 1 — Xây Trie từ tập pattern

Trie (prefix tree) là cây trong đó mỗi cạnh biểu diễn một ký tự và mỗi node biểu diễn một tiền tố của pattern nào đó. Các pattern dùng chung tiền tố sẽ dùng chung đường đi từ gốc.

Ví dụ tập pattern {"he", "she", "his", "hers"}:

Dấu ✓ là output node — pattern kết thúc tại đó. Đích failure ghi sẵn trong từng node để mục 3 dưới đây có chỗ đối chiếu; chỗ đáng nhìn nhất là she, node duy nhất mà failure trỏ tới một node có output.

function buildTrie(patterns):
    root <- node mới (id=0)
    for each pattern P trong patterns:
        node <- root
        for each ký tự c trong P:
            if node không có cạnh c:
                node.children[c] <- node mới
            node <- node.children[c]
        node.output.add(P)             -- đánh dấu pattern kết thúc ở đây
    return root
// Time: O(M·Σ)  Space: O(M·Σ)  -- M = tổng độ dài pattern

Thử ngẫmhai chữ ký virus trong bộ dữ liệu của bạn cùng bắt đầu bằng 40 byte giống hệt nhau. Trie ở trên có lưu 40 byte đó hai lần hay chỉ một lần?

3. Bước 2 — Xây failure link bằng BFS

3.1 Failure link là gì?

Khi quét text và đang ở node v của trie, nhưng ký tự tiếp theo không có cạnh từ v — ta thất bại. Câu hỏi: chuyển về node nào để không mất thông tin đã khớp?

Failure link fail[v] trỏ đến node ứng với hậu tố thực sự dài nhất của chuỗi biểu diễn bởi đường đi từ gốc đến v mà cũng là tiền tố của ít nhất một pattern.

Đây chính xác là ý tưởng lps của KMP — nhưng áp lên trie thay vì mảng một chiều.

3.2 Xây bằng BFS theo tầng

Failure link của node tầng 1 luôn là root (không có hậu tố thực sự nào là tiền tố). Với node sâu hơn, dùng failure link của cha để tìm.

function buildFailureLinks(root):
    Queue Q <- rỗng
    -- Tầng 1: failure link trỏ về root
    for each ký tự c và node v = root.children[c]:
        fail[v] <- root
        Q.enqueue(v)
    -- BFS các tầng tiếp
    while Q không rỗng:
        u <- Q.dequeue()
        for each ký tự c và node v = u.children[c]:
            -- Tìm failure link cho v
            f <- fail[u]
            while f != root and f.children[c] không tồn tại:
                f <- fail[f]
            if f.children[c] tồn tại and f.children[c] != v:
                fail[v] <- f.children[c]
            else:
                fail[v] <- root
            -- Gộp output: kế thừa pattern từ failure node
            v.output.addAll(fail[v].output)
            Q.enqueue(v)
// Time: O(M·Σ)  Space: O(M·Σ)

Trực giác gộp output: nếu fail[v] là output node (có pattern kết thúc tại đó), thì khi ta đi đến v trong quá trình quét, cũng cần báo những pattern đó — chúng là hậu tố của chuỗi ta vừa đọc. Gộp vào v.output ngay lúc build để quét text O(1) mỗi node.

3.3 Minh hoạ failure link cho tập {"he", "she", "his", "hers"}

Đối chiếu lại hình trie ở mục 2: bốn node có failure trỏ vào một node khác root là sh → h, she → he, his → s và hers → s. Ba node còn lại (he, hi, her) không có hậu tố nào là tiền tố pattern, nên failure của chúng về thẳng root.

Failure link quan trọng nhất: fail[SHE] = HE — sau khi khớp "she", hậu tố "he" cũng là pattern → SHE.output chứa cả "she" lẫn "he".

4. Bước 3 — Quét text bằng automaton

Sau khi build trie + failure link, quét text T:

function search(root, T):
    node <- root
    matches <- danh sách rỗng
    for i from 0 to T.length-1:
        c <- T[i]
        -- Đi theo failure link cho đến khi tìm được cạnh c hoặc về root
        while node != root and node.children[c] không tồn tại:
            node <- fail[node]
        if node.children[c] tồn tại:
            node <- node.children[c]
        -- Báo mọi pattern kết thúc tại node hiện tại
        for each pattern P trong node.output:
            matches.append((P, i - P.length + 1))  -- (pattern, vị trí bắt đầu)
    return matches
// Time: O(n + z)  Space: O(1) ngoài output  -- z = số match

4.1 Trace T = "ushers", pattern {"he", "she", "his", "hers"}

Một lần quét 6 ký tự, tìm được 3 khớp: she tại 1, he tại 2, hers tại 2.

Bảng trên nén bước i = 4 thành một ô — đó là chỗ dễ trượt qua nhất, vì nó chứa tới ba chuyển. Tách ra thì thấy cơ chế thật: she không có cạnh 'r', tụt một nấc failure về he, ở đó mới có cạnh 'r'. Automaton chưa bao giờ giữ quá một trạng thái, và số pattern không nhân vào chi phí quét.

Thử ngẫmnếu ở một bước automaton phải tụt hai nấc failure liên tiếp trước khi tìm được cạnh khớp, điều đó có phá vỡ đảm bảo O(n) khi quét không?

5. Tại sao tổng độ phức tạp là O(M + n + z)?

Build trie: mỗi ký tự của mỗi pattern tạo đúng một node → O(M).

Build failure link: BFS mỗi node đúng một lần. Vòng while f != root... có thể lặp nhiều lần trên một node, nhưng tổng số bước theo failure link trong toàn bộ BFS bị chặn bởi O(M) (phân tích amortized tương tự KMP — mỗi bước tụt failure link tương ứng rút ngắn chiều sâu, tổng số lần rút bị chặn bởi tổng chiều sâu = O(M)). → O(M).

Quét text: con trỏ i tăng đúng n lần. Mỗi lần tụt failure link làm giảm chiều sâu node hiện tại ít nhất 1, mà chiều sâu chỉ tăng khi i tăng (đi theo cạnh trie) → tổng số lần tụt failure link toàn quá trình quét bị chặn bởi n. Báo output: O(z) lần. → O(n + z).

Tổng: O(M + n + z).

Thử ngẫmClamAV cập nhật thêm 500 chữ ký virus mới mỗi ngày. Theo phân tích ở trên, chi phí build lại toàn bộ automaton có tăng tuyến tính theo tổng số chữ ký hiện có không?

6. Pitfall

Pitfall 1 — Quên gộp output từ failure node khi build

-- SAI: chỉ đánh dấu pattern kết thúc trực tiếp tại node
node.output.add(P)       -- đúng khi build trie
-- ... nhưng không gộp fail[v].output khi build failure link

-- Hệ quả: khi SHE.output = {"she"} nhưng KHÔNG có "he"
-- Quét "ushers" → tìm thấy "she" nhưng BỎ SÓT "he"

-- DUNG: sau khi set fail[v], gộp output ngay
fail[v] <- f.children[c]
v.output.addAll(fail[v].output)   -- kế thừa toàn bộ output từ failure chain

Không gộp output khi build buộc quét text phải đi theo chuỗi failure link để thu output — phá vỡ đảm bảo O(1) mỗi ký tự và dễ bỏ sót match.

Pitfall 2 — BFS không đúng tầng, dẫn đến failure link chưa được tính

-- SAI: dùng DFS thay vì BFS để xây failure link
-- DFS có thể xử lý node v trước khi fail[parent(v)] được tính
-- Hệ quả: fail[v] dựa trên fail[parent] chưa đúng → failure link sai

-- DUNG: BFS đảm bảo xử lý tầng i trước tầng i+1
-- fail[v] = f(fail[parent(v)], ký tự cạnh) -- chỉ đúng khi fail[parent(v)] đã tính

Failure link có tính phụ thuộc theo tầng — node tầng d cần failure link tầng d-1. BFS tự nhiên đảm bảo điều này.

Pitfall 3 — Không xử lý trường hợp failure link về root khi root cũng không có cạnh

-- SAI: vòng while chỉ dừng khi node != root, nhưng root cũng có thể không có cạnh c
while node != root and node.children[c] không tồn tại:
    node <- fail[node]
if node.children[c] tồn tại:
    node <- node.children[c]
-- Thiếu: nếu root cũng không có cạnh c, node ở lại root (đúng)
-- Nhưng code không kiểm tra lại sau vòng while → node có thể là root
-- Và `node.children[c]` tồn tại? Chỉ đúng nếu có pattern bắt đầu bằng c
-- Trường hợp không có → node ở lại root, i tiến. Đây là hành vi ĐÚNG.

-- DUNG: kiểm tra rõ ràng tại root
-- Sau vòng while, nếu node = root và root.children[c] không tồn tại:
-- → ký tự c không bắt đầu pattern nào → giữ nguyên root, tiến i.
-- Code trên đã đúng nhưng cần đọc kỹ: if sau while là conditional, không mandatory.

Lỗi thường gặp là vô tình tạo vòng lặp vô hạn khi fail[root] được set thành root (thay vì null) và vòng while node != root không bao giờ kết thúc.

7. Liên hệ các bài khác

• KMP — failure function: Failure link của Aho-Corasick là failure function lps của KMP mở rộng lên trie nhiều nhánh. Khi trie chỉ có một nhánh (k=1 pattern), Aho-Corasick thu gọn thành đúng KMP. Hiểu KMP sâu là điều kiện tiên quyết để hiểu tại sao BFS xây failure link đúng.
• Z-function: Z-function là giải pháp O(n+m) cho đơn pattern. Khi cần đa mẫu, Z-function không mở rộng tự nhiên — phải chạy k lần O(k·n). Aho-Corasick là câu trả lời cho bài đa mẫu.
• Trie — cấu trúc dữ liệu nền: Bước 1 của Aho-Corasick là xây trie chuẩn. Nếu chưa quen trie, đọc bài đó trước — Aho-Corasick thêm failure link và output link lên trie, không thay đổi cấu trúc trie cơ bản.
• Case study — Lucene & ClamAV: Bài này mổ xẻ cách ClamAV dùng Aho-Corasick quét hàng triệu chữ ký và Lucene tối ưu multi-term search — xem sau khi nắm vững automaton ở bài này.

📚 Deep Dive

Tóm tắt

• Bài toán đa mẫu: KMP × k lần tốn O(k·n) — không thực tế khi k lớn.
• Aho-Corasick xây trie từ toàn bộ pattern O(M), thêm failure link bằng BFS O(M), rồi quét text O(n + z) — tổng O(M + n + z).
• Failure link fail[v] = node ứng với hậu tố dài nhất của chuỗi tại v mà cũng là tiền tố pattern — tổng quát hoá lps KMP lên trie.
• Output link: mỗi node gộp output của failure node để quét text thu đủ match O(1) mỗi ký tự.
• BFS xây failure link đảm bảo tầng d-1 tính trước tầng d — điều kiện cần để failure link đúng.
• Pitfall hay gặp: quên gộp output, dùng DFS thay BFS, failure link root tạo vòng lặp vô hạn.
• Nền tảng của ClamAV, Snort, Hyperscan — bất cứ hệ thống nào cần khớp nhiều pattern trong một lần quét.

Tự kiểm tra

Bài tiếp theo: Mini-challenge — tự viết grep bằng KMP