5

制限された正規表現を処理するように検索ツリーを適応させるにはどうすればよいですか？

ファイル名を指定すると、そのファイル名に一致するすべてのノードを見つける必要があります。ノードには、通常のファイル名グロブ（*および？）が含まれる場合があります。これは探索木であるため、速度が重要です。

スピードの最も重要なケースは、試合を除外する平均時間であることを付け加えておきます。ほとんどの場合、マッチングは失敗します。

ツリーに次のノードが含まれている場合：

foo, bar, foo*, *bar, foo?bar
  • 「foo」を検索すると、ノード1と3が返されます。
  • 「バー」を検索すると、ノード2と4が返されます。
  • 「fob」を検索してもノードは返されません。
  • 「fooxbar」を検索すると、ノード5が返されます。
  • 「foobar」を検索すると、ノード3と4が返されます。
4

1 に答える 1

9

Aho-Corasick検索ツリーは、この法案に適合します。「Tries 」は、この種のことと、正規表現検索を置き換えるために Evolution で使用されるEtrie実装に関する非常に優れた記事です。

文字列全体の一致を行うには、開始アンカー状態と終了アンカー状態を追加できます。複数行のデータをスキャンする場合、先頭と末尾に改行を追加できます。別の一致を開始する部分一致のクロス リンクを追加する部分を削除することもできます。これにより、より迅速な除外も可能になります。

文字列セットのメンバーシップをチェックする別のアルゴリズムはCritBitです。これには正規表現はありませんが、シンプルで完全な文字列をテストします。

于 2009-02-25T19:03:30.687 に答える