6

aho-corasick 文字列一致アルゴリズムを理解しようとしています。パターンがabcdとであるとしbcます。このような木になります

       []
       /\
    [a]..[b]
    /  :  |
   [b].: [c]
    |     :
   [c].....
    |
   [d]

点線は故障関数を示しています。

ここで、string をフィードするとしますabcd。これはツリーに従って「abcd」の一致を検出しますが、私が知る限り、一致bcは報告されません。アルゴリズムを誤解していますか？

4

3 に答える 3

3

このノードで終了する文字列がある場合は、ノードを really_final としてマークする必要があります。あなたの例では、そのようなノードは「abcd」と「bc」です。その後、ノードの最終状態を計算する必要があります。ノードが本当に最終的な場合、または障害関数によるノードが最終的な場合、ノードは最終的です。したがって、「abcd」、「bc」、および「abc」が最終的なものになります。

言い換えれば、いくつかのパターンがここで終了するか、障害リンクを歩いている現在のノードからいくつかの最終ノードに到達できる場合、ノードは最終です。

于 2011-03-22T18:22:17.213 に答える
3

Artem の答えは正しいですが、おそらくあまり明確ではありません。基本的に行う必要があるのは、新しいノードに到達するたびに、このノードから始まり、障害リンクで構成されるパス全体を調べ、このパスで一致を見つけることです。(これは現在の位置を変更しません)。あなたの例では、パス b->b (一致が見つからない) と c->c (一致bcが見つかった) を調べます。

効率上の理由から、各ノードで「次の一致」の値をキャッシュする必要があることに注意してください。つまり、 node から始まるパスを調べて、いくつかの手順を経uて一致するノードを見つけたv場合、その値を覚えておいてnext_match[u] = vください。そうすれば、次にこのパスを調べなければならないときに、 に 1 回ジャンプすることができますv。

于 2011-03-22T19:36:08.223 に答える
0

AhoCorasick ツリーのセットアップの一部は、次の文字が一致しない場合にツリー内のどこに移動するかを示すポインターをセットアップすることです。たとえば、ツリーを描いたとおりに abcq のシーケンスをたどる場合、abc の位置から bc の位置にジャンプして、bc の下に aq があるかどうかを確認する必要があります。このパスを使用して、別の一連のポインターをセットアップして、abcd で一致を通知した後に bcd で一致を通知するように指示することができます。

それを書いているとき、http: //www.cs.helsinki.fi/~jjaakkol/sgrep.html にある sgrep のソースが非常に役立つことがわかりました。私が覚えている限りでは、sgrep は AhoCorasick だけでなく多くのことを行いますが、その一部として AhoCorsick の実装が含まれています。

于 2011-03-22T18:21:15.963 に答える