正則表達式掛起模式匹配

我已經輸入文件here（請解壓縮它）和下面的代碼。剛剛打印出「pat = \ n」;它掛在模式匹配，而我看到在Windows任務管理器的Perl（v5.010000）以25％的CPU時間：正則表達式掛起模式匹配

use strict; 
open FP, "<default.php" or die "can't read"; 

$/ = undef;  

my $content = <FP>; 

while ($content =~ /(['"])([^\s\x00-\x1f]{300,})\1/gs) { 
#looks like we've found base encoded string etc 
    my $subpat = $2; 
    print "pat=<$subpat>\n"; 
    if ($subpat =~ m#(?:(....).{5,30}(?=\1)){50}#s) { 
     print "hello world"; 
    } else { 
     die(""); 
    } 
    exit; 
}

編輯：理想我想弄清楚任何制服重複的字節模式（長什麼： 4）在連續組（最大50）中，其中每個組大小可以是4 + 30字節最大值和4 + 5字節最小值。

例如（各組大小在重複 '=>' 1至30字節）：

'CS'=> '捷克'， 'DA'=> '丹麥'， 'NL' =>'荷蘭語'，'fi'=>'芬蘭語'，'fr'=>'法語'，'de'=>'德語'，'el'=>'希臘語'，

該行：print「pat = \ n」;打印以下和掛起：

輕拍= <， '小時'=> '克羅地亞語'， 'CS'=> '捷克'， 'DA'=> '丹麥'， 'NL'=>「荷蘭」， '網絡'=> '芬蘭'， 'FR'=> '法國'， '德'=> '德'， '厄爾尼諾'=> '希臘'， '喜'=> '印地文'， '它' => '意大利'， 'JA'=> '日本'， 'KO'=> '韓'， '無'=> '挪威'， 'PL'=> '波蘭'， 'PT'=> '葡萄牙' 'RO'=> '羅'， '儒'=> '俄羅斯'， 'ES'=> '西班牙語'， 'SV'=> '瑞典'， 'CA'=> '加泰羅尼亞語'， 'TL'= > '菲律賓'， 'IW'=> '希伯來語'， 'ID'=> '印度尼西亞'， 'LV'=> '拉脫維亞'， 'LT'=> '立陶宛語'， 'SR'=> '塞爾維亞語'， 'SK'=> '斯洛伐克語'， 'SL'=> '斯洛文尼亞語'， 'UK'=> '烏克蘭'， 'VI'=> '越南'， '平'=> '阿爾巴尼亞人'， '等'=> '愛沙尼亞語'， 'GL'=> '加利西亞語'， '虎'=> '匈牙利語'， 'MT'=> '馬耳他'， '日'=> '泰'， 'TR'=> '土耳其'，」 FA '=>' 波斯 ' 'AF'=> '語'， '毫秒'=> '馬來'， 'SW'=> '斯瓦希里'， 'GA'=> '愛爾蘭'， 'CY'=>'威爾士 ' '是'=> '白俄羅斯'， '是'=> '冰島'， 'MK'=> '馬其頓'， '義'=>' Y iddish'''hy'=>'亞美尼亞'，'az'=>'阿塞拜疆'，'eu'=>'巴斯克語'，'ka'=>'格魯吉亞語'，'ht'= >>

來源

2012-10-13 AgA

你能用文字解釋你想要哪個正則表達式匹配等嗎？ –

@martin clayton我已更新編輯 – AgA

Perl正則表達式不是特別聰明。您的模式通過回溯實現 - 基本上，在每個決策點（例如，未錨定的開始或{5,30}）中，正則表達式將其狀態保存在堆棧中，並以儘可能最小的匹配繼續前進。如果卡住了，它會彈出一個關卡。

通常情況下，這種方法工作得很好，因爲輸入的大小是有限的，在那裏有匹配的字面或字符類匹配以儘早切斷失敗的匹配，並且使用嵌套變量重複指令是有限的。另外，當回溯不存在時，可以將正則表達式轉換（理論上，儘管perl不這樣做）到確定性有限自動機中，這可以有效地執行。

在這裏，你有很多通配符匹配，一個很大的輸入字符串，加上什麼是有效的50迭代循環，中間有一個25層分支，周圍有一個循環來試圖找到開始和比賽結束。在最糟糕的情況下，你的正則表達式可能需要回溯25^50次，這甚至沒有考慮到缺少開始或結束錨點。

所以你需要弄清楚一個更聰明的方法來使這個算法的工作。嘗試僅生成字符串的每個4個字符的子字符串，並計算出現次數。對於不止一次出現的每個子字符串，檢查發現的匹配的偏移量以查看是否有模式。

來源

2012-10-13 09:50:32 bdonlan

在將長度從50縮小到30時，它可以穿過（m＃（？：（....）。{5,30}（？= \ 1））{ 30} #s） – AgA

@AgA，它仍然在回溯一噸，只是30意味着你有更多潛在的匹配方式（即它是一個較少約束的問題），因此尋找匹配解決方案所需的回溯較少。 – bdonlan

的一個好方法直觀地看到回溯其成本到你的正常表達Regexp::Debugger

好伴侶模型傑弗裏Friedl的「精通正則表達式」，它詳細討論了回溯。

來源

2012-10-13 13:36:27 JRFerguson

正則表達式掛起模式匹配

回答

相關問題