vi
new
0
Avatar
Huy Hoàng @hhoang
14.0K 201 1.5K
Đã đăng vào khoảng 3 giờ trước 7 phút đọc
6

Cấu trúc dữ liệu và Giải thuật Bài 76: Thuật toán Aho-Corasick - Cỗ máy tìm kiếm đa mẫu (Multi-pattern String Matching).

Thuật toán KMP (Bài 53) là một kiệt tác khi bạn cần tìm kiếm một từ khóa duy nhất trong một văn bản khổng lồ. Tuy nhiên, các hệ thống backend thực tế thường đối mặt với một bài toán khắc nghiệt hơn rất nhiều: Tìm kiếm hàng ngàn từ khóa cùng lúc trên một luồng dữ liệu (Stream) đang chảy qua hệ thống.

Hãy tưởng tượng luồng đánh giá sản phẩm tại Hasaki. Hệ thống cần quét nội dung bình luận của người dùng để lọc ra 10,000 từ ngữ tục tĩu (Profanity Filter) hoặc phát hiện các mẫu tấn công SQL Injection (WAF). Nếu sử dụng KMP để quét qua từng từ khóa một, độ phức tạp sẽ là O(K⋅N)O(K \cdot N) (với KK là số lượng từ khóa). CPU sẽ bị vắt kiệt ngay lập tức.

Năm 1975, Alfred V. Aho và Margaret J. Corasick (hai nhà nghiên cứu tại Bell Labs) đã phát minh ra một cỗ máy trạng thái hữu hạn có khả năng gộp toàn bộ 10,000 từ khóa đó vào thành một cấu trúc duy nhất. Hệ thống chỉ cần duyệt qua văn bản đúng một lần duy nhất, đạt tốc độ O(N+M+Z)O(N + M + Z) (với MM là tổng độ dài các từ khóa, ZZ là số lượng kết quả tìm thấy). Thuật toán này mang tên Aho-Corasick, linh hồn của mọi công cụ tìm kiếm toàn văn bản như grep hay các hệ thống phát hiện xâm nhập mạng (Snort/Suricata).

1. Giải phẫu Aho-Corasick: Trie kết hợp Automaton

Thuật toán Aho-Corasick được xây dựng dựa trên sự nâng cấp của Cây tiền tố (Trie - Bài 52). Cấu trúc của nó bao gồm 3 thành phần liên kết chặt chẽ:

  1. Cây Trie (Trie / Goto Function): Tiền xử lý toàn bộ tập hợp từ khóa cần tìm (Dictionary) và nhét chúng vào một cây Trie. Quá trình này nhóm các tiền tố chung lại với nhau để tiết kiệm bộ nhớ.

  2. Liên kết thất bại (Failure Link / Fail Function): Tương tự như mảng lps của KMP, nhưng áp dụng trên cây. Khi thuật toán đang khớp văn bản theo một nhánh của Trie mà bị sai (ký tự tiếp theo không khớp), thay vì quay lại gốc, Failure Link sẽ chỉ cho hệ thống nhảy ngay sang một Node khác trên cây. Node này đại diện cho hậu tố thực sự dài nhất của chuỗi hiện tại mà cũng là tiền tố của một từ khóa khác.

  3. Liên kết đầu ra (Dictionary Link / Output Link): Đây là bẫy logic quan trọng nhất. Giả sử từ điển có từ "she" và "he". Khi bạn duyệt đến chữ "e" trong nhánh "she", bạn không chỉ tìm thấy "she", mà còn ngầm tìm thấy "he" (vì "he" là hậu tố của "she"). Output Link tạo ra một đường cao tốc chỉ thẳng đến các từ khóa bị lồng ghép bên trong nhau, giúp hệ thống không bỏ sót bất kỳ kết quả nào.

2. Quá trình xây dựng Cỗ máy Aho-Corasick

  • Bước 1: Dựng Cây Trie từ danh sách từ khóa.

  • Bước 2: Sử dụng thuật toán Duyệt theo chiều rộng (BFS) để thiết lập các Cạnh Thất bại (Fail) và Cạnh Đầu ra (Output) cho từng Node.

    • Các Node ở độ sâu 1 (con trực tiếp của Root) luôn có Fail Link trỏ về Root.

    • Với các Node sâu hơn, để tìm Fail Link cho đỉnh con vv (nối với cha uu bằng ký tự cc), ta đi theo Fail Link của uu cho đến khi tìm thấy một Node có nhánh đi xuống bằng ký tự cc.

3. Triển khai Thuật toán Aho-Corasick bằng Golang

Dưới đây là thiết kế chuẩn mực của cỗ máy Aho-Corasick, tối ưu cho xử lý chuỗi UTF-8 (hỗ trợ Tiếng Việt) bằng cách sử dụng map[rune]*ACNode:

Go

package main

import (
	"fmt"
)

// Cấu trúc Node của cỗ máy trạng thái
type ACNode struct {
	children    map[rune]*ACNode // Goto function
	fail        *ACNode          // Failure link
	output      *ACNode          // Dictionary/Output link (trỏ tới node kết thúc từ khóa gần nhất)
	wordIndices []int            // Lưu vị trí (index) của từ khóa nếu node này là điểm kết thúc
}

func newACNode() *ACNode {
	return &ACNode{
		children:    make(map[rune]*ACNode),
		wordIndices: make([]int, 0),
	}
}

type AhoCorasick struct {
	root  *ACNode
	words []string
}

func NewAhoCorasick() *AhoCorasick {
	return &AhoCorasick{
		root:  newACNode(),
		words: make([]string, 0),
	}
}

