6

私はフォームの（種）名を解析しています：

Parus Ater
H. sapiens
T. rex
Tyr. rex

通常は 2 つの項 (二項式) がありますが、3 つ以上の項がある場合もあります。

Troglodytes troglodytes troglodytes 
E. rubecula sensu stricto

私が書いた

[A-Z][a-z]*\.?\s+[a-z][a-z]+(\s*[a-z]+)*

ほとんどの場合は機能しましたが、無限ループに陥ることがありました。それが正規表現マッチングにあることを突き止めるのに少し時間がかかりましたが、それがタイプミスであることに気づき、書くべきでした

[A-Z][a-z]*\.?\s+[a-z][a-z]+(\s+[a-z]+)*

これは適切に実行されます。

私の質問は次のとおりです。

  • なぜこのループが起こるのですか？
  • プログラムを実行する前に同様の正規表現エラーをチェックする方法はありますか? そうしないと、プログラムが配布される前にそれらをトラップすることが困難になり、問題が発生する可能性があります。

[注: 種のより一般的な表現は必要ありません - 種の名前には正式な 100 行以上の正規表現仕様があります - これは最初のフィルターにすぎません]。

注: ほとんどの名前は正確に 2 語または場合によっては 3/4 語 (イタリック体で表示されている) に抽出されていましたが、いくつかの誤検出 ( など"Homo sapiens lives in big cities like London") があり、一致が "L" で失敗したため、問題が発生しました。

注: これをデバッグしているときに、正規表現はしばしば完了していましたが、非常に遅いことがわかりました (たとえば、ターゲット文字列が短い場合)。病理学的なケースを通じてこのバグを発見したことは貴重です。私は重要な教訓を学びました！

4

2 に答える 2

7

質問の最初の部分に対処するには、壊滅的なバックトラッキングを読む必要があります。基本的に、正規表現を文字列と一致させる方法が多すぎるため、パーサーはそれを機能させるために継続的にバック トラッキングを行っています。

あなたの場合、それはおそらくネストされた繰り返しでした。 (\s*[a-z]+)*これにより、非常に奇妙なループが発生した可能性があります。Qtax が巧みに指摘しているように、これ以上の情報がないと判断するのは困難です。

ご質問の 2 番目の部分は、残念ながらお答えできません。それは基本的に停止問題です。正規表現は本質的に入力が文字列である有限状態マシンであるため、どの正規表現が壊滅的にバックトラックし、どれがそうでないかを予測する一般的なソリューションを作成することはできません。

正規表現をより速く実行するためのヒントについて教えてください。それはワームの大きな缶です。私は自分で正規表現を研究するのに多くの時間を費やし、それらを最適化するのに時間を費やしました。一般的に役立つことがわかったのは次のとおりです。

  1. 言語でサポートされている場合は、ループの外で正規表現をコンパイルします。
  2. アンカーが有用であることがわかっている場合は、可能な限りアンカーを追加してください。特に^文字列の先頭に。参照: 単語境界
  3. ペストのようなネストされた繰り返しを避けてください。それが必要な場合は (そうするつもりです)、意図しないバックトラッキングを回避するためのヒントをエンジンに提供するために最善を尽くしてください。
  4. フレーバー コンストラクトを利用して処理を高速化します。私は、非キャプチャ グループと所有量指定子が好きです。すべてのフレーバーに表示されるわけではありませんが、表示される場合は使用する必要があります。原子団もチェック
  5. 私は常にこれが正しいと思っています:正規表現が長くなればなるほど、効率化に苦労することになります. 正規表現は優れた強力なツールであり、非常にスマートなハンマーのようなものです。 すべてを釘のように見るという罠にはまらないでください。探している文字列関数が目の前にある場合があります。

これがお役に立てば幸いです。幸運を。

于 2013-04-10T08:04:28.270 に答える
2

最初の正規表現の場合:

[A-Z][a-z]*\.?\s+[a-z][a-z]+(\s*[a-z]+)*

(\s*[a-z]+)*コメントで指摘されているように、壊滅的なバックトラックが発生します。ただし、 で文字列を検証している場合にのみ true を保持します。String.matches()これは、無効な文字に遭遇するとエンジンが一致を返すのではなく、バックトラックを試行する唯一のケースであるためです (Matcherループ)。

に対して無効な文字列を照合してみましょう(\s*[a-z]+)*:

inputstringinputstring;

(Repetition 1)
\s*=(empty)
[a-z]+=inputstringinputstring
FAILED

Backtrack [a-z]+=inputstringinputstrin
(Repetition 2)
\s*=(empty)
[a-z]+=g
FAILED

(End repetition 2 since all choices are exhausted)
Backtrack [a-z]+=inputstringinputstri
(Repetition 2)
\s*=(empty)
[a-z]+=ng
FAILED

Backtrack [a-z]+=n
(Repetition 3)
\s*(empty)
[a-z]+=g
FAILED

(End repetition 3 since all choices are exhausted)
(End repetition 2 since all choices are exhausted)
Backtrack [a-z]+=inputstringinputstr

ここまでで、問題に気付くはずです。T(n)長さ n の文字列がパターンに一致しないことを確認するための作業量として定義しましょう。バックトラックの方法から、私たちは知っていT(n) = Sum [i = 0..(n-1)] T(i)ます。そこから、 を導き出すことができますT(n + 1) = 2T(n)。つまり、バックトラッキング プロセスは時間の複雑さにおいて指数関数的です!

に変更*すると+ 、問題が完全に回避されます。繰り返しのインスタンスは、スペース文字と英語のアルファベット文字の間の境界でのみ開始できるためです。対照的に、最初の正規表現では、任意の 2 つのアルファベット文字の間で繰り返しのインスタンスを開始できます。

これを実証する(\s+[a-z]+\s*)*ために、無効な入力文字列に複数の連続するスペースで区切られた多くの単語が含まれている場合、繰り返しインスタンスの複数の場所を開始できるため、逆戻り地獄が発生します。これは、が連続するスペースの最大数 (マイナス 1) であり、 が連続するスペースの数であるという式b^dに従います。最初の正規表現よりも深刻ではありません (最初の正規表現では繰り返しごとに 1 つの英語のアルファベットが必要であるのに対し、繰り返しごとに少なくとも 1 つの英語のアルファベットと 1 つの空白文字が必要です) が、それでも問題は残ります。bd

于 2013-04-10T08:54:41.917 に答える