Trong bài toán này, chúng ta được cung cấp một chuỗi đầu vào và một mảng arr []. Nhiệm vụ của chúng ta là tìm tất cả các lần xuất hiện của tất cả các từ của mảng trong chuỗi. Đối với điều này, chúng tôi sẽ sử dụng Thuật toán Aho-Corasick để tìm kiếm mẫu.
Tìm kiếm chuỗi và mẫu là một việc quan trọng trong lập trình. Và trong lập trình, thuật toán càng tốt thì càng có nhiều ứng dụng thực tế hơn. Thuật toán Aho-Corasick là một thuật toán rất quan trọng và mạnh mẽ giúp tìm kiếm chuỗi dễ dàng . Nó là một loại thuật toán so khớp từ điển, khớp tất cả các chuỗi đồng thời. Thuật toán sử dụng cấu trúc Trie data để triển khai nó.
Cấu trúc dữ liệu ngắn gọn
Trie là một loại cây tiền tố hoặc cây tìm kiếm kỹ thuật số, trong đó mỗi cạnh được gắn nhãn bằng một số chữ cái (mỗi cạnh đi ra có các chữ cái khác nhau) .
Hãy lấy một ví dụ để hiểu Aho-Corasick thuật toán
Đầu vào
string = "bheythisghisanexample"
arr[] = {"hey", "this", "is", "an", “example”} Đầu ra
Word hey starts from 2 Word this starts from 5 Word is starts from 11 Word an starts from 13 Word example starts from 15
Độ phức tạp về thời gian của thuật toán này là O (N + L + Z) , trong đó N =Độ dài đầu vào của chuỗi / văn bản
L =Độ dài của từ khóa (các từ trong mảng)
Z =số trận đấu.
Thực hiện
Thuật toán Aho-Corasick có thể được xây dựng bằng các bước đơn giản sau
-
Xây dựng trie bằng cách sử dụng hàng đợi để chúng tôi có thể đưa từng ký tự vào hàng đợi dưới dạng nút od ‘trie’.
-
Xây dựng liên kết lỗi (liên kết hậu tố) dưới dạng một mảng có thể lưu trữ ký tự tiếp theo và ký tự hiện tại
-
Tạo liên kết đầu ra dưới dạng một mảng để lưu trữ các từ phù hợp
-
Xây dựng một hàm Traverse (FindNextState) để kiểm tra tất cả các ký tự.
Liên kết thất bại (liên kết hậu tố) - Khi chúng ta nhấn một phần của chuỗi mà chúng ta không thể tiếp tục đọc các ký tự, chúng ta quay lại bằng cách đi theo các liên kết hậu tố để cố gắng bảo vệ càng nhiều ngữ cảnh càng tốt. Tóm lại, nó lưu trữ tất cả các cạnh được theo sau khi một ký tự hiện tại không có cạnh trong Trie.
Liên kết đầu ra - Nó luôn trỏ đến nút tương ứng với từ dài nhất có trong trạng thái hiện tại, chúng tôi đảm bảo rằng chúng tôi liên kết tất cả các mẫu lại với nhau bằng cách sử dụng các liên kết đầu ra.
Ví dụ
#include<iostream>
#include <string.h>
#include<algorithm>
#include<queue>
using namespace std;
const int MaxStates = 6 * 50 + 10;
const int MaxChars = 26;
int OccurenceOfWords[MaxStates];
int FF[MaxStates];
int GotoFunction[MaxStates][MaxChars];
int BuildMatchingMachine(const vector<string> &words, char lowestChar = 'a', char highestChar = 'z'){
memset(OccurenceOfWords, 0, sizeof OccurenceOfWords);
memset(FF, -1, sizeof FF);
memset(GotoFunction, -1, sizeof GotoFunction);
int states = 1;
for (int i = 0; i < words.size(); ++i){
const string &keyword = words[i];
int currentState = 0;
for (int j = 0; j < keyword.size(); ++j){
int c = keyword[j] - lowestChar;
if (GotoFunction[currentState][c] == -1){
GotoFunction[currentState][c] = states++;
}
currentState = GotoFunction[currentState][c];
}
OccurenceOfWords[currentState] |= (1 << i);
}
for (int c = 0; c < MaxChars; ++c){
if (GotoFunction[0][c] == -1){
GotoFunction[0][c] = 0;
}
}
queue<int> q;
for (int c = 0; c <= highestChar - lowestChar; ++c){
if (GotoFunction[0][c] != -1 && GotoFunction[0][c] != 0){
FF[GotoFunction[0][c]] = 0;
q.push(GotoFunction[0][c]);
}
}
while (q.size()){
int state = q.front();
q.pop();
for (int c = 0; c <= highestChar - lowestChar; ++c){
if (GotoFunction[state][c] != -1){
int failure = FF[state];
while (GotoFunction[failure][c] == -1){
failure = FF[failure];
}
failure = GotoFunction[failure][c];
FF[GotoFunction[state][c]] = failure;
OccurenceOfWords[GotoFunction[state][c]] |= OccurenceOfWords[failure];
q.push(GotoFunction[state][c]);
}
}
}
return states;
}
int FindNextState(int currentState, char nextInput, char lowestChar = 'a'){
int answer = currentState;
int c = nextInput - lowestChar;
while (GotoFunction[answer][c] == -1){
answer = FF[answer];
}
return GotoFunction[answer][c];
}
vector<int> FindWordCount(string str, vector<string> keywords, char lowestChar = 'a', char highestChar = 'z') {
BuildMatchingMachine(keywords, lowestChar, highestChar);
int currentState = 0;
vector<int> retVal;
for (int i = 0; i < str.size(); ++i){
currentState = FindNextState(currentState, str[i], lowestChar);
if (OccurenceOfWords[currentState] == 0)
continue;
for (int j = 0; j < keywords.size(); ++j){
if (OccurenceOfWords[currentState] & (1 << j)){
retVal.insert(retVal.begin(), i - keywords[j].size() + 1);
}
}
}
return retVal;
}
int main(){
vector<string> keywords;
keywords.push_back("All");
keywords.push_back("she");
keywords.push_back("is");
string str = "Allisheall";
cout<<"The occurrences of all words in the string ' "<<str<<" ' are \n";
vector<int> states = FindWordCount(str, keywords);
for(int i=0; i < keywords.size(); i++){
cout<<"Word "<<keywords.at(i)<<' ';
cout<<"starts at "<<states.at(i)+1<<' ';
cout<<"And ends at "<<states.at(i)+keywords.at(i).size()+1<<endl;
}
} Đầu ra
The occurrences of all words in the string ' Allisheall ' are Word All starts at 5 And ends at 8 Word she starts at 4 And ends at 7 Word is starts at 1 And ends at 3