2

我在这里有输入文件（请提取它）和下面的代码。就在 print "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;
}

编辑：理想情况下，我想找出连续组（最多 50 个）中任何统一的字节重复模式（长度：4），其中每个组的大小可以是最大 4+30 字节和最小 4+5 字节。

例如（在每组大小 1 到 30 个字节中重复 '=>'）：

'cs'=>'捷克语','da'=>'丹麦语','nl'=>'荷兰语','fi'=>'芬兰语','fr'=>'法语','de'=> '德语','el'=>'希腊语',

该行：打印“pat=\n”；打印以下内容并挂起：

pat=<,'hr'=>'克罗地亚语','cs'=>'捷克语','da'=>'丹麦语','nl'=>'荷兰语','fi'=>'芬兰语',' fr'=>'法语','de'=>'德语','el'=>'希腊语','hi'=>'印地语','it'=>'意大利语','ja'=>'日语','ko'=>'韩语','no'=>'挪威语','pl'=>'波兰语','pt'=>'葡萄牙语','ro'=>'罗马尼亚语','ru '=>'俄语','es'=>'西班牙语','sv'=>'瑞典语','ca'=>'加泰罗尼亚语','tl'=>'菲律宾语','iw'=>'希伯来语','id'=>'印尼语','lv'=>'拉脱维亚语','lt'=>'立陶宛语','sr'=>'塞尔维亚语','sk'=>'斯洛伐克语','sl'=>'斯洛文尼亚语','uk'=>'乌克兰语','vi'=>'越南语' ,'sq'=>'阿尔巴尼亚语','et'=>'爱沙尼亚语','gl'=>'加利西亚语','hu'=>'匈牙利语','mt'=>'马耳他语','th'= >'泰语','tr'=>'土耳其语','fa'=>'波斯语','af'=>'南非荷兰语','ms'=>'马来语','sw'=>'斯瓦希里语', 'ga'=>'爱尔兰','cy'=>'威尔士','be'=>'白俄罗斯','is'=>'冰岛','mk'=>'马其顿','yi'=> '意第绪语','hy'=>'亚美尼亚语','az'=>'阿塞拜疆','eu'=>'巴斯克','ka'=>'格鲁吉亚','ht'=>>

4

2 回答 2

5

Perl 正则表达式并不是特别聪明。您的模式是通过回溯实现的 - 基本上，在每个决策点（例如，未锚定的开始或{5,30}），正则表达式将其状态保存在堆栈中，并以尽可能小的匹配继续前进。如果它被卡住，它会从堆栈中弹出一个级别。

通常这工作得很好，因为输入的大小是有限的，那里有文字或字符类匹配可以及早切断失败的匹配，并且嵌套变量重复指令的使用是有限的。此外，当不存在回溯时，正则表达式可以转换（理论上，尽管 perl 不这样做）为确定性有限自动机，可以有效地执行。

在这里，你有很多通配符匹配，一个大的输入字符串，加上一个有效的 50 次迭代循环，中间有一个 25 层分支，围绕它的循环试图找到匹配的开始和结束. 在最坏的情况下，您的正则表达式可能不得不回溯 25^50 次，这甚至没有考虑缺少开始或结束锚点。

所以你需要想出一个更聪明的方法来使这个算法工作。尝试只生成字符串的每个 4 个字符的子字符串，并计算出现次数。对于出现多次的每个子字符串，检查找到的匹配项的偏移量，看看您是否有您的模式。

于 2012-10-13T09:50:32.123 回答
1

直观地查看回溯及其成本的一个好方法是使用Regexp::Debugger为您的正则表达式建模

Jeffrey Friedl 的“精通正则表达式”是一个很好的伴侣，它详细讨论了回溯。

于 2012-10-13T13:36:27.573 回答