// 1. Thêm từ khóa vào Cây Trie
func (ac *AhoCorasick) AddWord(word string) {
	node := ac.root
	for _, ch := range word {
		if _, exists := node.children[ch]; !exists {
			node.children[ch] = newACNode()
		}
		node = node.children[ch]
	}
	node.wordIndices = append(node.wordIndices, len(ac.words))
	ac.words = append(ac.words, word)
}

// 2. Xây dựng Liên kết thất bại (Failure Links) bằng BFS
func (ac *AhoCorasick) Build() {
	queue := []*ACNode{}

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

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

		for ch, v := range u.children {
			// Đi tìm fail link cho node v
			failNode := u.fail
			for failNode != nil && failNode.children[ch] == nil {
				failNode = failNode.fail
			}

			if failNode == nil {
				v.fail = ac.root
			} else {
				v.fail = failNode.children[ch]
			}

			// Thiết lập Output link: Nếu v.fail kết thúc một từ khóa, output của v trỏ tới v.fail
			// Ngược lại, kế thừa output từ v.fail
			if len(v.fail.wordIndices) > 0 {
				v.output = v.fail
			} else {
				v.output = v.fail.output
			}

			queue = append(queue, v)
		}
	}
}

// Result lưu trữ thông tin từ khóa tìm được
type Match struct {
	Keyword string
	EndPos  int
}

// 3. Quét văn bản và đối chiếu (O(N + Z))
func (ac *AhoCorasick) Search(text string) []Match {
	var results []Match
	node := ac.root

	for i, ch := range text {
		// Nhảy theo fail link nếu ký tự hiện tại không khớp
		for node != nil && node.children[ch] == nil {
			node = node.fail
		}

		if node == nil {
			node = ac.root
			continue
		}

		// Đi xuống nhánh hợp lệ
		node = node.children[ch]

		// Thu thập tất cả các kết quả (cả tại node hiện tại và thông qua output link)
		temp := node
		for temp != nil {
			for _, wordIdx := range temp.wordIndices {
				results = append(results, Match{
					Keyword: ac.words[wordIdx],
					EndPos:  i, // Vị trí kết thúc (theo rune index)
				})
			}
			temp = temp.output // Dò ngược theo dictionary link để gom các chuỗi lồng nhau
		}
	}
	return results
}

func main() {
	ac := NewAhoCorasick()
	// Thêm danh sách từ khóa bậy hoặc nhạy cảm cần lọc
	ac.AddWord("he")
	ac.AddWord("she")
	ac.AddWord("his")
	ac.AddWord("hers")

	ac.Build()

	text := "ushers"
	fmt.Printf("Văn bản gốc: %s\n", text)
	
	matches := ac.Search(text)
	for _, m := range matches {
		fmt.Printf("- Bắt được từ khóa: '%s' (Kết thúc tại index %d)\n", m.Keyword, m.EndPos)
	}
	// Mong đợi: 'she' (end: 2), 'he' (end: 2), 'hers' (end: 5)
}

4. Phân tích Hiệu năng (Big-O)

  • Thời gian Xây dựng (Preprocessing): O(M⋅Σ)O(M \cdot \Sigma) (với MM là tổng độ dài của tất cả từ khóa, Σ\Sigma là bảng chữ cái). BFS đi qua mỗi Node một lần, thời gian khởi tạo cỗ máy cực kỳ nhanh và chỉ cần làm một lần duy nhất lúc khởi động server.

  • Thời gian Truy vấn (Query Time): O(N+Z)O(N + Z) (với NN là độ dài đoạn văn bản cần quét, ZZ là số lượng kết quả tìm thấy). Bất kể số lượng từ khóa trong từ điển là 10 hay 1,000,000, tốc độ quét ngang qua văn bản là không đổi.

  • Không gian (Space Complexity): O(M⋅Σ)O(M \cdot \Sigma) để lưu trữ cây Trie và các con trỏ trạng thái. Nếu dùng map trong Go, không gian được tối ưu cực tốt cho các luồng dữ liệu Unicode/UTF-8.

5. Ứng dụng Thực tế trong Kỹ thuật Phần mềm

Aho-Corasick là hạt nhân của các hệ thống xử lý nội dung luồng dữ liệu tốc độ cao:

  • Tường lửa Ứng dụng Web (WAF): Khi các Nginx Controller hoặc Envoy Proxy quét các gói tin HTTP payload đi vào hệ thống, thuật toán Aho-Corasick được sử dụng để đối chiếu đồng thời hàng ngàn signature độc hại (XSS, SQLi payloads) với độ trễ xấp xỉ bằng không.

  • Kiểm duyệt Nội dung (Content Moderation): Các hệ thống Chat thời gian thực hoặc kiểm duyệt bình luận sử dụng cỗ máy này để load bảng từ khóa bậy (Profanity list) khổng lồ lên RAM và lọc trực tiếp từng tin nhắn bay qua WebSocket.

  • Tìm kiếm và thay thế Hàng loạt (Batch Replace): Khi xử lý file log khổng lồ bằng các lệnh như fgrep trên Linux, Aho-Corasick hoạt động ngầm để tìm ra mọi dòng chứa tập hợp các từ khóa theo dõi.

Chúng ta đã sở hữu vũ khí mạnh nhất trong mảng tìm kiếm văn bản tĩnh và luồng tĩnh. Khi dữ liệu bùng nổ sang không gian đa chiều — nơi không chỉ có text mà có Tọa độ, Vị trí địa lý, hay Vector khoảng cách đa biến, chúng ta phải chuyển sang một cấu trúc cây hoàn toàn mới của hệ hình học tọa độ.

cấu trúc dữ liệu

All rights reserved

Mục lục


Viblo
Hãy đăng ký một tài khoản Viblo để nhận được nhiều bài viết thú vị hơn.
Đăng kí