私はこのような状況に何度か遭遇しました: 一部のテキストが一致する複数のパターンがあり、そのパターンに基づいて何か特定のことをしたいとします。
以前は、常に正規表現のリストを使用して、一致が見つかるまで繰り返していました。
私が疑問に思っているのは、これにより効率的なデータ構造があるかどうかです。たとえば、C# を使用している場合、Regex キーを持つ辞書のようなものです。
パターンがすべて接頭辞または接尾辞である場合、Trie のようなものが理にかなっていることがわかりました。ただし、これが一般的なケースで機能するかどうかはわかりません。
また、キーの衝突に関して、ここでいくつかのあいまいさがあるように思えます。たとえば、一部のテキストが複数のパターンに一致する場合、何を返す必要がありますか? (その場合、おそらく非決定論的な結果でも問題ないと思いますが、動作が文書化されている限り、問題ありません。)
とにかく、そのようなデータ構造は .NET または他の場所に存在しますか?
数年前、トーマスが回答で説明したものと非常によく似た、決定論的な有限状態マシンに基づく正規表現検索エンジンの実装を作成しました。正規表現キーと値のリストを単一の有限状態オートマトンにコンパイルします。これは、最終状態で定義された型のオブジェクトを参照します (たとえば、RegexTrie は最終状態で文字列を参照します)。
実装はこちらから入手できます: https://bitbucket.org/tjnieminen/regexkeytrie
標準検索は、マシン全体のパスのリストを維持することによって実行されます。各アクティブ パスは、検索テキストの文字ごとに進められ、最終状態に到達するたびに一致が記録されます。マシン ルートで始まる新しいパスがソース テキストの各文字に追加され (これにより部分文字列の一致が可能になります)、非終端状態で停止するパスはパス リストから削除されます。
一般に、タスクが何であれ、処理をカスタマイズするのが最善です。たとえば、エンジンを正規表現の置換に使用する場合、返された一致で検索および置換アクションを実行する代わりに、トラバーサル中に (トランスデューサーのように) 編集されたテキストを生成するのが最善の場合があります。
通常の .Net 正規表現に対して実装のベンチマークを行いましたが、正規表現の大規模なセットと検索する長いテキストの組み合わせなど、本来あるべきシナリオではうまくいくようです。
実装は完全にテストされていないため、いくつかのバグが残っている可能性があり、複雑な正規表現を使用するとメモリ不足になる可能性があります (または、コンパイルに永遠にかかる可能性があります)。しかし、現時点では同様のものは利用できないため、それが提供するパフォーマンス特性を探している人にとっては有用な出発点になるかもしれません.