既知の分離された数のテキストブロックを含む入力セットを提供します。
入力セット内のすべてのテキストブロックに一致する1つ以上の正規表現を自動的に生成するプログラムを作成したいと思います。
ブルートフォース検索を実装するための比較的簡単な方法がいくつかあります。しかし、私はコンパイラ理論の専門家ではありません。それが私が興味を持っている理由です：
1）この問題は解決可能ですか？または、そのようなアルゴリズムを作成するためのいくつかの原則的な不可能性がありますか？
2）このアルゴリズムの多項式の複雑さを達成し、ブルートフォースを回避することは可能ですか？
「。*」は、入力セット内のすべてのテキストブロックに一致する1つ以上の正規表現です。;-)
問題は、特定の入力セットに一致する正規表現が膨大な数 (実際には無限にある) あることです。それらは、すべてに一致する非常に「貪欲な」表現にまで及びます
.*
入力セットと完全に一致する非常に非「貪欲な」表現
InputA OR inputB OR inputC etc
これら 2 つの間で、さまざまな方法で表現を変更して、貪欲さを増減させることができます (たとえば、特定の数字を任意の数字に一致する表現に置き換えるなど)。
考えられる答えの範囲のどこが正しいのかを知るために、問題についてもう少し教えていただく必要があります;)
わかりました。コメントで、入力セット内の文字列の1つに等しいか、特定のレベルの「変動」内の文字列の1つとのみ異なるすべての文字列を照合することを明確にしました。'バリエーション'を正確に定義しなかったので、レーベンシュタイン距離を使用します。
文字列sと整数を指定すると、次のように、レーベンシュタイン距離がその文字列以下nのすべての文字列に正確に一致する正規表現を作成できます。n
最初に、距離が。以下のすべての文字列を一緒に一致させる単純なregexenのリストを指定sして返す関数を記述します。ここで、「単純な正規表現」とは、リテラル文字とワイルドカードのみを含む正規表現を意味します。nns
そのn=0関数の場合は、を返します[s]。それ以外の場合は、のリストを計算してn-1から、その中の各アイテムを調べます。アイテムrごと、および位置ごとiに0 <= i < length(r)、次のregexenがリストに追加されます。
.に追加された正規表現。riiのth文字rが削除された正規表現。iのth文字が。rに置き換えられた正規表現.。次に、特定の文字列セットの正規表現との特定の値nを計算するために、各文字列のリストを計算してから、orすべての正規表現を1つの大きな正規表現にまとめます。
これはすぐに非常に大きなregexenにつながることに注意してください。
http://txt2re.com/は、あなたが望むものかもしれません。