7

静的文字列（特定の正規表現が一致するために一致しなければならない文字列）を効率的に抽出しようとしています。私は最も単純なケースでそれを行うことができましたが、より堅牢なソリューションを見つけようとしています。

以下のような正規表現が与えられます

"fox jump(ed|ing|s)"

私たちに与えるだろう

"fox,jumped,jumping,jumps"

別の例は

"fox jump(ed|ing|s)?"

それは私たちに与えるだろう

"fox,jump"

オプションの演算子のため

私が持っているアルゴリズムは今のところ非常に単純です。正規表現の最後から始まり、グループまたは単一の文字の後にこれらの演算子「*？」が続くものを削除します。また、グループ化されたOR演算子「（|）」を「分解」します。これは非常にうまく機能しましたが、正規表現の完全な構文を考慮していません。これは、正規表現の最小セット生成プロセスの一種と考えることができます（正規表現が「生成/一致する必要がある」文字列の最小セット）。

なぜ？ 大量のテキストを大量の正規表現と照合しようとしています。「必須」であるこれらの正規表現の「キーワード」のリストを取得できる場合は、そのキーワードをすばやくテキスト検索して、関心のある正規表現をフィルタリングできます（一致しないことが保証されているものは無視するか、そのテキストをスキップすることもできます）。正規表現のセット内で一致しないことが保証されているため、テキストに対して正規表現を完全に効果的に実行していません）。このキーワードのセットを効率的なデータ構造（Binary Search / Trie / Aho-Corasick）に整理して、有限オートマトンでテキストを実行する前に、一連のregexesをフィルター処理できます。正規表現を実行する前にフィルタリングステージとして実行できる非常に高速な文字列照合アルゴリズムがあります。私'

4

2 に答える 2

0

私があなたの問題を正しく理解しているなら、あなたはこれらすべての単語が（与えられた）正規表現によって受け入れられる任意の単語の（ばらばらの）部分文字列であるような単語のセットを探しています。

私の推測では、そのようなセットは非常に多くの場合空になりますが、それでも見つけることができます。

そのようなセットを見つけるために、私は次のアルゴリズムを提案します。

  1. 入力正規表現に対応するFAを見つけます。
  2. 開始状態Sと受け入れ状態Fの間のブリッジ（https://en.wikipedia.org/wiki/Bridge_(graph_theory））を特定します。これは、たとえば、エッジEを削除し、Sからパスが存在するかどうかを確認することで実行できます。 Eを削除したFAのEに-すべてのエッジに対してこれを繰り返します。
  3. ブリッジであるすべてのエッジは、受け入れ実行中にヒットする必要があり、各エッジは入力文字に対応します。
  4. これで、後続のブリッジエッジをエンドツーエンドで接続することにより、必要な単語を生成できます。

アルゴリズムの構築から、これが機能するにはFA（DFAではなく）で十分であると思います。繰り返しになりますが、証明は素晴らしいでしょうが、私はそれがうまくいくはずだと思います:)

于 2013-01-04T23:21:31.253 に答える
0

正規表現を指定すると、一致する可能性のあるすべての文字列が得られるライブラリXegerを参照してください。

これらの文字列の共通の接頭辞（オプションの演算子を無視すると言った部分）だけを保持したいようですが、そうすると、その共通の接頭辞があり、目的の末尾がない刺し傷をキャプチャする可能性があります（「あなたの例では「びくびく」）。これが問題にならない場合は、オプションの演算子が正規表現の最後でのみ発生すると仮定して、Xegerによって指定された最短の文字列を見つけてください。

于 2014-11-15T10:44:55.597 に答える