正規表現置換の複雑さ

StackOverflow https://stackoverflow.com/questions/21669

  •  09-06-2019
  •  | 
  •  

質問

これに対する答えはどこにもありませんでした。正規表現の一致と置換の実行時の複雑さはどれくらいですか?

編集：私はPythonで働いています。ただし、最も一般的な言語/ツール (Java、perl、sed) について全般的に知りたいと考えています。

役に立ちましたか？

解決

純粋に理論的な立場から言えば、

私がよく知っている実装は、正規表現を認識する決定論的有限オートマトンを構築することです。これは、標準アルゴリズムを使用して O(2^m) で実行されます (m は正規表現のサイズです)。これが構築されると、文字列を実行すると、文字列の長さは線形になります - O(n) (n は文字列の長さ)。文字列内で見つかった一致の置換は定数時間である必要があります。

したがって、全体としては O(2^m + n) だと思います。

他のヒント

その他の興味深い理論情報。

わかりやすくするために、正規表現の標準定義を仮定します。

http://en.wikipedia.org/wiki/レギュラー言語

形式言語理論から。実際には、これは唯一の建築材料がアルファベット記号、連結、交互の閉鎖、クリーンの閉鎖の演算子、およびユニットとゼロ定数（グループ理論的理由のために表示される）であることを意味します。一般的に、あいまいにつながる言語の日常的な練習にもかかわらず、この用語を過負荷にしないことは良い考えです。

正規表現rの一致する問題を解決するNFA構造と、O（| r | | t |）時間とO（| r |）スペースの入力テキストTを解決します。ここで| - |長さ関数です。このアルゴリズムはマイヤーズによってさらに改良されました

http://doi.acm.org/10.1145/128749.128755

オートマトン ノード リストと 4 つのロシア人のパラダイムを使用して、時間と空間の複雑さ O(|r| |t| / log |t|) を計算します。このパラダイムは、オンラインではない画期的な論文を書いた4人のロシア人の男にちなんで名付けられたようです。ただし、パラダイムはこれらの計算生物学の講義ノートに示されています

http://lyle.smu.edu/~saad/courses/cse8354/lectures/lecture5.pdf

姓の代わりに、著者の数と国籍によってパラダイムを挙げるのは陽気だと思います。

繰り返しを追加した正規表現の一致する問題はNP Completeであり、AHOによって証明されました

http://portal.acm.org/quote.cfm?id=114877

古典的な NP 完全問題である頂点カバー問題からの帰着によって。

正規表現と背景と決定的に一致するために、バックトラッキング（Perl Regexエンジンとは異なり）を使用して、Rの変数に割り当てることができる入力テキストTの可能なサブワードを追跡できます。rのいずれかの変数に割り当てることができるo（| t |^2）のサブワードのみがあります。rにn変数がある場合、o（| t |^2n）可能な割り当てがあります。変数へのサブストリングの割り当てが修正されると、問題は平易な正規表現のマッチングに減少します。したがって、正規表現と逆流を一致させるための最悪の複雑さはO（| t |^2n）です。

ただし、背景を伴う正規表現は、まだフル機能の再gexenではありません。

たとえば、他のオペレーターとは別に「気にしない」シンボルを考えてみましょう。パターンのセットが入力テキストと一致するかどうかを決定する多項式アルゴリズムがいくつかあります。たとえば、クチェロフとルシノウィッチ

http://dx.doi.org/10.1007/3-540-60044-2_46

パターンを単語 w_1@w_2@...@w_n として定義します。各 w_i は単語 (正規表現ではありません) で、「@」はどちらの w_i にも含まれない可変長の「ドントケア」記号です。それらは、入力テキストTと一連のパターンPを一致させるためのO（| t | + | p |）log | p |）アルゴリズムを導き出します。ここで| t |テキストの長さであり、| p | Pのすべての単語の長さです。

これらの複雑さの測定がどのように組み合わされ、正規表現の一致する問題の複雑さの尺度が、「Do n't Care」、および実用的な正規表現のその他の興味深い特徴をどのように組み合わせているかを知ることは興味深いでしょう。

ああ、Python については何も言っていませんでした...:)

正規表現で何を定義するかによって異なります。concatenation、alternative、および Kleene-star の演算子を許可すると、実際の時間は次のようになります。 O(m*n+m), 、 どこ m 正規表現のサイズであり、 n 文字列の長さです。これを行うには、NFA (つまり、線形) を構築します。 m）、その後、現在の状態のセットを維持し、それを更新することでそれをシミュレートします（ O(m)) 入力文字ごとに。

正規表現の解析を難しくしているもの:

  • 括弧と後方参照:キャプチャは前述のアルゴリズムでも問題ありませんが、複雑さが増すため実行不可能になる可能性があります。後方参照は正規表現の認識力を高め、その難易度は十分に高くなります
  • 前向きな先読み:これは交差の別の名前であり、前述のアルゴリズムの複雑さがさらに高まります。 O(m^2+n)
  • 否定的な先読み:オートマトンの構築には大失敗 (O(2^m), 、PSPACE が完了している可能性があります)。しかし、次のような動的アルゴリズムに取り組むことはまだ可能であるはずです。 O(n^2*m)

具体的に実装すると、状況が良くなったり悪くなったりする可能性があることに注意してください。経験則として、単純な機能は十分に高速であり、明確である必要があります (例:みたいではなく a*a*) 正規表現の方が優れています。

プライズの答えを詳しく説明すると、オートマトンの構築では O(2^m) が最悪のケースですが、それは実際には正規表現の形式に依存します (単語に一致する非常に単純な正規表現の場合、O( になります) m)、たとえば、 クヌース・モリス・プラットアルゴリズム).

実装に応じて異なります。どの言語/ライブラリ/クラスですか?最良のケースがあるかもしれませんが、それは実装内の機能の数によって非常に具体的になります。

DFA の代わりに非決定的な有限オートマトンを構築することで、スペースを犠牲にして速度を得ることができます。これは線形時間で通過できます。もちろん、最悪の場合、O(2^m) のスペースが必要になる可能性があります。トレードオフにはそれだけの価値があると期待しています。

照合と置換を行っている場合、それはグループ化と後方参照を意味します。

以下は、グループ化と後方参照を使用して NP 完全問題を解決できる Perl の例です。 http://perl.plover.com/NPC/NPC-3SAT.html

これは (他のいくつかの理論上の豆知識と組み合わせると)、照合と置換に正規表現を使用することが NP 完全であることを意味します。

これは、グループ化の概念がない正規表現の正式な定義とは異なり、他の回答で説明されているように多項式時間で一致することに注意してください。

ライセンス： CC-BY-SA と 帰属
所属していません StackOverflow
scroll top