エイホ-コラシックアルゴリズム

このアルゴリズムは、指定されたすべてのキーワードセットのすべての出現箇所を見つけるのに役立ちます。これは一種の辞書照合アルゴリズムです。すべてのキーワードを使用したツリー構造を使用します。ツリーを作成した後、線形時間で検索を行うために、ツリーをオートマトンとして変換しようとします。 Aho-Corasickアルゴリズムには3つの異なるフェーズがあります。

これらはGo-to、Failure、 および出力 。移行段階では、すべてのキーワードを使用してツリーを作成します。次のフェーズまたは失敗フェーズでは、いくつかのキーワードの適切なサフィックスを取得するために、後方遷移を見つけようとします。出力ステージでは、オートマトンのすべての状態「s」について、状態「s」で終わるすべての単語が検索されます。

このアルゴリズムの時間計算量は次のとおりです。O（N + L + Z）、ここでNはテキストの長さ、Lはキーワードの長さ、Zは一致の数です。

入力と出力

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

アルゴリズム

buildTree（patternList、size）

入力- すべてのパターンのリスト、およびリストのサイズ

出力- パターンを見つけるための遷移マップを生成します

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）

入力- 現在の状態と次の状態を決定する次の文字

出力 ： 次の状態

Begin
   answer := presentState
   ch := nextChar

   while goto[answer, ch] = -41, do
      answer := fail[answer]
   done
   return goto[answer, ch]
End

patternSearch（patternList、size、text）

入力- パターンのリスト、リストのサイズ、および本文

出力- パターンが見つかったテキストのインデックス

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

例

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

出力

Word there location: 2
Word any location: 7
Word answer location: 10
Word bye location: 22