0

Aho-Corasickオートマトンを使用して解決する必要のある問題に直面しています。私は一連の単語（「0」または「1」で構成される）-パターンを与えられ、与えられたパターンを含まない無限のテキストを作成できるかどうかを判断する必要があります。解決策は、エイホ-コラシックオートマトンを作成し、状態を一致させずにサイクルを検索することだと思いますが、それを行うための良い方法を提案することはできません。DFSを使用して状態グラフを検索することを考えましたが、それが機能するかどうかはわかりません。実装に問題があります。「1」エッジの状態にあると仮定しますが、その状態はそれによって示されます。エッジは一致としてマークされているため、そのエッジを使用できないため、リンクの失敗を試すことができます（現在の状態には「0」エッジがありません）。ただし、「1」を使用できなかったことも覚えておく必要があります。

誰かが私を訂正して、それを行う方法を教えてもらえますか？私はC++でAho-Corasickを作成しましたが、それが機能すると確信しています。アルゴリズム全体も理解しています。

基本コードは次のとおりです。

class AhoCorasick
{

static const int ALPHABET_SIZE = 2;

struct State
{
  State* edge[ALPHABET_SIZE];
  State* fail;
  State* longestMatchingSuffix;
  //Vector used to remember which pattern matches in this state.
  vector< int > matching;
  short color;

  State()
  {
    for(int i = 0; i < ALPHABET_SIZE; ++i)
      edge[i] = 0;
    color = 0;
  }

  ~State()
  {
    for(int i = 0; i < ALPHABET_SIZE; ++i)
    {
      delete edge[i];
    }
  }
};

private:
  State root;
  vector< int > lenOfPattern;
  bool isFailComputed;

  //Helper function used to traverse state graph.
  State* move(State* curr, char letter)
  {
    while(curr != &root && curr->edge[letter] == 0)
    {
      curr = curr->fail;
    }
    if(curr->edge[letter] != 0)
      curr = curr->edge[letter];
    return curr;
  }

  //Function which computes fail links and longestMatchingSuffix. 
  void computeFailLink()
  {
    queue< State* > Q;
    root.fail = root.longestMatchingSuffix = 0;
    for(int i = 0; i < ALPHABET_SIZE; ++i)
    {
      if(root.edge[i] != 0)
      {
        Q.push(root.edge[i]);
        root.edge[i]->fail = &root;
      }
    }
    while(!Q.empty())
    {
      State* curr = Q.front();
      Q.pop();
      if(!curr->fail->matching.empty())
      {
        curr->longestMatchingSuffix = curr->fail;
      }
      else
      {
        curr->longestMatchingSuffix = curr->fail->longestMatchingSuffix;
      }
      for(int i = 0; i < ALPHABET_SIZE; ++i)
      {
        if(curr->edge[i] != 0)
        {
          Q.push(curr->edge[i]);
          State* state = curr->fail;
          state = move(state, i);
          curr->edge[i]->fail = state;
        }
      }
    }
    isFailComputed = true;
  }

public:
  AhoCorasick()
  {
    isFailComputed = false;
  }

  //Add pattern to automaton.
  //pattern - pointer to pattern, which will be added
  //fun - function which will be used to transform character to 0-based index.
  void addPattern(const char* const pattern, int (*fun) (const char *))
  {
    isFailComputed = false;
    int len = strlen(pattern);
    State* curr = &root;
    const char* pat = pattern;
    for(; *pat; ++pat)
    {
      char tmpPat = fun(pat);
      if(curr->edge[tmpPat] == 0)
      {
        curr = curr->edge[tmpPat] = new State;
      }
      else
      {
        curr = curr->edge[tmpPat];
      }
    }
    lenOfPattern.push_back(len);
    curr->matching.push_back(lenOfPattern.size() - 1);
  }
};

int alphabet01(const char * c)
{
  return *c - '0';
}
4

1 に答える 1

0

私はあなたのコードを調べませんでしたが、非常にシンプルで効率的な実装を知っています.

まず、ディクショナリ サフィックス リンクをツリーに追加します (説明は Wikipedia にあります)。次に、すべてのツリーを調べて、一致するノードと Dict Suffix Links を持つノードを不良ノードとしてマークする必要があります。これらのアクションの説明は明らかです。一致するすべてのノードや、一致する接尾辞を持つノードが必要なわけではありません。

これで、一致するノードのない Aho-Corasick ツリーができました。結果のツリーで DFS アルゴを実行するだけで、必要なものが得られます。

于 2013-03-26T17:56:13.820 に答える