28

正規表現のコンテナがあります。それらを分析して、複数の文字列に一致する文字列を生成できるかどうかを判断したいと思います。このユースケースを念頭に置いて独自の正規表現エンジンを作成する以外に、C ++またはPythonでこの問題を解決する簡単な方法はありますか？

4

3 に答える 3

37

簡単な方法はありません。

正規表現が標準機能のみを使用している限り（Perlでは任意のコードをマッチングに埋め込むことができると思います）、REがマッチングするすべての文字列をコンパクトにエンコードする非決定性有限状態オートマトン（NFA）をそれぞれから生成できます。

NFAの任意のペアが与えられると、それらの交差が空であるかどうかを決定できます。交差が空でない場合、一部の文字列はペアの両方のREに一致します（逆に）。

標準の決定可能性証明は、最初にそれらをDFAに決定し、次に、状態が2つのDFAの状態のペアであり、最終状態がペアの両方の状態が元のDFAで最終である新しいDFAを構築することです。 。あるいは、NFAの補集合を計算する方法をすでに示している場合は、（ドモルガンの法則スタイル）で交差を取得できますcomplement(union(complement(A),complement(B)))。

残念ながら、NFA-> DFAには、潜在的に指数関数的なサイズの爆発が伴います（DFAの状態はNFAの状態のサブセットであるため）。ウィキペディアから：

正規言語の一部のクラスは、決定性有限オートマトンによってのみ記述できます。そのサイズは、最短の同等の正規表現のサイズで指数関数的に増大します。標準的な例は、ここでは、k番目の最後の文字がaに等しいアルファベット{a、b}上のすべての文字列で構成される言語L_kです。

ちなみに、間違いなくOpenFSTを使用する必要があります。オートマトンをテキストファイルとして作成し、最小化、交差などの操作を試して、問題に対してどれほど効率的かを確認できます。オープンソースのregexp->nfa->dfaコンパイラがすでに存在します（Perlモジュールを覚えています）。1つを変更して、OpenFSTオートマトンファイルを出力し、遊んでください。

幸い、州のサブセットの爆発を回避し、DFAと同じ構造を使用して2つのNFAを直接交差させることができます。

if A ->a B （1つのNFAでは、状態AからBに移動して、文字「a」を出力できます）

およびX ->a Y（他のNFAで）

その後(A,X) ->a (B,Y)、交差点で

(C,Z)一方のNFAでCが最終であり、もう一方のNFAでZが最終である場合、は最終です。

プロセスを開始するには、2つのNFAの開始状態のペアで開始します。たとえば(A,X)、これは交差点の開始状態です-NFA。最初に状態にアクセスするたびに、2つの状態を離れるアークのペアごとに上記のルールに従ってアークを生成し、次にそれらのアークが到達するすべての（新しい）状態にアクセスします。状態のアークを展開したという事実を（たとえばハッシュテーブルに）保存し、最初から到達可能なすべての状態を探索することになります。

イプシロン遷移（文字を出力しない）を許可する場合、それは問題ありません。

A ->epsilon B最初のNFAの場合は、(A,Y)到達するすべての状態について、アーク(A,Y) ->epsilon (B,Y)を追加し、同様に2番目の位置のNFAのイプシロンについても追加します。

イプシロン遷移は、正規表現をNFAに変換するときに、2つのNFAの和集合を取得するのに役立ちます（必須ではありません）。交代があるときはいつでもregexp1|regexp2|regexp3、ユニオンを取ります。開始状態が交代の正規表現を表す各NFAへのイプシロン遷移を持つNFAです。

NFAの空を決定するのは簡単です。開始状態から深さ優先探索を実行して最終状態に到達した場合、それは空ではありません。

このNFA交差は、有限状態トランスデューサの構成に似ています（トランスデューサは、入力文字列と出力文字列の両方に一致するように、または特定の入力を出力に変換するためにペアごとに連結されたシンボルのペアを出力するNFAです）。

于 2009-12-04T20:34:03.910 に答える
2

この正規表現インバーター（pyparsingを使用して記述）は、re構文の限定されたサブセット（たとえば、*または+は許可されません）で動作します。2つのreを2つのセットに反転してから、セットの共通部分を探すことができます。

于 2009-12-04T21:38:43.390 に答える
-1

理論的には、あなたが説明する問題は不可能です。

実際には、限られたサブセットまたはregexp構文を使用する管理可能な数の正規表現、および/または正規表現のコンテナと照合するために使用できる文字列の限られた選択がある場合、それを解決できる可能性があります。

あなたが抽象的な一般的なケースを解決しようとしていないと仮定すると、実際のアプリケーションを解決するためにあなたができることがあるかもしれません。おそらく、正規表現の代表的なサンプルを提供し、照合する文字列を記述した場合、問題を解決するためにヒューリスティックを作成できます。

于 2009-12-04T20:58:18.300 に答える