4

受信したそれほど長くないテキストを検索して、特定の文字列が出現するかどうかを調べる必要があります。文字列はセッション全体で一定であり、多くはありません (~10)。さらに単純化すると、どの文字列も他の文字列には含まれません。

現在、とのブースト正規表現マッチングを使用していstr1 | str2 | ...ます。このタスクのパフォーマンスは重要なので、改善できないかと考えています。ブースト担当者よりも優れたプログラミングができるわけではありませんが、専用の実装は一般的な実装よりも効率的です。

文字列は長期間にわたって一定のままであるため、状態遷移表のようなデータ構造を事前に構築する余裕があります。

たとえば、文字列がabcx、 、bcyおよびczであり、これまで読んだabcことがある場合、 を意味する結合状態にあるはずyou're either 3 chars into string 1, 2 chars into string 2 or 1 char into string 1です。x次に、次を読み取るとstring 1 matched状態などに移動し、以外の文字xyzは初期状態に移動し、に戻る必要はありませんb。

どんなアイデアや参考文献も大歓迎です。

4

8 に答える 8

6

Aho–Corasick 文字列マッチング アルゴリズムをチェックしてください。

于 2010-08-24T20:31:14.207 に答える
4

Suffix Treeを見てください。

于 2010-08-24T19:48:43.763 に答える
1

私は答えを見てきましたが、どれも非常に明確に見えません...そしてほとんどの場合、いくつかのリンクに要約されます。

ここで私が興味をそそられるのは、あなたの問題の独自性です。これまでに公開された解決策は、干し草の山で一度に複数の針を探しているという事実をまったく利用していません。

確かにKMP/Boyer Mooreを見てみますが、1本の針に合わせて調整されているので、盲目的に適用することはしません（少なくとも手元に時間があれば）。複数の文字列があり、カスタムステートマシン（またはBMのカスタムテーブル）を使用してそれらすべてを一度にチェックするという事実を利用しました。

もちろん、ビッグオーを改善する可能性は低いですが（ボイヤームーア文字は各弦に対して3nで実行されるため、とにかく線形になります）、おそらく一定の係数で利益を得ることができます。

于 2010-08-25T06:22:09.420 に答える
1

これを見てください：http://www.boost.org/doc/libs/1_44_0/libs/regex/doc/html/boost_regex/configuration/algorithm.html

再帰的/非再帰的な区別の存在は、BOOST が必ずしも線形時間離散有限状態マシンではないことを強く示唆しています。したがって、特定の問題を改善できる可能性が高くなります。

最良の答えは、持っている干し草の山と針の最小サイズによってかなり異なります. 最小の針が数文字よりも長い場合は、一般化された正規表現ライブラリよりも少しだけうまくいく可能性があります。

基本的にすべての文字列検索は、現在の位置 (カーソル) での一致をテストすることによって機能し、何も見つからない場合は、カーソルをさらに右にスライドさせて再試行します。

Rabin-Karp は、検索対象の文字列 (または複数の文字列) から DFSM を構築し、テストとカーソルの動きが 1 回の操作で結合されるようにします。ただし、Rabin-Karp はもともと 1 つの針用に設計されているため、ある一致が別の一致の適切なプレフィックスになる場合は、バックトラッキングをサポートする必要があります。(コードを再利用したい場合に備えて覚えておいてください。)

もう 1 つの戦術は、可能であれば、カーソルを 1 文字以上右にスライドさせることです。ボイヤー・ムーアはこれを行います。通常、1 本の針用に作られています。すべての文字と、それらが針に現れる右端の位置 (存在する場合) のテーブルを作成します。次に、カーソルを len(needle)-1 に置きます。テーブル エントリは、(a) 針が見つかる可能性があるカーソルからの左方向オフセット、または (b) カーソル len(needle) をさらに右に移動できることを示します。

複数の針がある場合、テーブルの構成と使用はより複雑になりますが、プローブを大幅に節約できる可能性があります。それでも DFSM を作成したい場合がありますが、一般的な検索メソッドを呼び出す代わりに、dos_this_DFSM_match_at_this_offset() を呼び出します。

もう 1 つの戦術は、一度に 8 ビット以上をテストすることです。一度に 32 ビットの機械語を調べるスパムキラー ツールがあります。次に、単純なハッシュ コードを実行して結果を 12 ビットに合わせ、テーブルを調べてヒットがあるかどうかを確認します。パターンごとに 4 つのエントリ (パターンの先頭から 0、1、2、および 3 のオフセット) があり、この方法では、表に何千ものパターンがあるにもかかわらず、サブジェクトの 32 ビット ワードごとに 1 つまたは 2 つしかテストしません。ライン。

したがって、一般的に、はい、針が一定の場合、正規表現よりも速く進むことができます。

于 2010-08-25T10:53:34.700 に答える
0

正規表現エンジンの初期化にはある程度のオーバーヘッドが予想されるため、実際の正規表現が含まれていない場合は、C - memcmp() で問題なく動作するはずです。

ファイル サイズと具体的な使用例を教えていただければ、ベンチマークを作成できます (これは非常に興味深いと思います)。

興味深い: memcmp の探索とタイミングの違い

よろしく

rbo

于 2010-08-24T19:37:44.690 に答える
0

Flex および Bison ツールのサポートにより、非常に人気のある Lex および Yacc ツールで実行できます。文字列のトークンを取得するために Lex を使用できます。事前定義された文字列をレクサーから返されたトークンと比較します。一致が見つかったら、目的のアクションを実行します。Lex と Yacc について説明しているサイトはたくさんあります。そのようなサイトの 1 つがhttp://epaperpress.com/lexandyacc/です。

于 2010-08-27T11:28:04.117 に答える
0

ボイヤー・ムーアはいつもそこにいる

于 2010-08-24T19:51:45.327 に答える
0

Rabin-Karp-Algorithm と Knuth-Morris-Pratt-Algorithm のほかに、私の Algorithm-Book は、文字列マッチングのための有限ステート マシンを提案しています。検索文字列ごとに、そのような有限状態マシンを構築する必要があります。

于 2010-08-24T20:30:54.657 に答える