regex - 正規表現置換の複雑さ

Question

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

編集：私はPythonで作業しています。しかし、最も人気のある言語/ツール（java、perl、sed）について一般的に知りたいです。

Answer 1

純粋に理論的な立場から：

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

したがって、全体として、O（2 ^ m + n）と思います。

Answer 2

theprise の答えを掘り下げると、オートマトンの構築では、O(2^m) が最悪のケースですが、それは正規表現の形式に大きく依存します (単語に一致する非常に単純なものの場合、O( m)、例えば、Knuth-Morris-Pratt アルゴリズムを使用)。

Answer 3

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

Answer 4

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

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

これは (他のいくつかの理論的なヒントと相まって)、マッチングと置換に正規表現を使用すると NP 完全であることを意味します。

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

Answer 5

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