Thuật toán Aho-Corasick được phát triển bởi Alfred Aho và Margaret Corasick vào năm 1975 cho bài toán tìm kiếm đa mẫu sau:
Với mỗi từ khóa $K_i$, ta có thế áp dụng thuật toán tuyến tính (ví dụ KMP hoặc thuật toán Z) để tìm kiếm sự xuất hiện của $K_i$ trong $T$. Mỗi lần tìm kiếm như vậy ta mất thời gian $O(n + m_i + z_i)$ và do đó, tổng thời gian tìm kiếm $k$ từ khóa là $O(kn + \sum_{i=1}^k (m_i + z_i)) = O(kn + M+ Z)$. Nếu cả $n$ và $k$ đều lớn thì thuật toán này thực sự không hiệu quả. Aho-Corasick dựa trên ý tưởng của thuật toán KMP và máy trạng thái hữu hạn đã phát triển giải thuật với thời gian $O(n + M|\Sigma| + Z)$ trong đó $|\Sigma|$ là số kí tự trong bảng chữ cái sử dụng. Thông thường, $|\Sigma|$ là một hằng số, do đó, thuật toán có thể coi là có thời gian tuyến tính. Trọng tâm bài này là định lý sau:
Máy trạng thái hữu hạn
Trong bài máy trạng thái hữu hạn (finite-state machine - FSM), chúng ta đã làm quen với một máy trạng thái hữu hạn định nghĩa cho một xâu mẫu $P[1,2,\ldots,m]$ và cách xây dựng máy trạng thái đó trong thời gian $O(m)$. Bây giờ chúng ta sẽ mở rộng khái niệm đó cho tập các từ khóa $\mathcal{K} = \{K_1, \ldots, K_k \}$. Mình khuyến khích bạn đọc xem lại bài máy trạng thái hữu hạn trước khi đọc tiếp phần dưới đây.
Một máy trạng thái hữu hạn của tập các từ khóa $\mathcal{K}$ là một đồ thị có hướng $G(V,\vec{E})$ và có các đặc điểm sau:
- Mỗi nút được gán cho một số nguyên duy nhất và được gọi là mỗi trạng thái. Đồ thị $G(V,\vec{E})$ có một nút đặc biệt có trạng thái $0$.
- Có hai loại cạnh trong đồ thị $G$: cạnh khớp (success edge) và cạnh không khớp (failure edge). Mỗi cạnh khớp sẽ có nhãn là một kí tự xuất hiện trong một từ khóa nào đó.
- Tập các cạnh khớp sẽ tạo thành một cây với gốc tại nút $0$. Cây này chính là cây Trie của tập khóa $\mathcal{K}$, hay còn gọi là cây tiền tố (sẽ giải thích ở dưới đây).
- Mỗi nút trong, không phải là gốc, của cây trie này sẽ có một cạnh không khớp tới một nút khác. Các cạnh khớp sẽ được xác định dựa trên luật cạnh không khớp được mô tả sau đây. Cạnh không khớp sẽ có hướng từ nút có độ sâu (trong cây Trie) lớn đến nút có độ sâu nhỏ hơn.
Trong hình dưới đây mô tả một cây Trie với tập từ khóa $ \mathcal{K} = \{he, she, his, hers\}$ (hình (a)) và máy trạng thái hữu hạn tương ứng (hình (b)). Các cạnh màu đỏ là các cạnh không khớp.
Với mỗi nút $i$ của cây Trie, ta gọi xâu tạo bởi các kí tự trên đường đi từ $0$ tới $i$ là nhãn đường đi (path label) của nút $i$. Có thể thấy cây Trie cho một tập các từ khóa có các đặc điểm sau:
- Mỗi từ khóa của $K$ sẽ tương ứng với một nút trong cây trie có nhãn đường đường đi của nút đi là từ khóa đó. Ví dụ mỗi từ khóa trong hình (a) sẽ tương ứng với một nút được tô màu.
- Mỗi nút lá có nhãn đường đi là một từ khóa trong $\mathcal{K}$. Tuy nhiên ngược lại không đúng. Hay nói cách khác, có thể có từ khóa sẽ có nút tương ứng không phải là nút lá. Ví dụ nút được tô màu tương ứng với từ $\mathrm{he}$ không phải là nút lá.
- Hai từ khóa có chung một tiền tố thì tiền tố đó sẽ là nhãn đường đi của tổ tiên chung gần nhất (lowest common ancestor) của hai nút tương ứng với hai từ khóa đó. Ví dụ $\mathrm{his}$ và $\mathrm{hers}$ có chung tiền tố là kí tự $h$ là nhãn đường đi của nút $1$, là tổ tiên chung gần nhất của hai nút tương ứng với hai từ khóa $\mathrm{his}$ và $\mathrm{hers}$.
Các cạnh không khớp trong máy trạng thái được xây dựng dựa trên luật cạnh không khớp sau:
Luật cạnh không khớp: Nút $i$ có một cạnh không khớp tới nút $j$ khi và chỉ nhãn đường đi của nút $j$ là hậu tố dài nhất của nhãn đường đi của nút $i$.
Ví dụ trong hình (b) ở trên, nút $5$ có một cạnh không khớp tới nút $2$ vì nhãn đường đi của $2$ (xâu $\mathrm{he}$) là hậu tố dài nhất của nhãn đường đi của $5$ (xâu $\mathrm{she}$). Bạn đọc có thể kiểm tra luật này với các nút khác.
Xây dựng máy trạng thái hữu hạn
Gọi $s$ là số trạng thái của FSM. Ta sẽ dùng một mảng hai chiều $G[0,\ldots, s-1][1,2,\ldots |\Sigma|]$ để biểu diễn cây Trie, trong đó $G[i] = j$ nếu như nút $j$ là con của nút $i$ và cạnh $i\rightarrow j$ có nhãn là $c$. Ta sẽ xây dựng Trie bằng cách "chèn lần lượt" từng từ khóa của $\mathcal{K}$ vào cây Trie. Ví dụ các bước xây dựng cây Trie cho $\mathcal{K} = \{\mathrm{he}, \mathrm{she}, \mathrm{his}, \mathrm{hers}\}$ được minh họa bởi hình sau:
Giả mã của thuật toán xây dựng cây Trie như sau:
$s\leftarrow$ the number of states
set all entries of $G[0,\ldots, s-1][1,\ldots, |\Sigma|]$ to $-1$
$state \leftarrow 0$
for each key $K[1,2,\ldots,m_i]$ in $\mathcal{K}$
$\ell \leftarrow 0$
$j \leftarrow 1$
while $G[\ell][K[j]] \not= -1$
$\ell \leftarrow G[\ell][K[j]]$ $\ll$ go to the next state in the Trie $\gg$
$j\leftarrow j+1$
while $j \leq m_i$
$state \leftarrow state + 1$
$G[\ell][K[j]] \leftarrow state$ $\ll$ attach the new state to the Trie $\gg$
$j \leftarrow j+1$
$\ell \leftarrow state$
annotate node $\ell$ with key $K[1,\ldots,m_i]$
return $G[0,\ldots,s-1][1,\ldots, |\Sigma|]$
Code C:
// Construct the Trie and stores its structure in a 2D array
// Keys: the set of keywords
// num_keys: the number of keywords in Keys
// num_state: the number of states in the finite state machine, this parameter need not to be exact
// any upper bound of this parameter is ok
// alpb: the size of the alphabet
int **construct_trie(char **Keys, int num_keys, int num_state, int alpb){
int **G;
G = (int **)malloc(num_state*sizeof(int*));
int i = 0;
for(; i < num_state; i++){
G[i] = (int *)malloc(alpb*sizeof(int));
memset(G[i],-1, alpb*sizeof(int));
}
int state = 0;
int j = 1;
for(i = 0; i < num_keys; i++){
int klen = strlen(Keys[i])-1; // -1 since each string is added a space char at the beginning
int ell = 0;
j = 1;
while(G[ell][id(Keys[i][j])] != -1){
ell = G[ell][id(Keys[i][j])];
j ++;
}
while(j <= klen){
state++;
G[ell][id(Keys[i][j])] = state;
j++;
ell = state;
}
printf("key '");
print_char_arr(Keys[i]);
printf("' is added to state %d\n",ell);
L[ell] = Keys[i]; // put the key to the state i
}
nstates = state+1;
printf("the numer of state is %d\n", nstates);
// print out the trie
// for(i = 0; i < nstates; i++){
// for(j = 0; j < alpb; j++){
// printf("%d ", G[i][j]);
// }
// printf("\n");
// }
return G;
}
Sau khi đã xây dựng cây Trie, ta phải xây dựng các cạnh không khớp. Để biểu diễn cạnh không khớp của mỗi nút, ta sẽ sử dụng mảng $F[0,1,\ldots, s-1]$ trong đó $F[i] = j$ nếu có một cạnh không khớp từ nút $i$ đến nút $j$.
Hiển nhiên sử dụng luật cạnh không khớp, ta có thể xây dựng mảng $F[0,\ldots, s-1]$ trong thời gian $O(s^2)$ bằng cách với mỗi nút $i$, ta sẽ duyệt các nút có độ sâu nhỏ hơn $i$ (sử dụng Bread First Search -- BFS) và tìm ra nút thỏa mãn luật cạnh không khớp. Duyệt như vậy mất thời gian $O(s)$ cho mỗi cạnh không khớp, và do đó, tổng thơi gian là $O(s^2)$.
Tuy nhiên, sử dụng ý tưởng quy hoạch động trong xây dựng FSM ở bài trước, ta có thể xây dựng mảng $F[0,\ldots, s-1]$ trong thời gian $O(s)$ như sau. Ta sẽ xây dựng cạnh không khớp cho các nút theo thứ tự tằng dần của chiều sâu (thứ tự BFS). Ban đầu $F[0] = -1$. Giả sử ta đang xây dựng cạnh không khớp cho một nút $i$ ở chiều sâu $d$ (chiều sâu của một nút là khoảng cách từ nút đó đến gốc của cây Trie), và ta đã xác định được cạnh không khớp cho các nút ở chiều sâu nhỏ hơn $d$. Gọi $j_0$ là nút cha của $i$ trong cây Trie và $c_{i}$ là nhãn của cạnh $j_0 \rightarrow i$ trong cây Trie. Xét nút $j_1 = F[j_0]$ (giá trị này đã xác định theo giả thiết quy nạp vì $j_0$ có chiều sâu nhỏ hơn $i$), nhãn của nút $j_1$ là hậu tố của nhãn của nút $j_0$. Do đó, nếu $G[j_1][c_i] \not = -1$, thì ta chỉ việc gán $F[i] = G[j_1][c_i]$ do nhãn của nút $G[j_1][c_i]$ là hậu tố của nhãn của nút $i$ (hình (a)). Nếu không ($G[j_1][c_i] = -1$), ta tiếp tục xét nút $j_2 = F[j_1]$ và lặp lại tương tự, so sánh $G[j_2][c_i]$ với $-1$ (hình (b)). Trường hợp xấu nhất ta sẽ trở lại nút $0$ và lúc này ta sẽ gán $F[i] = 0$.
Giả mã như sau:
$s \leftarrow$ the number of states
$F[0] \leftarrow -1$
for $d \leftarrow 1$ to max depth
for each state $i$ at depth $d$
$j \leftarrow$ parent of $i$ in the Trie
$c_i \leftarrow$ the label of the edge $(j \leftarrow i)$
$j \leftarrow F[j]$
while $G[j][c_i] = -1$ and $j \geq 0$
$j \leftarrow F[j]$
if $j = -1$
$F[i] \leftarrow 0$
else
$F[i] \leftarrow G[j][c_i]$
return $F[0,\ldots,s-1]$
Code C:
// Construct the finite state machine for the set of keywords
// Keys: the set of keywords
// G: the 2D array represents the Trie for the keyword set Keys
// alpb: the size of the alphabet
// num_keys: the number of keys in the keyword set Keys
int *construct_fsm(char **Keys, int **G, int alpb, int num_keys){
int *F;
F = (int *)malloc(nstates*sizeof(int));
F[0] = -1;
enqueue(0);
int i = 0;
while(is_empty() == 0){
int j = dequeue();
int c = 0;
for(; c < alpb; c++){
if(G[j] != -1){
// j is the parent of i
i = G[j];
int k = F[j];
while(k >= 0 && G[k] == -1){
k = F[k];
}
if(k == -1){
F[i] = 0;
}else{
F[i] = G[k];
}
enqueue(i);
}
}
} // end while
printf("the failure array: \n");
for(i = 0; i < nstates; i++){
printf("%d ", F[i]);
}
printf("\n");
return F;
}
Từ các thảo luận ở trên, ta có:
Tìm kiếm với các từ khóa độc lập
Giả sử trong tập từ khóa $K$, không có hai từ khóa $K_i, K_j$ nào sao cho $K_i$ là xâu con của $K_j$. Ta gọi bộ từ khóa $\mathcal{K}$ là bộ từ khóa độc lập. Bộ từ khóa trong ví dụ trên là không độc lập vì từ khóa $\mathrm{he}$ là xâu con của từ khóa $\mathrm{she}$.
Ta có định lý sau:
Ta có thể dễ dàng chứng minh định lý trên bằng phản chứng (và coi như bài tập cho bạn đọc). Định lý trên cho phép chúng ta tìm kiếm trong văn bản $T$ giống như thuật toán KMP. Ta sẽ sử dụng FSM để tìm kiếm trong $T$ như sau. Mỗi bước của thuật toán ta xét một kí tự và một trạng thái của máy FSM. Ban đầu ta xét kí tự $T[0]$ và trạng thái (nút) $0$ của máy FSM. Gọi $T[i]$ và $x$ lần lượt là kí tự hiện tại ta đang xét của $T$ và trạng thái hiện tại ta đang xét của FSM.
- Nếu $x$ là một nút lá của cây Trie, ta sẽ in ra từ khóa tương ứng với nút lá đó và nhảy sang trạng thái $y = F[x]$ và tiếp tục xét $T[i]$ và $y$ trong bước tiếp theo.
- Nếu $x$ không phải là nút lá, có hai trường hợp xảy ra:
- Nếu $G[x][T[i]] \not = -1$, hay có một cạnh trong cây trie với nút cha $x$ có nhãn $T[i]$, ta sẽ đi theo cạnh đó và xét trạng thái $G[x][T[i]]$ và kí tự $T[i+1]$ trong bước tiếp theo.
- Nếu $G[x][T[i]] = -1$, ta sẽ xét $y = F[x]$ và $T[i]$ trong bước tiếp theo.
Giả mã của thuật toán như sau:
$s \leftarrow$ the number of states
$G[0,\ldots,s-1][1,\ldots, |\Sigma|] \leftarrow$ ConstructTrie($\mathcal{K}$)
$F[0,\ldots,s-1]\leftarrow$ ConstructFSM($\mathcal{K},G[0,\ldots,s-1][1,\ldots, |\Sigma|] $)
$j \leftarrow 0$
for $i \leftarrow 1$ to $n$
while $G[j][T[i]] = -1$ and $j \geq 0$
$j \leftarrow F[j]$
if $j = -1$
$j \leftarrow 0$
else
$j \leftarrow G[j][T[i]]$
if $j$ is a leaf
print the keyword of $j$ and its position in $T$
$j \leftarrow F[j]$
Code C:
// search keywords in array Keys in the text T
// Keys: the 2D char array holding keywords
// T: the pointer to the text array
// num_states: the number of states in the finite state machine,
// this parameter need not to be exact, you can input the maximum number of states
// num_keys: the number of keys in the keyword set
// alpb: the size of the alphabet.
void independent_search(char *T, char **Keys, int num_states, int num_keys, int alpb){
int **G = construct_trie(Keys, num_keys, num_states, alpb);
int *F = construct_fsm(Keys,G, alpb, num_keys);
int j = 0;
int i = 1;
int n = strlen(T) - 1; // characters in T are indexed from 1
for(; i <= n; i++){
while(j >= 0 && G[j][id(T[i])] == -1){
j = F[j];
}
if(j == -1) j = 0;
else {
j = G[j][id(T[i])];
if(is_leaf(j, G, alpb)){
printf("the keyword found at state %d is: ", j);
print_char_arr(L[j]);
printf("\n");
int keylen = strlen(L[j])-1; // ignore the first empty character
printf("this keywords is at pos %d of the text\n", i -keylen + 1);
j = F[j];
}
}
}
}
// check whether a state is a leaf of the Trie
// x: the state
// G: the Trie
// alpb:the size of the alphabet
int is_leaf(int x, int **G, int alpb){
int j = 0;
for(; j < alpb; j++){
if(G[x][j] != -1){
return 0;
}
}
return 1;
}
Phân tích thuật toán: Bên cạnh thời gian để xây dưng FSM, thời gian chạy của thuật toán tỉ lệ với phép so sánh bằng ($G[j][T[i]] = -1$) cộng với số phép so sánh không bằng ($G[j][T[i]] \not= -1$) cộng với số lần từ khóa xuất hiện trong văn bản $T$ (mỗi khi $j$ là nút lá). Số lần xuất hiện trong văn bản được cố định là $Z$, do đó ta không cần phân tích thêm nữa về đại lượng này. Mỗi lần $G[j][T[i]] \not= -1$, ta sẽ tăng biển $i$ lên $1$ đơn vị và $j$ sẽ được tăng lên trạng thái ở độ sâu cao hơn. Do đó, có tối đa $O(n + m)$ phép so sánh bằng. Mỗi lần so sánh bằng, $i$ giữ nguyên còn $j$ sẽ được giảm về trạng thái ở độ sâu thấp hơn. Do số lần giảm độ sâu của $j$ không thể vượt quá số lần tăng độ sâu của $j$, do đó, số phép so sánh bằng không thể vượt quá số phép so sánh không bằng. Như vậy, thời gian của thuật toán bằng thời gian để xây dưng FSM + $O(m+n + Z)$. Kết hợp với Lemma 1, ta suy ra Theorem 1 trong trường hợp bộ từ khóa độc lập.
Tìm kiếm với bộ từ khóa bất kì
Nếu bộ từ khóa $\mathcal{K}$ có hai từ khóa $K_i,K_j$ sao cho $K_i$ là xâu con của $K_j$ thì việc tìm kiếm sẽ trở nên khó khăn hơn nhiều. Ví dụ bộ từ khóa gồm 3 từ $\mathcal{K} = \{he, sherd, herdsman\}$ và văn bản $T[1,\ldots,5] = \mathrm{sherdsman}$. Khi tìm kiếm theo thuật toán với khóa độc lập, ta sẽ tìm thấy khóa $\mathrm{sherd}$ đầu tiền, sau đó đi theo cạnh không khớp và tiếp tục tìm được từ khóa $\mathrm{herdsman}$. Mặc dù $\mathrm{he}$ có trong văn bản nhưng ta sẽ không tìm ra nó. trong hình dưới đây, mình lược bỏ một số cạnh không khớp để hình nhìn đỡ rối hơn.
Nếu làm theo từng bước của thuật toán trên, khi ta so sánh kí tự $T[3] = e$ với trạng thái 5 của FSM, ta nên đi tới cạnh không khớp để tìm ra từ $\mathrm{he}$ và sau đó tiếp tuc so sánh $T[4] = r$ với trạng thái 6 của FSM. Tuy nhiên, làm như vậy thì mỗi lần so kí tự, ta lại phải kiểm tra (bằng cách đi theo cạnh không khớp) xem có từ khóa nào xuất hiện trong $T$ hay không. Đó là chưa kể, nếu đi theo cạnh không khớp của nút $j$ tới nút $F[j]$, ta phải tiếp tục đi theo $F[F[j]]$. Ví dụ với bộ $\mathcal{K} = \{he, sherd, herdsman,e\}$ và $T[1,\ldots,5] = \mathrm{sherdsman}$,
Khi ta so sánh $T[3]$ với trạng thái $5$, ta phải đi theo cạnh không khớp tới trạng thái 2 để in ra $\mathrm{he}$ và sau đó tiếp tục đi theo cạnh không khớp của 2 đi tới 14 để in ra $e$, và sau đó mới tiếp tục so sánh $T[4]$ và trạng thái 6.
Để giải quyết vấn đề này, ta sẽ dùng một mảng $L[1,2\ldots,s-1]$ trong đó $L[i]$ là một tập các từ khóa sao cho mỗi từ khóa trong $L[i]$ là hậu tố của nhãn đường đi của trạng thái $i$. Ví dụ trạng thái $5$ sẽ có $L[5] = \{e,he\}$ vì cả hai từ khóa này đều là hậu tố của $\{\mathrm{she}\}$ (là nhãn đường đi của $5$). Trong hình dưới đây, các từ khóa tương ứng với các nút là danh sách $L$ của nút đó. Các nút không có gì là các nút có danh sách $L$ rỗng.
Giả sử ta đã tính được $L[1,2,\ldots,s-1]$ ta chỉ cần thay đổi một chút thủ tục tìm kiếm với bộ từ khóa độc lập ở trên như sau:
$s \leftarrow$ the number of states
$G[0,\ldots,s-1][1,\ldots, |\Sigma|] \leftarrow$ ConstructTrieAndL($\mathcal{K}$)
$F[0,\ldots,s-1]\leftarrow$ ConstructFSMAndL($\mathcal{K},G[0,\ldots,s-1][1,\ldots, |\Sigma|] $)
$j \leftarrow 0$
for $i \leftarrow 1$ to $n$
while $G[j][T[i]] = -1$ and $j \geq 0$
$j \leftarrow F[j]$
if $j = -1$
$j \leftarrow 0$
else
$j \leftarrow G[j][T[i]]$
if $L[j] \not= \emptyset$
print the keywords in $L[j]$ and their positions in $T$
if $j$ is a leaf
$j \leftarrow F[j]$
Code C:
// search keywords in array Keys in the text T
// Keys: the 2D char array holding keywords
// T: the pointer to the text array
// num_states: the number of states in the finite state machine,
// this parameter need not to be exact, you can input the maximum number of states
// num_keys: the number of keys in the keyword set
// alpb: the size of the alphabet.
void multi_pattern_search(char *T, char **Keys, int num_states, int num_keys, int alpb){
int **G = construct_trie_and_L(Keys, num_keys, num_states, alpb);
int *F = construct_fsm_and_L(Keys,G, alpb, num_keys);
int j = 0;
int i = 1;
int n = strlen(T) - 1; // characters in T are indexed from 1
for(; i <= n; i++){
while(j >= 0 && G[j][id(T[i])] == -1){
j = F[j];
}
if(j == -1) j = 0;
else {
j = G[j][id(T[i])];
if(strlen(L[j]) > 0){
printf("the keyword found at state %d is: ", j);
print_char_arr(L[j]);
printf("\n");
int keylen = strlen(L[j])-1; // ignore the first empty character
printf("the last pos of the text containing the keywords is: %d\n", i);
}
if(is_leaf(j, G, alpb)){
j = F[j];
}
}
}
}
// check whether a state is a leaf of the Trie
// x: the state
// G: the Trie
// alpb:the size of the alphabet
int is_leaf(int x, int **G, int alpb){
int j = 0;
for(; j < alpb; j++){
if(G[x][j] != -1){
return 0;
}
}
return 1;
}
Để tính mảng $L[1,2,\ldots,s-1]$, ta sẽ sửa đổi thủ tục ConstructTrie và ConstructFSM như sau:
$s\leftarrow$ the number of states
set all entries of $G[0,\ldots, s-1][1,\ldots, |\Sigma|]$ to $-1$
$state \leftarrow 0$
for each key $K[1,2,\ldots,m_i]$ in $\mathcal{K}$
$\ell \leftarrow 0$
$j \leftarrow 1$
while $G[\ell][K[j]] \not= -1$
$\ell \leftarrow G[\ell][K[j]]$ $\ll$ go to the next state in the Trie $\gg$
$j\leftarrow j+1$
while $j \leq m_i$
$state \leftarrow state + 1$
$G[\ell][K[j]] \leftarrow state$ $\ll$ attach the new state to the Trie $\gg$
$j \leftarrow j+1$
$\ell \leftarrow state$
$L[\ell] \leftarrow \{K[1,\ldots,m_i]\}$ $\ll$ put the keyword to the list $L[\ell] \gg$
return $G[0,\ldots,s-1][1,\ldots, |\Sigma|]$
Code C:
// Construct the Trie and stores its structure in a 2D array
// Keys: the set of keywords
// num_keys: the number of keywords in Keys
// num_state: the number of states in the finite state machine, this parameter need not to be exact
// any upper bound of this parameter is ok
// alpb: the size of the alphabet
int **construct_trie_and_L(char **Keys, int num_keys, int num_state, int alpb){
int **G;
G = (int **)malloc(num_state*sizeof(int*));
int i = 0;
for(; i < num_state; i++){
G[i] = (int *)malloc(alpb*sizeof(int));
memset(G[i],-1, alpb*sizeof(int));
}
int state = 0;
int j = 1;
for(i = 0; i < num_keys; i++){
int klen = strlen(Keys[i])-1; // -1 since each string is added a space char at the beginning
int ell = 0;
j = 1;
while(G[ell][id(Keys[i][j])] != -1){
ell = G[ell][id(Keys[i][j])];
j ++;
}
while(j <= klen){
state++;
G[ell][id(Keys[i][j])] = state;
j++;
ell = state;
}
printf("key '");
print_char_arr(Keys[i]);
printf("' is added to state %d\n",ell);
L[ell] = (char *)malloc(MAX_STR_LEN);
strcat(L[ell], Keys[i]);
}
nstates = state+1;
printf("the numer of state is %d\n", nstates);
// print out the Trie
// for(i = 0; i < nstates; i++){
// for(j = 0; j < alpb; j++){
// printf("%d ", G[i][j]);
// }
// printf("\n");
// }
return G;
}
$s \leftarrow$ the number of states
$F[0] \leftarrow -1$
for $d \leftarrow 1$ to max depth
for each state $i$ at depth $d$
$j \leftarrow$ parent of $i$ in the Trie
$c_i \leftarrow$ the label of the edge $(j \leftarrow i)$
$j \leftarrow F[j]$
while $G[j][c_i] = -1$ and $j \geq 0$
$j \leftarrow F[j]$
if $j = -1$
$F[i] \leftarrow 0$
else
$F[i] \leftarrow G[j][c_i]$
$L[i] \leftarrow L[i] \cup L[F[i]]$
return $F[0,\ldots,s-1]$
Code C:
// Construct the finite state machine for the set of keywords
// Keys: the set of keywords
// G: the 2D array represents the Trie for the keyword set Keys
// alpb: the size of the alphabet
// num_keys: the number of keys in the keyword set Keys
int *construct_fsm_and_L(char **Keys, int **G, int alpb, int num_keys){
int *F;
F = (int *)malloc(nstates*sizeof(int));
F[0] = -1;
enqueue(0);
int i = 0;
while(is_empty() == 0){
int j = dequeue();
int c = 0;
for(; c < alpb; c++){
if(G[j] != -1){
// j is the parent of i
i = G[j];
int k = F[j];
while(k >= 0 && G[k] == -1){
k = F[k];
}
if(k == -1){
F[i] = 0;
if(L[i] == NULL) L[i] = (char*) malloc(MAX_STR_LEN);
}else{
F[i] = G[k];
// union L[i] and L[F[i]]
if(L[i] == NULL) L[i] = (char*) malloc(MAX_STR_LEN);
int len2 = strlen(L[F[i]]);
if(len2 != 0){
strcat(L[i],",");
strcat(L[i], L[F[i]]);
}
}
enqueue(i);
}
}
} // end while
printf("the failure array: \n");
for(i = 0; i < nstates; i++){
printf("%d ", F[i]);
}
printf("\n");
return F;
}
Sử dụng danh sách liên kết, ta có thể thực hiên $L[i] \leftarrow L[i] \cup L[F[i]]$ trong thời gian $O(1)$. Từ đó ta suy ra Theorem 1.
Code của bài viết: aho-corasick with independent keywords, aho-corasick with non-indenpendent keywords.
Tham khảo
[1] Aho, Alfred V., and Margaret J. Corasick. Efficient string matching: an aid to bibliographic search . Communications of the ACM 18.6 (1975): 333-340.
Recent Comments