正規表現のコレクションのために「最小限のスパニングセット」を見つける方法は？

Question

環境：

私は小さい（現在100未満）が、正規表現のコレクションを拡大しているので、特定のテキスト文字列を決定するプロセスを最適化したいと思います。

RESの一部には順序付け関係があります - たとえば、文字列$ tが /Windows /iと一致することを知っている場合、$ tが /windows.*2000/iであることも知っています。したがって、私のコレクションのRESに対して$ tをテストするとき、私はすでに/Windows.*2000 /iに対して$ tをテストしていて、試合を見つけた場合、テスト /Windows /iをスキップできます（ただし/Windows.*2000 /I Does いいえ もちろん私は一致します できません /windows /i）に対してテストをスキップします。

私のコレクションのRESのいずれも完全に同等ではないことに注意してください（REのペアには、1つに一致して行うテキスト文字列が少なくとも1つあります。 いいえ 他のものと一致します）。

ストラテジー：

コレクションの各REのノードと、順序付け関係を持つREの各ペアの指向性エッジを使用して指向グラフGを構築したい（A-> bは「bとの一致との一致」を意味します）、そしてaを見つけたいと考えています。グラフのノードの「最小限のスパニングセット」（gのすべてのノードがSに由来する方向のパスにあるように、ノードの最小セット）。

簡単な部分：

指示された非環式グラフを操作するための自由に利用可能なアルゴリズムがたくさんあります。したがって、RESのコレクション用にグラフGが構築されたら（Gが非環式であることが明確であることは保証されるはずです）、Gの最小限のスパニングセットを見つけるための適切なアルゴリズムを見つけるのはそれほど困難ではありません。

私が助けが必要なところ：

私のコレクション内のRES間のすべての順序関係を見つける効率的な方法を見つけたいと思います - そしておそらく、コレクションの2つのREが同等のものでないことを確認したいと思います（新しいRESがそうであるため、これを自動的に検証する方法が必要です追加した）。

したがって、私の（本質的にランダムな）Web検索は、2つのRESの間に（もしあれば）順序付け関係が実際に存在するが、完全なアルゴリズムの説明をまだ表示していないという合理的な順序付け関係が存在する合理的な方法があるという少なくとも1つの妥当な主張を示しています。

合理的に効率的で、自由に入手可能な既存の実装（RESを比較する）を知っている人はいますか？

Answer 1

使用する必要がある正規表現ライブラリに関して柔軟性があるかどうかはわかりませんが、見ることができます RE2 だれの 設定 インターフェイスは、複数の正規表現を同時に一致させることができます。 RE2は主にDFAアプローチを使用しており、他の、ほとんどバックトラッキングの実装が行うすべての正規表現機能をサポートしていないことに注意してください。