Thuật toán này hữu ích để tìm tất cả các lần xuất hiện của tất cả các tập hợp từ khóa đã cho. Nó là một loại thuật toán đối sánh từ điển. Nó sử dụng cấu trúc cây bằng cách sử dụng tất cả các từ khóa. Sau khi tạo cây, nó sẽ cố gắng chuyển đổi cây như một động cơ tự động để thực hiện việc tìm kiếm trong thời gian tuyến tính. Có ba giai đoạn khác nhau của Thuật toán Aho-Corasick.
Đây là Đi tới, Không đạt, và Đầu ra . Trong giai đoạn bắt đầu, nó làm cho cây bằng cách sử dụng tất cả các từ khóa. Trong giai đoạn tiếp theo hoặc trong Giai đoạn Thất bại, nó cố gắng tìm ra sự chuyển đổi ngược lại để có được một hậu tố thích hợp của một số từ khóa. Trong giai đoạn đầu ra, đối với mọi trạng thái ‘s’ của automaton, nó sẽ tìm thấy tất cả các từ kết thúc ở trạng thái ‘s’.
Độ phức tạp về thời gian của thuật toán này là:O (N + L + Z), trong đó N là độ dài của văn bản, L là độ dài của các từ khóa và Z là một số kết quả phù hợp.
Đầu vào và Đầu ra
Input:
A set of patterns: {their, there, answer, any, bye}
The main string: “isthereanyanswerokgoodbye”
Output:
Word there location: 2
Word any location: 7
Word answer location: 10
Word bye location: 22 Thuật toán
buildTree (patternList, size)
Đầu vào - Danh sách tất cả các mẫu và kích thước của danh sách
Đầu ra - Tạo bản đồ chuyển tiếp để tìm các mẫu
Begin set all elements of output array to 0 set all elements of fail array to -1 set all elements of goto matrix to -1 state := 1 //at first there is only one state. for all patterns ‘i’ in the patternList, do word := patternList[i] present := 0 for all character ‘ch’ of word, do if goto[present, ch] = -1 then goto[present, ch] := state state := state + 1 present:= goto[present, ch] done output[present] := output[present] OR (shift left 1 for i times) done for all type of characters ch, do if goto[0, ch] ≠ 0 then fail[goto[0,ch]] := 0 insert goto[0, ch] into a Queue q. done while q is not empty, do newState := first element of q delete from q. for all possible character ch, do if goto[newState, ch] ≠ -1 then failure := fail[newState] while goto[failure, ch] = -1, do failure := goto[failure, ch] done fail[goto[newState, ch]] = failure output[goto[newState, ch]] :=output[goto[newState,ch]] OR output[failure] insert goto[newState, ch] into q. done done return state End
getNextState (presentState, nextChar)
Đầu vào - trạng thái hiện tại và ký tự tiếp theo để xác định trạng thái tiếp theo
Đầu ra : trạng thái tiếp theo
Begin answer := presentState ch := nextChar while goto[answer, ch] = -41, do answer := fail[answer] done return goto[answer, ch] End
patternSearch (patternList, size, text)
Đầu vào - Danh sách các mẫu, kích thước của danh sách và văn bản chính
Đầu ra - Các chỉ mục của văn bản nơi tìm thấy các mẫu
Begin call buildTree(patternList, size) presentState := 0 for all indexes of the text, do if output[presentState] = 0 ignore next part and go for next iteration for all patterns in the patternList, do if the pattern found using output array, then print the location where pattern is present done done End
Ví dụ
#include <iostream>
#include <queue>
#define MAXS 500 //sum of the length of all patterns
#define MAXC 26 //as 26 letters in alphabet
using namespace std;
int output[MAXS];
int fail[MAXS];
int gotoMat[MAXS][MAXC];
int buildTree(string array[], int size) {
for(int i = 0; i<MAXS; i++)
output[i] = 0; //all element of output is 0
for(int i = 0; i<MAXS; i++)
fail[i] = -1; //all element of failure array is -1
for(int i = 0; i<MAXS; i++)
for(int j = 0; j<MAXC; j++)
gotoMat[i][j] = -1; //all element of goto matrix is -1
int state = 1; //there is only one state
for (int i = 0; i < size; i++) { //make trie structure for all pattern in array
//const string &word = array[i];
string word = array[i];
int presentState = 0;
for (int j = 0; j < word.size(); ++j) { //all pattern is added
int ch = word[j] - 'a';
if (gotoMat[presentState][ch] == -1) //ic ch is not present make new node
gotoMat[presentState][ch] = state++; //increase state
presentState = gotoMat[presentState][ch];
}
output[presentState] |= (1 << i); //current word added in the output
}
for (int ch = 0; ch < MAXC; ++ch) //if ch is not directly connected to root
if (gotoMat[0][ch] == -1)
gotoMat[0][ch] = 0;
queue<int> q;
for (int ch = 0; ch < MAXC; ++ch) { //node goes to previous state when fails
if (gotoMat[0][ch] != 0) {
fail[gotoMat[0][ch]] = 0;
q.push(gotoMat[0][ch]);
}
}
while (q.size()) {
int state = q.front(); //remove front node
q.pop();
for (int ch = 0; ch <= MAXC; ++ch) {
if (gotoMat[state][ch] != -1) { //if goto state is present
int failure = fail[state];
while (gotoMat[failure][ch] == -1) //find deepest node with proper suffix
failure = fail[failure];
failure = gotoMat[failure][ch];
fail[gotoMat[state][ch]] = failure;
output[gotoMat[state][ch]] |= output[failure]; // Merge output values
q.push(gotoMat[state][ch]); //add next level node to the queue
}
}
}
return state;
}
int getNextState(int presentState, char nextChar) {
int answer = presentState;
int ch = nextChar - 'a'; //subtract ascii of 'a'
while (gotoMat[answer][ch] == -1) //if go to is not found, use fail function
answer = fail[answer];
return gotoMat[answer][ch];
}
void patternSearch(string arr[], int size, string text) {
buildTree(arr, size); //make the trie structure
int presentState = 0; //make current state as 0
for (int i = 0; i < text.size(); i++) { //find all occurances of pattern
presentState = getNextState(presentState, text[i]);
if (output[presentState] == 0) //if no match continue;
for (int j = 0; j < size; ++j) { //matching found and print words
if (output[presentState] & (1 << j)) {
cout << "Word " << arr[j] << " location: " << i - arr[j].size() + 1 << endl;
}
}
}
}
int main() {
string arr[] = {"their", "there", "answer", "any", "bye"};
string text = "isthereanyanswerokgoodbye";
int k = sizeof(arr)/sizeof(arr[0]);
patternSearch(arr, k, text);
return 0;
} Đầu ra
Word there location: 2 Word any location: 7 Word answer location: 10 Word bye location: 22