C++でのパターン検索のためのAho-Corasickアルゴリズム

この問題では、入力文字列と配列arr[]が与えられます。私たちのタスクは、文字列内の配列のすべての単語のすべての出現を見つけることです。このために、パターン検索にAho-Corasickアルゴリズムを使用します。

文字列とパターンの検索は、プログラミングにおいて重要なことです。また、プログラミングでは、アルゴリズムが優れているほど、より実用的な用途に使用できます。 Aho-Corasickアルゴリズム は文字列検索を簡単にする非常に重要で強力なアルゴリズムです 。これは一種の辞書照合アルゴリズムであり、すべての文字列を同時に照合します。アルゴリズムはTrieデータ構造を使用します その実装のために。

トライデータ構造

Trieは一種のプレフィックスツリーまたはデジタル検索ツリーであり、各エッジは何らかの文字でラベル付けされています（各出力エッジは異なる文字を持っています） 。

例を挙げてエイホ-コラシックを理解しましょう アルゴリズム

入力

string = "bheythisghisanexample"
arr[] = {"hey", "this", "is", "an", “example”}

出力

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

このアルゴリズムの時間計算量はO（N + L + Z）です。 、ここで、N=文字列/テキストの入力の長さ

L =キーワードの長さ（配列内の単語）

Z=一致数。

実装

Aho-Corasickアルゴリズムは、これらの簡単な手順で構築できます

• キューを使用してトライを構築し、キュー内の各文字を「トライ」のノードとしてポップできるようにします。

• 失敗リンク（サフィックスリンク）を、次の現在の文字を格納できる配列として構築します

• 一致する単語を格納するための配列として出力リンクを構築します

• トラバース関数（FindNextState）を作成して、すべての文字をチェックします。

障害リンク（サフィックスリンク） −文字列の一部をヒットして文字を読み続けることができない場合は、サフィックスリンクをたどってフォールバックし、可能な限り多くのコンテキストを保持しようとします。簡単に言うと、現在のキャラクターのトライにエッジがない場合に続くすべてのエッジが格納されます。

出力リンク −常に現在の状態で存在する最長の単語に対応するノードを指しているため、出力リンクを使用してすべてのパターンを確実に連鎖させます。

例

#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;
   }
}

出力

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