Cấu trúc dữ liệu và Giải thuật Bài 116: Thuật toán Aho-Corasick - Tìm kiếm đồng thời tập nhiều mẫu (Multi-pattern Matching) trong thời gian tuyến tính.

Trong các hệ thống kiểm duyệt nội dung (Content Moderation), tường lửa ứng dụng (WAF), hệ thống phát hiện xâm nhập mạng (IDS như Snort/Suricata), hoặc phần mềm diệt virus (ClamAV), bài toán đặt ra luôn là: Tìm kiếm đồng thời hàng chục nghìn từ khóa (patterns/signatures) trong một luồng văn bản hoặc gói tin mạng liên tục theo thời gian thực.

Nếu áp dụng các thuật toán so khớp chuỗi đơn lẻ như KMP (Knuth-Morris-Pratt) hay Rabin-Karp cho từng mẫu một, với $K$ mẫu có độ dài trung bình $M$ và văn bản độ dài $N$ , tổng thời gian chạy sẽ là $O(K \cdot N)$ . Khi danh sách từ khóa cấm lên tới $50,000$ từ và luồng dữ liệu truyền vào hàng triệu ký tự mỗi giây, cách tiếp cận này sẽ gây tắc nghẽn toàn bộ hệ thống.

Vào năm 1975, Alfred V. Aho và Margaret J. Corasick đã công bố Thuật toán Aho-Corasick. Thuật toán này kết hợp cấu trúc Cây tiền tố (Trie) với cơ chế Liên kết thất bại (Failure Links của KMP) để tạo thành một máy tự động hữu hạn tiền định (DFA). Nhờ đó, việc quét và phát hiện tất cả các mẫu xuất hiện trong văn bản chỉ mất đúng $O(N + M + Z)$ thời gian ( $M$ là tổng độ dài của tất cả các mẫu, $Z$ là số lần các mẫu xuất hiện trong văn bản).

1. Kiến trúc ba tầng của Aho-Corasick

Aho-Corasick vận hành dựa trên ba thành phần cốt lõi:

A. Cây tiền tố (Trie)

Tất cả các từ khóa cần tìm kiếm được nạp vào một cây Trie tiêu chuẩn. Mỗi nút đại diện cho một tiền tố của một hoặc nhiều từ khóa. Nút gốc đại diện cho chuỗi rỗng "".

B. Liên kết thất bại (Failure Links / Suffix Links)

Đây là trái tim của thuật toán. Trong KMP, khi gặp ký tự không khớp, ta nhảy về giá trị trong mảng tiền tố $\pi$ . Trong Aho-Corasick, mỗi nút $u$ trong Trie (đại diện cho chuỗi $S$ ) sở hữu một con trỏ fail:

fail[u] trỏ đến nút đại diện cho hậu tố riêng thực sự dài nhất (longest proper suffix) của $S$ mà cũng xuất hiện trong Trie.
Nếu không có hậu tố nào phù hợp, fail[u] sẽ trỏ về nút gốc (root).
Tất cả các liên kết fail được tính toán thông qua duyệt theo chiều rộng BFS (Breadth-First Search) theo từng tầng của Trie.

C. Liên kết đầu ra (Output / Dictionary Links)

Một chuỗi con hợp lệ có thể nằm lồng bên trong một chuỗi con khác (ví dụ: tìm thấy từ "he" khi đang ở nút đại diện cho "she"). Liên kết đầu ra giúp thu thập toàn bộ các từ khóa kết thúc tại nút hiện tại hoặc kết thúc tại bất kỳ nút nào dọc theo chuỗi liên kết fail mà không cần duyệt ngược thủ công.

2. Quy trình tính toán Failure Links qua BFS

Sau khi dựng xong cây Trie cơ sở:

Khởi tạo hàng đợi (Queue) cho BFS.
Tất cả các nút con trực tiếp của nút gốc (độ sâu 1) được gán fail = root và đẩy vào Queue.
Với mỗi nút cha $u$ lấy ra từ Queue:
- Xét từng nhánh con $v$ ứng với ký tự $c$ :
- Đi theo chuỗi fail của cha $u$ cho đến khi tìm thấy một nút có nhánh rẽ theo ký tự $c$ , hoặc chạm gốc.
- Gán fail[v] trỏ tới nút đích vừa tìm được.
- Gộp danh sách từ khóa hợp lệ từ fail[v] vào danh sách output[v].
- Đẩy $v$ vào Queue để tiếp tục duyệt tầng sâu hơn.

Khi duyệt văn bản $T$ , ta chỉ cần duyệt một lần từ đầu đến cuối ký tự của $T$ . Tại mỗi bước, nếu ký tự tiếp theo có nhánh đi tiếp thì đi xuống; nếu không, nhảy theo con trỏ fail tương tự như dịch chuyển trạng thái máy tự động.

3. Hiện thực hóa Thuật toán Aho-Corasick bằng Golang

