値からすべての正規表現を見つける

Question

URLを持つ変数と100個の正規表現を含むファイルがあります。どの正規表現がその変数に当てはまるかをどのように見つけることができますか？私はファイル内のすべてのパターンに対してパターンマッチをしたくありません。効率的なソリューションを探しています。

Answer 1

最終的には、「真の」パフォーマンス効率の良いソリューションを手放すことはできませんが、評価する必要のあるパターンの数を減らすために活用できる簡単なヒューリスティックがあります。

たとえば、単純化されたバージョンを使用してパターンを「グループ化」してみてください。二つのパターン

[a-z]\d[a-z] 
[a-z]{3} 

もパターン​​にマッチするこれらのパターンの両方に一致する文字列を考えます。より一般的なパターンが一致しない場合、前の2つのパターンをスキップすると、全体の処理時間を節約できます（おそらく）。より一般化できるほど、より多くのパターンを一度に削除できます。これの最終的な表現は階層的であり、パターンはファイルシステムのようなグループ構成に従います。このシステムの最悪の場合のパフォーマンスは、すべてのパターンを通過するよりも悪いですが、パターンの異なるグループが削除されるため、平均的なケースはやや良いでしょう。

あなたはO(n)の正規表現の数に比べてパフォーマンスは良くなりませんが、係数はnで節約される可能性があります。