正则表达式挂起模式匹配

Question

我有输入文件 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;
}

编辑:理想情况下，我想找出连续组(最多 50 个)中任何统一的字节重复模式(长度:4)，其中每个组的大小最大为 4+30 字节，最小为 4+5 字节。

例如(在每个大小为 1 到 30 字节的组中重复 '=>'):

'cs'=>'Czech','da'=>'Danish','nl'=>'Dutch','fi'=>'Finnish','fr'=>'French','de'=>'German','el'=>'Greek',

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

pat=<,'hr'=>'Croatian','cs'=>'Czech','da'=>'Danish','nl'=>'Dutch','fi'=>'Finnish','fr'=>'French','de'=>'German','el'=>'Greek','hi'=>'Hindi','it'=>'Italian','ja'=>'Japanese','ko'=>'Korean','no'=>'Norwegian','pl'=>'Polish','pt'=>'Portuguese','ro'=>'Romanian','ru'=>'Russian','es'=>'Spanish','sv'=>'Swedish','ca'=>'Catalan','tl'=>'Filipino','iw'=>'Hebrew','id'=>'Indonesian','lv'=>'Latvian','lt'=>'Lithuanian','sr'=>'Serbian','sk'=>'Slovak','sl'=>'Slovenian','uk'=>'Ukrainian','vi'=>'Vietnamese','sq'=>'Albanian','et'=>'Estonian','gl'=>'Galician','hu'=>'Hungarian','mt'=>'Maltese','th'=>'Thai','tr'=>'Turkish','fa'=>'Persian','af'=>'Afrikaans','ms'=>'Malay','sw'=>'Swahili','ga'=>'Irish','cy'=>'Welsh','be'=>'Belarusian','is'=>'Icelandic','mk'=>'Macedonian','yi'=>'Yiddish','hy'=>'Armenian','az'=>'Azerbaijani','eu'=>'Basque','ka'=>'Georgian','ht'=>>

Answer 1

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

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

在这里，您有很多通配符匹配项、一个大输入字符串，以及一个有效的 50 次迭代循环，中间有一个 25 层分支，周围有一个循环以尝试找到开始和结束比赛的。在最坏的情况下，您的正则表达式可能不得不回溯 25^50 次，这甚至没有考虑缺少开始或结束 anchor 。

因此，您需要想出一种更聪明的方法来使该算法发挥作用。尝试只生成字符串的每个 4 个字符的子字符串，并计算出现次数。对于出现不止一次的每个子字符串，检查找到的匹配项的偏移量以查看是否有您的模式。