2

決して戻らない正規表現を書くことが可能だとは思ってもみませんでした。

正規表現

/^((?:\d|\w{1,2}[-\d\s])(?:[-\s\d]|\w{1,2}[-\d\s])*\d)$/

1桁または2文字で始まり、その後にダッシュ、空白または数字が続き、数字で終わる数字に一致するように構築されました。開始パターンの間に繰り返されるか、空白またはダッシュが発生する可能性があります。

例：1234、de-12943、EN-12de -50

次のサンプルコードは終了しません。

ルビー

#!/usr/bin/ruby
string = "101000000750000000000000000000000001000038127OXMOO0OOOOO00000000000N9"
re = /^((?:\d|\w{1,2}[-\d\s])(?:[-\s\d]|\w{1,2}[-\d\s])*\d)$/
p re.match("101000000750000000000000000000000001000038127OXMOO0OOOOO00000000000N9")

スカラ

"""^((?:\d|\w{1,2}[-\d\s])(?:[-\s\d]|\w{1,2}[-\d\s])*\d)$""".r findFirstIn "101000000750000000000000000000000001000038127OXMOO0OOOOO00000000000N9"

アンカー（^、$）を削除すると、正規表現をすばやく終了できます。

RubyとScalaで試してみました。

そこで何が起こっているのですか？アンカーはより速い終了につながるべきではありませんか？

4

1 に答える 1

11

まず、\wは手紙ではなく、[a-zA-Z0-9_]です。だから、本当に文字が欲しいだけなら、それを作って[a-zA-Z]ください。

第二に、壊滅的なバックトラックのケースがあるかもしれないと思います。

OXMパターン内の3つの連続する文字を一致させる方法がないため、正規表現は明らかに通過しません。アンカーを削除する$と、正規表現は喜んで一致しますが、アンカーを離れると、正規表現は失敗し、バックトラックを開始します。

それで、それがと一致OXし\w{1,2}、失敗したと仮定します。次に、2番目の非キャプチャグループ全体の最後の繰り返しを破棄し、1ステップ戻って、と一致7し[-\s\d]ます。これで、代わりにまたはと一致しようとしますが、それぞれまたは7Oとの一致に失敗します。もう1つ後退すると、再マッチングまたはとの再マッチングが試行され、再度失敗します。などなど。さらに戻ると、文字との照合が再び可能になる可能性があります。そうすると、エンジンは完全に前進します。7\w{1,2}[-\d\s]XO272\w{1,2}[-\d\s]OXMもう一度、楽しみを再開します。バックトラックが最終的に文字列の先頭と最初の交代に達すると、その交代の3つのオプションすべても試行され、すべてが何度も繰り返されます。

繰り返しで使用されている代替案を書き出すことにより、バックトラックの最初のステップを視覚化してみましょう。各2行の最初の行はテストされた文字列で、2番目の行には使用された対応する正規表現構造が含まれています。各試行は最後の文字で失敗します。

... 1       2       7       O
... [-\s\d] [-\s\d] [-\s\d] [-\s\d] 

... 1       2       7       OX    M
... [-\s\d] [-\s\d] [-\s\d] \w{2} [-\d\s]

... 1       2       7       O     X
... [-\s\d] [-\s\d] [-\s\d] \w{1} [-\d\s]

... 1       2       7O    X
... [-\s\d] [-\s\d] \w{2} [-\d\s]

... 1       2       7     O
... [-\s\d] [-\s\d] \w{1} [-\d\s]

... 1       27    O      
... [-\s\d] \w{2} [-\d\s]

... 1       2     7       O
... [-\s\d] \w{1} [-\d\s] [-\s\d]

... 1       2     7       OX    M
... [-\s\d] \w{1} [-\s\d] \w{2} [-\d\s]

... 1       2     7O    X
... [-\s\d] \w{1} \w{2} [-\d\s]

等々。私はあなたがその考えを理解することを望みます。数行のASCIIでそれを視覚化するのは難しいです。

\w同等の組み合わせが少ないため、適切な文字グループに変更するだけで、すでに問題が解決している可能性があります。やってみよう。

于 2012-11-07T11:08:20.597 に答える