1

Regex が 3000 行の XML ファイルを完成させるのは非常に遅いことに気付きました [1]:

\(<Annotation\(\s*\w\+="[^"]\{-}"\s\{-}\)*>\)\@<=\(\(<\/Annotation\)\@!\_.\)\{-}"MATCH\_.\{-}\(<\/Annotation>\)\@=

私は常々、正規表現は効率的だと思っていました。正規表現を完了するのになぜそんなに時間がかかるのですか?

[1] VIM で A から B まで繰り返し一致させるにはどうすればよいですか?

4

4 に答える 4

5

効率的かどうかは正規表現自体に依存します。それが非効率になるのはバックトラックです。そしてこれを避けるために、正規表現は可能な限り明確でなければなりません。

a.*b例として正規表現を取り上げ、それを文字列に適用してみましょうabcdef。アルゴリズムは、最初にリテラルaina.*bをainに一致させabcdefます。次に、式.*が処理されます。乗数が最大に拡張される通常の貪欲モードでは、の残りの部分全体に一致しbcdefますabdef。の最後のリテラルよりも処理さbれa.*bます。ただし、文字列の終わりにすでに到達しており、乗数が使用されているため、アルゴリズムはパターン全体に一致するようにバックトラックを試みます。.*（ ）の一致はbcdef1文字（）減少しbcde、アルゴリズムは残りのパターンに準拠しようとします。しかし、bインa.*bは一致しませんfでabcdef。したがって、空の文字列と一致し（したがって、0回繰り返される）、inがinと一致.*するまで、さらに1文字減少します。.ba.*bbabcdef

ご覧のとおり、正規表現全体が一致するまで、6つのバックトラッキングアプローチが必要a.*bです。ただし、正規表現を変更し、代わりにを使用して区別する場合は、バックトラックは不要であり、正規表現は最初のアプローチ内で一致する可能性があります。abdef.*a[^b]*b

そして、代わりに怠惰な修飾子を使用することを検討している場合、このルールは、貪欲な修飾子と怠惰な修飾子の両方のすべての修飾子に適用されることをお伝えしておきます。違いは、最初に一致を最大に拡張する代わりに、一度に1文字ずつ一致を減らすことによってバックトラックを実行する（貪欲）のではなく、レイジー修飾子は最初に最小の一致に拡張され、次に一度に1文字ずつ増加します。

于 2009-04-11T12:47:01.263 に答える
3

REは効率的ですが、魔法ではありません :-)

速度を低下させるのは、入力ファイルの行数ではありません (3,000 は非常に小さい数値です)。RE がコンパイルされると、基本的に (概念的に) その RE に基づいて入力ファイルを解析できるプログラムを作成する必要があります。

その「プログラム」の速度は、常に RE の複雑さに依存します。

たとえば、"^$"非常に高速に"[0-9]{1,9}"なり、やや遅くなり、バックトラッキングを含むもの (つまり、RE でバックアップする必要があるもの、通常は複数の要素数の可変句を含むもの) は次のようになります。まだ遅い。

事前に行数を最小限に抑えるためにできることは、ある程度は役に立ちますが、RE 自体の最適化に関しては、それはしばしば黒魔術と見なされます。1 つの可能性は、注釈が停止および開始する行の間の行以外の行を最初に削除することです。

RE の最適化についてあまり心配することはありません (通常、RE はそれほど複雑ではありません)。私の見解では、彼らは時間がかかると思います。それが長すぎる場合、私は通常、より高速で適応性の低い別のソリューションを探します。

属性に MATCH が含まれるすべての注釈 XML を取得したい RE の場合about、入力ファイルが合理的に固定された形式であるため、Perl (または、私たちベテランの場合は awk :-) でそれを行います。

  • 最初の行の「<注釈」[a]。
  • 「MATCH」も最初の行 [a] にあります。
  • </Annotation> は最後の行とそれ自体 [b] にあります。

これは単純なライン スキャナとして高速であり、[a] 条件が満たされたときにエコーをオンにし (そしてその行を印刷)、エコーがオンのときに他の行を印刷し、[b] 条件が満たされたときにエコーをオフにします (その後)。印刷ライン）。

はい、適応性ははるかに低くなりますが、ほぼ確実に高速になります（適切にフォーマットされた入力を考えると）。

于 2009-04-11T12:33:48.860 に答える
2

すべての円記号を使用して正規表現を読み取るのは非常に難しいと思います。この正規表現の方言（vim？）を正しく解釈している場合、あなたが言っているのは、冗長なpcreが綴る内容です。

(?<= <Annotation(\s*\w+="[^"]*?"\s*?)*> )
    ((?! <\/Annotation).)*?
    "MATCH.*?
(?= <\/Annotation> )

飛び出す明らかな問題は、可変長のルックビハインドアサーションで始まることです。可変長の後読みは、そのままでは十分に面倒ですが（多くの正規表現の方言ではサポートされていません）、その後にリベラルな一致（負の先読みを持つ文字）が続くことでさらに複雑になります。

これは、プロセッサが一致するのは難しいです。この組み合わせは、達成できた可能性のある最適化をほとんど無効にします。ファイル内のすべての文字について、後戻りが一致するかどうかを確認するために（ファイルの先頭/前の一致の終わりまで）バックトラックしてから、「MATCH」を探して（ファイルの終わりまで）前に進む必要があります。

固定サイズのルックビハインドのみを使用するか、単にルックアラウンドを忘れて文字列全体を一致に含めることで、それを助けることができます。これにより、検索にもう少し後処理が必要になりますが、検索がより効率的になります。興味のあるグループ。

<Annotation(\s+(\w+="[^"]))*\s*>
    (.*? "MATCH .*?)
<Annotation>

ただし、この種の質問ではいつものように、Clippy sez：

正規表現を使用してXMLを解析しているようです。

ヘルプが必要ですか？

（）正規表現は本質的にXMLを解析できないため、実際のXMLパーサーを使用します

（）まだ機能しない読み取り不可能な複雑な正規表現を作成するだけの兵士

[]このヒントを二度と見せないでください

于 2009-04-11T13:02:36.187 に答える
1

「正規表現は効率的です」は、特性が広すぎて正確ではありません。さまざまな正規表現エンジンによって提供される相対的なパフォーマンスの違いを無視しても、正規表現の効率はパターンの複雑さに依存します。

正規表現は、テキストの一部をより速く一致させるのではなく、より速く失敗した場合に効率的です。IOW、完全に一致しないテキストが最後に到達するのではなく、一致プロセスの早い段階で拒否されるように、十分に具体的である必要があります。これは、バックトラックを最小限に抑える必要があることも意味します。バックトラックは壊滅的なレベルに達する可能性があり、最高の正規表現エンジンでさえフリーズすることに注意してください。Jan Goyvaertsによって提供された例では、ファイルのサイズは言及されておらず、関連性がありません。ただし、重要なのは文字列のサイズです。

これは、数年前にRegexAdvice.comで開始した、正規表現のパフォーマンスについて人々に議論してもらうことを目的としたディスカッションスレッドです。そこから学ぶべきいくつかの指針があると思います。

于 2009-04-11T12:52:02.403 に答える