なぜPerlのバックトラッキングの失敗は成功と比べて時間がかかりますか？

Question

私は巨大なファイルaab.txtを持っています。内容はaaa ... aabです。私の大きな驚き

perl -ne '/a*bb/' < aab.txt 

実行（試合障害）よりも速く

perl -ne '/a*b/' < aab.txt 

（マッチ成功）へ

。なぜ？？？？どちらも最初にすべてのaを邪魔しなければならず、次に2番目のものがすぐに成功し、最初のものは何度も何度も戻って失敗しなければなりません。

Answer 1

Perl正規表現は、できるだけ早く成功するよりも、できるだけ早く失敗するように最適化されています。これは、大規模なログファイルをグレープするときには非常に意味があります。

文字列の定数部分を最初に検索する最適化があります。この場合、「浮動」bまたはbbです。これは、バックトラッキング状態を追跡することなく、むしろ効率的にチェックすることができます。いいえbbが見つかり、一致がすぐに中止されます。

あまりにもbで。その浮動部分文字列が見つけられ、そこでマッチが構築されます。ここで正規表現マッチのデバッグ出力は、（プログラムが"aaab" =~ /a*b/である）である：

Compiling REx "a*b" 
synthetic stclass "ANYOF_SYNTHETIC[ab][]". 
Final program: 
    1: STAR (4) 
    2: EXACT <a> (0) 
    4: EXACT <b> (6) 
    6: END (0) 
floating "b" at 0..2147483647 (checking floating) stclass ANYOF_SYNTHETIC[ab][] minlen 1 
Guessing start of match in sv for REx "a*b" against "aaab" 
Found floating substr "b" at offset 3... 
start_shift: 0 check_at: 3 s: 0 endpos: 4 checked_upto: 0 
Does not contradict STCLASS... 
Guessed: match at offset 0 
Matching REx "a*b" against "aaab" 
Matching stclass ANYOF_SYNTHETIC[ab][] against "aaab" (4 bytes) 
    0 <> <aaab>    | 1:STAR(4) 
            EXACT <a> can match 3 times out of 2147483647... 
    3 <aaa> <b>    | 4: EXACT <b>(6) 
    4 <aaab> <>    | 6: END(0) 
Match successful! 
Freeing REx: "a*b" 

あなたはreプラグマのdebugオプションを指定して、このような出力を得ることができます。

厳密に言えば、bまたはbbを見つけることは必要ありませんが、一致がずっと早く失敗することができます。

Answer 2

/a*bb/ 

基本的

/^(?s:.*?)a*bb/ 

2つ*に留意されたいです。最適化はさておき、それは二次関数です。最悪の場合のシナリオ（すべてaの文字列）では、長さNの文字列に対して、現在の文字がa N *（N-1）/ 2回であるかどうかがチェックされます。これをO（N ）と呼びます。

文字列（O（N））のスキャンを実行して、マッチを開始する前に一致する可能性があるかどうかを調べる価値があります。マッチするのにもう少し時間がかかりますが、マッチするのがずっと速くなりません。これはPerlの動作です。

次

perl -Mre=debug -e"'aaaaab' =~ /a*bb/" 

1. を実行すると、あなたは、パターンのコンパイルに関する情報を取得：

   Compiling REx "a*bb" 
   synthetic stclass "ANYOF{i}[ab][{non-utf8-latin1-all}]". 
   Final program: 
       1: STAR (4) 
       2: EXACT <a> (0) 
       4: EXACT <bb> (6) 
       6: END (0) 
   floating "bb" at 0..2147483647 (checking floating) stclass ANYOF{i}[ab][{non-utf8-latin1-all}] minlen 2 
   

   最後の行は、それが起動する前に入力してbbを検索することを示します合わせる。

2. あなたはパターンの評価に関する情報を取得：

   ここ

   Guessing start of match in sv for REx "a*bb" against "aaaaab" 
   Did not find floating substr "bb"... 
   Match rejected by optimizer 
   

   あなたは、アクションにそのチェックを参照してください。