Đoạn code dưới đây cài đặt bộ khung Aho-Corasick hoàn chỉnh trong Go, hỗ trợ nạp từ điển mẫu, xây dựng Failure Links bằng BFS và quét tìm vị trí xuất hiện của tất cả các mẫu trong văn bản:

package main

import (
	"fmt"
)

// Node đại diện cho một nút trong Trie / Aho-Corasick Automaton
type Node struct {
	children map[rune]*Node
	fail     *Node
	output   []string // Danh sách các từ khóa kết thúc tại tiền tố này
}

func newNode() *Node {
	return &Node{
		children: make(map[rune]*Node),
		output:   make([]string, 0),
	}
}

// AhoCorasick quản lý toàn bộ máy tự động
type AhoCorasick struct {
	root *Node
}

func NewAhoCorasick() *AhoCorasick {
	return &AhoCorasick{
		root: newNode(),
	}
}

// 1. Thêm một từ khóa vào Trie
func (ac *AhoCorasick) Insert(word string) {
	curr := ac.root
	for _, ch := range word {
		if _, exists := curr.children[ch]; !exists {
			curr.children[ch] = newNode()
		}
		curr = curr.children[ch]
	}
	curr.output = append(curr.output, word)
}

// 2. Xây dựng các liên kết thất bại (Failure Links) bằng BFS
func (ac *AhoCorasick) Build() {
	queue := make([]*Node, 0)

	// Các con trực tiếp của gốc có fail trỏ về gốc
	for _, child := range ac.root.children {
		child.fail = ac.root
		queue = append(queue, child)
	}

	for len(queue) > 0 {
		curr := queue[0]
		queue = queue[1:]

		for ch, child := range curr.children {
			// Tìm fail link cho child
			fallback := curr.fail
			for fallback != nil {
				if target, exists := fallback.children[ch]; exists {
					child.fail = target
					break
				}
				if fallback == ac.root {
					child.fail = ac.root
					break
				}
				fallback = fallback.fail
			}

			// Kế thừa các kết quả khớp từ nút fail
			if child.fail != nil && len(child.fail.output) > 0 {
				child.output = append(child.output, child.fail.output...)
			}

			queue = append(queue, child)
		}
	}
}

// MatchResult lưu trữ thông tin kết quả tìm thấy
type MatchResult struct {
	Word     string
	EndIndex int
}

// 3. Quét văn bản và trả về tất cả các mẫu tìm được cùng vị trí kết thúc
func (ac *AhoCorasick) Search(text string) []MatchResult {
	results := make([]MatchResult, 0)
	curr := ac.root

	for i, ch := range text {
		// Nhảy theo fail link nếu không tìm thấy nhánh ký tự tiếp theo
		for curr != ac.root && curr.children[ch] == nil {
			curr = curr.fail
		}

		if next, exists := curr.children[ch]; exists {
			curr = next
		} else {
			curr = ac.root
		}

		// Thu thập các kết quả khớp tại vị trí hiện tại
		for _, word := range curr.output {
			results = append(results, MatchResult{
				Word:     word,
				EndIndex: i,
			})
		}
	}

	return results
}

func main() {
	ac := NewAhoCorasick()

	// Danh sách các từ khóa cần tìm kiếm đồng thời
	patterns := []string{"he", "she", "his", "hers"}
	for _, p := range patterns {
		ac.Insert(p)
	}

	// Xây dựng Failure Links
	ac.Build()

	text := "ushers"
	matches := ac.Search(text)

	fmt.Printf("Văn bản cần quét: \"%s\"\n", text)
	fmt.Printf("Tìm thấy %d kết quả khớp:\n", len(matches))
	for _, m := range matches {
		startIndex := m.EndIndex - len(m.Word) + 1
		fmt.Printf("- Từ: \"%s\" tại khoảng [%d, %d]\n", m.Word, startIndex, m.EndIndex)
	}
}

4. Ứng dụng thực tế

Hệ thống lọc từ ngữ phản cảm (Profanity Filtering): Quét tin nhắn chat hoặc bình luận trong thời gian thực với kho từ điển hàng chục nghìn từ khóa bị cấm mà không làm tăng độ trễ mạng (Latency).
Hệ thống phòng chống xâm nhập (Network Intrusion Detection - NIDS): So khớp hàng trăm mẫu bytecode mã độc trong các gói tin giao thức TCP/UDP đi qua bộ chuyển mạch.
Khai phá dữ liệu & Gắn thẻ văn bản (Entity Extraction): Tự động nhận diện và gắn thẻ tên riêng, mã chứng khoán hoặc thương hiệu xuất hiện trong các bài báo tài chính.

Aho-Corasick biến bài toán so khớp nhiều mẫu tưởng chừng nặng nề thành một tiến trình quét tuyến tính duy nhất qua máy trạng thái hữu hạn.

cấu trúc dữ liệu