---
tags:
- Dịch
e_maxx_link: aho_corasick
---
# Thuật toán Aho-Corasick
Thuật toán Aho-Corasick cho phép chúng ta tìm kiếm nhanh chóng nhiều mẫu trong một văn bản.
Tập hợp các chuỗi mẫu còn được gọi là _từ điển_.
Chúng ta sẽ ký hiệu tổng độ dài của các chuỗi cấu thành bằng $m$ và kích thước của bảng chữ cái bằng $k$.
Thuật toán xây dựng một máy trạng thái hữu hạn dựa trên trie trong thời gian $O(m k)$ và sau đó sử dụng nó để xử lý văn bản.
Thuật toán được đề xuất bởi Alfred Aho và Margaret Corasick vào năm 1975.
## Xây dựng trie
<center>
<img src="https://upload.wikimedia.org/wikipedia/commons/e/e2/Trie.svg" width="400px">
<br>
<i>Một trie dựa trên các từ "Java", "Rad", "Rand", "Rau", "Raum" và "Rose".</i>
<br>
<i><a href="https://commons.wikimedia.org/wiki/File:Trie.svg">Hình ảnh</a> do [nd](https://de.wikipedia.org/wiki/Benutzer:Nd) chia sẻ theo giấy phép <a href="https://creativecommons.org/licenses/by-sa/3.0/deed.en">CC BY-SA 3.0</a>.</i>
</center>
Về mặt hình thức, trie là một cây có gốc, trong đó mỗi cạnh của cây được gắn nhãn bằng một chữ cái nào đó
và các cạnh đi ra từ một đỉnh có nhãn khác nhau.
Chúng ta sẽ xác định mỗi đỉnh trong trie bằng chuỗi được tạo thành bởi các nhãn trên đường đi từ gốc đến đỉnh đó.
Mỗi đỉnh cũng sẽ có một cờ $\text{output}$ được đặt
nếu đỉnh tương ứng với một mẫu trong từ điển.
Theo đó, một trie cho một tập hợp các chuỗi là một trie sao cho mỗi đỉnh $\text{output}$ tương ứng với một chuỗi từ tập hợp, và ngược lại, mỗi chuỗi của tập hợp tương ứng với một đỉnh $\text{output}$.
Bây giờ chúng ta mô tả cách xây dựng một trie cho một tập hợp các chuỗi được cho trước trong thời gian tuyến tính so với tổng độ dài của chúng.
Chúng ta giới thiệu một cấu trúc cho các đỉnh của cây:
```{.cpp file=aho_corasick_trie_definition}
const int K = 26;
struct Vertex {
int next[K];
bool output = false;
Vertex() {
fill(begin(next), end(next), -1);
}
};
vector<Vertex> trie(1);
```
Ở đây, chúng ta lưu trữ trie dưới dạng một mảng của $\text{Vertex}$.
Mỗi $\text{Vertex}$ chứa cờ $\text{output}$ và các cạnh dưới dạng một mảng $\text{next}[]$, trong đó $\text{next}[i]$ là chỉ mục của đỉnh mà chúng ta đạt được bằng cách theo sau ký tự $i$, hoặc $-1$ nếu không có cạnh nào như vậy.
Ban đầu, trie chỉ bao gồm một đỉnh - gốc - có chỉ mục $0$.
Bây giờ chúng ta thực hiện một hàm sẽ thêm một chuỗi $s$ vào trie.
Việc thực hiện rất đơn giản:
chúng ta bắt đầu từ nút gốc và miễn là có các cạnh tương ứng với các ký tự của $s$, chúng ta sẽ theo các cạnh đó.
Nếu không có cạnh nào cho một ký tự, chúng ta sẽ tạo một đỉnh mới và kết nối nó với một cạnh.
Ở cuối quá trình, chúng ta đánh dấu đỉnh cuối cùng bằng cờ $\text{output}$.
```{.cpp file=aho_corasick_trie_add}
void add_string(string const& s) {
int v = 0;
for (char ch : s) {
int c = ch - 'a';
if (trie[v].next[c] == -1) {
trie[v].next[c] = trie.size();
trie.emplace_back();
}
v = trie[v].next[c];
}
trie[v].output = true;
}
```
Việc thực hiện này rõ ràng chạy trong thời gian tuyến tính,
và do mỗi đỉnh lưu trữ $k$ liên kết, nó sẽ sử dụng $O(m k)$ bộ nhớ.
Có thể giảm mức tiêu thụ bộ nhớ xuống $O(m)$ bằng cách sử dụng map thay cho mảng trong mỗi đỉnh.
Tuy nhiên, điều này sẽ làm tăng độ phức tạp về thời gian lên $O(m \log k)$.
## Xây dựng tự động
Giả sử chúng ta đã xây dựng một trie cho tập hợp các chuỗi được cho trước.
Bây giờ hãy xem xét nó từ một khía cạnh khác.
Nếu chúng ta xem xét bất kỳ đỉnh nào,
chuỗi tương ứng với nó là tiền tố của một hoặc nhiều chuỗi trong tập hợp, do đó mỗi đỉnh của trie có thể được hiểu là một vị trí trong một hoặc nhiều chuỗi từ tập hợp.
Trên thực tế, các đỉnh của trie có thể được hiểu là các trạng thái trong một **máy tự động xác định hữu hạn**.
Từ bất kỳ trạng thái nào, chúng ta có thể chuyển tiếp - sử dụng một chữ cái đầu vào nào đó - sang các trạng thái khác, nghĩa là, sang một vị trí khác trong tập hợp các chuỗi.
Ví dụ: nếu chỉ có một chuỗi $abc$ trong từ điển, và chúng ta đang đứng tại đỉnh $ab$, thì sử dụng chữ cái $c$, chúng ta có thể đi đến đỉnh $abc$.
Do đó, chúng ta có thể hiểu các cạnh của trie là các chuyển tiếp trong một máy tự động theo chữ cái tương ứng.
Tuy nhiên, trong một máy tự động, chúng ta cần phải có các chuyển tiếp cho mỗi tổ hợp của một trạng thái và một chữ cái.
Nếu chúng ta cố gắng thực hiện một chuyển tiếp bằng cách sử dụng một chữ cái, và không có cạnh nào tương ứng trong trie, thì dù sao chúng ta cũng phải vào một trạng thái nào đó.
Cụ thể hơn, giả sử chúng ta đang ở trong một trạng thái tương ứng với một chuỗi $t$, và chúng ta muốn chuyển tiếp sang một trạng thái khác bằng cách sử dụng ký tự $c$.
Nếu có một cạnh được gắn nhãn bằng ký tự $c$ này, thì chúng ta có thể đơn giản đi qua cạnh này và nhận được đỉnh tương ứng với $t + c$.
Nếu không có cạnh nào như vậy, do chúng ta muốn duy trì bất biến rằng trạng thái hiện tại là khớp một phần dài nhất trong chuỗi được xử lý, chúng ta phải tìm chuỗi dài nhất trong trie là hậu tố chính thức của chuỗi $t$, và thử thực hiện một chuyển tiếp từ đó.
Ví dụ: hãy để trie được xây dựng bởi các chuỗi $ab$ và $bc$, và chúng ta hiện đang ở đỉnh tương ứng với $ab$, đó cũng là một đỉnh $\text{output}$.
Để chuyển tiếp với chữ cái $c$, chúng ta buộc phải đi đến trạng thái tương ứng với chuỗi $b$, và từ đó theo cạnh có chữ cái $c$.
<center>
<img src="https://upload.wikimedia.org/wikipedia/commons/9/90/A_diagram_of_the_Aho-Corasick_string_search_algorithm.svg" width="300px">
<br>
<i>Máy tự động Aho-Corasick dựa trên các từ "a", "ab", "bc", "bca", "c" và "caa".</i>
<br>
<i>Các mũi tên màu xanh lam là liên kết hậu tố, các mũi tên màu xanh lá cây là liên kết đầu cuối.</i>
</center>
Một **liên kết hậu tố** cho một đỉnh $p$ là một cạnh trỏ đến hậu tố chính thức dài nhất của chuỗi tương ứng với đỉnh $p$.
Trường hợp đặc biệt duy nhất là gốc của trie, liên kết hậu tố của nó sẽ trỏ đến chính nó.
Bây giờ chúng ta có thể diễn đạt lại mệnh đề về các chuyển tiếp trong máy tự động như sau:
miễn là không có chuyển tiếp nào từ đỉnh hiện tại của trie bằng cách sử dụng chữ cái hiện tại (hoặc cho đến khi chúng ta đạt đến gốc), chúng ta sẽ theo liên kết hậu tố.
Do đó, chúng ta đã giảm vấn đề xây dựng máy tự động thành vấn đề tìm kiếm liên kết hậu tố cho tất cả các đỉnh của trie.
Tuy nhiên, chúng ta sẽ xây dựng các liên kết hậu tố này, thật kỳ lạ, bằng cách sử dụng các chuyển tiếp được xây dựng trong máy tự động.
Các liên kết hậu tố của đỉnh gốc và tất cả các con trực tiếp của nó trỏ đến đỉnh gốc.
Đối với bất kỳ đỉnh $v$ nào sâu hơn trong cây, chúng ta có thể tính toán liên kết hậu tố như sau:
nếu $p$ là tổ tiên của $v$ với $c$ là chữ cái gắn nhãn cho cạnh từ $p$ đến $v$,
đi đến $p$,
sau đó theo liên kết hậu tố của nó và thực hiện chuyển tiếp với chữ cái $c$ từ đó.
Do đó, vấn đề tìm kiếm các chuyển tiếp đã được giảm xuống vấn đề tìm kiếm các liên kết hậu tố, và vấn đề tìm kiếm các liên kết hậu tố đã được giảm xuống vấn đề tìm kiếm một liên kết hậu tố và một chuyển tiếp, ngoại trừ các đỉnh gần gốc hơn.
Vì vậy, chúng ta có một sự phụ thuộc đệ quy mà chúng ta có thể giải quyết trong thời gian tuyến tính.
Hãy chuyển sang việc thực hiện.
Lưu ý rằng bây giờ chúng ta sẽ lưu trữ tổ tiên $p$ và ký tự $pch$ của cạnh từ $p$ đến $v$ cho mỗi đỉnh $v$.
Ngoài ra, tại mỗi đỉnh, chúng ta sẽ lưu trữ liên kết hậu tố $\text{link}$ (hoặc $-1$ nếu nó chưa được tính toán), và trong mảng $\text{go}[k]$, các chuyển tiếp trong máy cho mỗi ký hiệu (cũng là $-1$ nếu nó chưa được tính toán).
```{.cpp file=aho_corasick_automaton}
const int K = 26;
struct Vertex {
int next[K];
bool output = false;
int p = -1;
char pch;
int link = -1;
int go[K];
Vertex(int p=-1, char ch='$') : p(p), pch(ch) {
fill(begin(next), end(next), -1);
fill(begin(go), end(go), -1);
}
};
vector<Vertex> t(1);
void add_string(string const& s) {
int v = 0;
for (char ch : s) {
int c = ch - 'a';
if (t[v].next[c] == -1) {
t[v].next[c] = t.size();
t.emplace_back(v, ch);
}
v = t[v].next[c];
}
t[v].output = true;
}
int go(int v, char ch);
int get_link(int v) {
if (t[v].link == -1) {
if (v == 0 || t[v].p == 0)
t[v].link = 0;
else
t[v].link = go(get_link(t[v].p), t[v].pch);
}
return t[v].link;
}
int go(int v, char ch) {
int c = ch - 'a';
if (t[v].go[c] == -1) {
if (t[v].next[c] != -1)
t[v].go[c] = t[v].next[c];
else
t[v].go[c] = v == 0 ? 0 : go(get_link(v), ch);
}
return t[v].go[c];
}
```
Dễ thấy rằng nhờ vào việc ghi nhớ các liên kết hậu tố và chuyển tiếp,
tổng thời gian để tìm tất cả các liên kết hậu tố và chuyển tiếp sẽ là tuyến tính.
Để minh họa khái niệm, hãy tham khảo slide số 103 của [slide của Stanford](http://web.stanford.edu/class/archive/cs/cs166/cs166.1166/lectures/02/Slides02.pdf).
### Xây dựng dựa trên BFS
Thay vì tính toán các chuyển tiếp và liên kết hậu tố bằng các cuộc gọi đệ quy đến `go` và `get_link`, chúng ta có thể tính toán chúng từ dưới lên bắt đầu từ gốc.
(Trên thực tế, khi từ điển chỉ bao gồm một chuỗi, chúng ta nhận được thuật toán Knuth-Morris-Pratt quen thuộc.)
Phương pháp này sẽ có một số lợi thế so với phương pháp được mô tả ở trên vì, thay vì tổng độ dài $m$, thời gian chạy của nó chỉ phụ thuộc vào số lượng đỉnh $n$ trong trie. Hơn nữa, có thể thích nghi nó cho bảng chữ cái lớn bằng cách sử dụng cấu trúc dữ liệu mảng liên tục, do đó làm cho thời gian xây dựng là $O(n \log k)$ thay vì $O(mk)$, đây là một cải tiến đáng kể khi $m$ có thể lên tới $n^2$.
Chúng ta có thể lập luận bằng quy nạp bằng cách sử dụng thực tế là BFS từ gốc duyệt các đỉnh theo thứ tự tăng dần độ dài.
Chúng ta có thể giả sử rằng khi chúng ta ở trong một đỉnh $v$, liên kết hậu tố $u = link[v]$ của nó đã được tính toán thành công, và đối với tất cả các đỉnh có độ dài ngắn hơn, các chuyển tiếp từ chúng cũng đã được tính toán đầy đủ.
Giả sử rằng tại thời điểm này chúng ta đứng trong một đỉnh $v$ và xem xét một ký tự $c$. Về cơ bản, chúng ta có hai trường hợp:
1. $go[v][c] = -1$. Trong trường hợp này, chúng ta có thể gán $go[v][c] = go[u][c]$, điều này đã được biết đến theo giả thuyết quy nạp;
2. $go[v][c] = w \neq -1$. Trong trường hợp này, chúng ta có thể gán $link[w] = go[u][c]$.
Bằng cách này, chúng ta dành $O(1)$ thời gian cho mỗi cặp đỉnh và ký tự, làm cho thời gian chạy là $O(mk)$. Chi phí chính ở đây là chúng ta sao chép rất nhiều chuyển tiếp từ $u$ trong trường hợp đầu tiên, trong khi các chuyển tiếp của trường hợp thứ hai tạo thành trie và cộng dồn thành $m$ trên tất cả các đỉnh. Để tránh sao chép $go[u][c]$, chúng ta có thể sử dụng cấu trúc dữ liệu mảng liên tục, sử dụng mà ban đầu chúng ta sao chép $go[u]$ vào $go[v]$ và sau đó chỉ cập nhật các giá trị cho các ký tự mà chuyển tiếp sẽ khác. Điều này dẫn đến thuật toán $O(m \log k)$.
## Ứng dụng
### Tìm tất cả các chuỗi từ một tập hợp đã cho trong một văn bản
Chúng ta được cung cấp một tập hợp các chuỗi và một văn bản.
Chúng ta phải in tất cả các lần xuất hiện của tất cả các chuỗi từ tập hợp trong văn bản đã cho trong $O(\text{len} + \text{ans})$, trong đó $\text{len}$ là độ dài của văn bản và $\text{ans}$ là kích thước của câu trả lời.
Chúng ta xây dựng một máy tự động cho tập hợp các chuỗi này.
Bây giờ chúng ta sẽ xử lý văn bản từng chữ cái một bằng cách sử dụng máy tự động,
bắt đầu từ gốc của trie.
Nếu chúng ta ở bất kỳ thời điểm nào ở trạng thái $v$, và chữ cái tiếp theo là $c$, thì chúng ta chuyển tiếp sang trạng thái tiếp theo với $\text{go}(v, c)$, do đó hoặc tăng độ dài của chuỗi khớp hiện tại lên $1$, hoặc giảm nó bằng cách theo sau một liên kết hậu tố.
Làm cách nào chúng ta có thể tìm ra đối với một trạng thái $v$, nếu có bất kỳ khớp nào với các chuỗi cho tập hợp?
Đầu tiên, rõ ràng là nếu chúng ta đứng trên một đỉnh $\text{output}$, thì chuỗi tương ứng với đỉnh kết thúc tại vị trí này trong văn bản.
Tuy nhiên, đây không phải là trường hợp duy nhất để đạt được một khớp:
nếu chúng ta có thể đạt được một hoặc nhiều đỉnh $\text{output}$ bằng cách di chuyển dọc theo các liên kết hậu tố, thì cũng sẽ có một khớp tương ứng với mỗi đỉnh $\text{output}$ được tìm thấy.
Một ví dụ đơn giản minh họa cho tình huống này có thể được tạo ra bằng cách sử dụng tập hợp các chuỗi $\{dabce, abc, bc\}$ và văn bản $dabc$.
Do đó, nếu chúng ta lưu trữ trong mỗi đỉnh $\text{output}$ chỉ mục của chuỗi tương ứng với nó (hoặc danh sách các chỉ mục nếu các chuỗi trùng lặp xuất hiện trong tập hợp), thì chúng ta có thể tìm thấy trong thời gian $O(n)$ các chỉ mục của tất cả các chuỗi khớp với trạng thái hiện tại, bằng cách đơn giản theo sau các liên kết hậu tố từ đỉnh hiện tại đến gốc.
Đây không phải là giải pháp hiệu quả nhất, vì điều này dẫn đến độ phức tạp $O(n ~ \text{len})$ tổng thể.
Tuy nhiên, điều này có thể được tối ưu hóa bằng cách tính toán và lưu trữ đỉnh $\text{output}$ gần nhất có thể truy cập được bằng cách sử dụng các liên kết hậu tố (điều này đôi khi được gọi là **liên kết thoát**).
Giá trị này chúng ta có thể tính toán lười biếng trong thời gian tuyến tính.
Do đó, đối với mỗi đỉnh, chúng ta có thể tiến lên trong thời gian $O(1)$ đến đỉnh được đánh dấu tiếp theo trong đường dẫn liên kết hậu tố, nghĩa là, đến khớp tiếp theo.
Do đó, đối với mỗi khớp, chúng ta dành $O(1)$ thời gian, và do đó chúng ta đạt được độ phức tạp $O(\text{len} + \text{ans})$.
Nếu bạn chỉ muốn đếm các lần xuất hiện thay vì tìm các chỉ mục, bạn có thể tính toán số lượng đỉnh được đánh dấu trong đường dẫn liên kết hậu tố cho mỗi đỉnh $v$.
Điều này có thể được tính toán trong thời gian $O(n)$ tổng thể.
Do đó, chúng ta có thể cộng dồn tất cả các khớp trong $O(\text{len})$.
### Tìm chuỗi nhỏ nhất về mặt từ vựng có độ dài đã cho không khớp với bất kỳ chuỗi nào đã cho
Một tập hợp các chuỗi và độ dài $L$ được cho trước.
Chúng ta phải tìm một chuỗi có độ dài $L$, không chứa bất kỳ chuỗi nào trong số đó, và dẫn xuất chuỗi nhỏ nhất về mặt từ vựng trong số các chuỗi đó.
Chúng ta có thể xây dựng máy tự động cho tập hợp các chuỗi.
Hãy nhớ rằng các đỉnh $\text{output}$ là các trạng thái mà chúng ta có một khớp với một chuỗi từ tập hợp.
Do trong nhiệm vụ này, chúng ta phải tránh các khớp, chúng ta không được phép vào các trạng thái đó.
Mặt khác, chúng ta có thể vào tất cả các đỉnh khác.
Do đó, chúng ta xóa tất cả các đỉnh "xấu" khỏi máy, và trong biểu đồ còn lại của máy tự động, chúng ta tìm đường dẫn nhỏ nhất về mặt từ vựng có độ dài $L$.
Nhiệm vụ này có thể được giải quyết trong $O(L)$ bằng cách sử dụng ví dụ [tìm kiếm theo chiều sâu](../graph/depth-first-search.md).
### Tìm chuỗi ngắn nhất chứa tất cả các chuỗi đã cho
Ở đây, chúng ta sử dụng cùng một ý tưởng.
Đối với mỗi đỉnh, chúng ta lưu trữ một mặt nạ biểu thị các chuỗi khớp với trạng thái đó.
Sau đó, vấn đề có thể được diễn đạt lại như sau:
ban đầu ở trạng thái $(v = \text{root},~ \text{mask} = 0)$, chúng ta muốn đạt đến trạng thái $(v,~ \text{mask} = 2^n - 1)$, trong đó $n$ là số lượng chuỗi trong tập hợp.
Khi chúng ta chuyển tiếp từ một trạng thái sang trạng thái khác bằng cách sử dụng một chữ cái, chúng ta sẽ cập nhật mặt nạ cho phù hợp.
Bằng cách chạy [tìm kiếm theo chiều rộng](../graph/breadth-first-search.md), chúng ta có thể tìm đường dẫn đến trạng thái $(v,~ \text{mask} = 2^n - 1)$ có độ dài nhỏ nhất.
### Tìm chuỗi nhỏ nhất về mặt từ vựng có độ dài $L$ chứa $k$ chuỗi {data-toc-label="Tìm chuỗi nhỏ nhất về mặt từ vựng có độ dài L chứa k chuỗi"}
Giống như trong vấn đề trước, chúng ta tính toán cho mỗi đỉnh số lượng khớp tương ứng với nó (đó là số lượng đỉnh được đánh dấu có thể truy cập được bằng cách sử dụng các liên kết hậu tố).
Chúng ta diễn đạt lại vấn đề: trạng thái hiện tại được xác định bởi một bộ ba số $(v,~ \text{len},~ \text{cnt})$, và chúng ta muốn đạt được từ trạng thái $(\text{root},~ 0,~ 0)$ đến trạng thái $(v,~ L,~ k)$, trong đó $v$ có thể là bất kỳ đỉnh nào.
Do đó, chúng ta có thể tìm đường dẫn như vậy bằng cách sử dụng tìm kiếm theo chiều sâu (và nếu tìm kiếm xem xét các cạnh theo thứ tự tự nhiên của chúng, thì đường dẫn được tìm thấy sẽ tự động là nhỏ nhất về mặt từ vựng).
## Bài toán
- [UVA #11590 - Tra cứu Tiền tố](https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=2637)
- [UVA #11171 - Tin nhắn SMS](https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=2112)
- [UVA #10679 - Tôi yêu chuỗi!!](https://uva.onlinejudge.org/index.php?option=onlinejudge&page=show_problem&problem=1620)
- [Codeforces - x-prime Chuỗi con](https://codeforces.com/problemset/problem/1400/F)
- [Codeforces - Tần số của Chuỗi](http://codeforces.com/problemset/problem/963/D)
- [CodeChef - TWOSTRS](https://www.codechef.com/MAY20A/problems/TWOSTRS)
## Tham khảo
- [CS166 của Stanford - Máy tự động Aho-Corasick](http://web.stanford.edu/class/archive/cs/cs166/cs166.1166/lectures/02/Slides02.pdf) ([Tóm tắt](http://web.stanford.edu/class/archive/cs/cs166/cs166.1166/lectures/02/Small02.pdf))
Sign in with Wallet
Connect another wallet