環境：
小さい (現在は 100 未満) ですが、正規表現のコレクションが増えています。特定のテキスト文字列に対して、コレクション内のどの正規表現がテキスト文字列と一致するかを判断するプロセスを最適化したいと考えています。
一部の RE には順序関係があります。たとえば、文字列 $t が /windows/i に一致することがわかっている場合、$t が /windows.*2000/i に一致することもわかっています。したがって、コレクション内の RE に対して $t をテストするとき、/windows.*2000/i に対して $t を既にテストして一致が見つかった場合は、/windows/i のテストをスキップできます (ただし、/windows.*2000/i が一致する場合)。一致しない場合、もちろん/windows/i に対するテストをスキップできません)。
私のコレクションの RE はどれも完全に同等ではないことに注意してください (RE の任意のペアには、一方に一致し、他方に一致しないテキスト文字列が少なくとも 1 つ存在します)。
ストラテジー：
コレクション内の各 RE のノードと、順序関係 (A -> B は「A との一致は B との一致を意味する」という意味) を持つ RE の各ペアの有向エッジを持つ有向グラフ G を構築し、グラフのノードの「最小スパニング セット」(G 内のすべてのノードが S から始まる有向パス上にあるようなノード S の最小セット)。
簡単な部分:
有向非巡回グラフを操作するための自由に利用できるアルゴリズムが多数あります。したがって、グラフ G が RE のコレクションに対して構築されると (G が非巡回であることは明確であることが保証されるはずです)、G の最小スパン集合を見つけるための適切なアルゴリズムを見つけるのにそれほど苦労することはないと思います。
助けが必要な場所:
コレクション内の RE 間のすべての順序関係を見つける効率的な方法を見つけたいと考えています。また、コレクション内の 2 つの RE が同等でないことを確認するためにも必要です (新しい RE が同じであるため、これを自動的に検証する方法が必要になります)。追加した）。
したがって、私の (基本的にランダムな) Web 検索では、2 つの RE 間に存在する順序関係 (存在する場合) を計算する合理的な方法が実際に存在するというもっともらしい主張が少なくとも 1 つ見つかりましたが、完全なアルゴリズムの説明はまだ見つかっていません。
合理的に効率的で、自由に利用でき、(理想的には) 一般的なスクリプト言語または C/C++ のいずれかで実装されている (RE を比較するための) 既存の実装を知っている人はいますか?