Regex挂起以进行模式匹配

Question

我有输入文件这里 (请解压)和下面的代码。就在打印“pat=\n”之后；它挂在模式匹配中，而我在(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‘=’s‘>’捷克语‘，’da‘=’>‘丹麦语’，‘nl’=‘Czech=’>‘荷兰语’，‘Czech=’Czech 2‘>’芬兰语‘，’fr‘>’法语‘，’de‘=’Czech=‘>’德文‘，’el‘=’Czech=‘Czech 3’>‘希腊语’，

行:打印"pat=\n"；打印以下内容并挂起：

pat=<，cs=‘cs 4’>‘cs=’cs 3‘>’cs=‘cs 3’>‘cs=’>‘cs=’cs=‘cs 3’>‘cs=’cs=‘>’cs=‘cs=’>‘cs=’>‘cs=’cs 3‘>’cs=‘>’cs=‘>’cs=‘cs=’cs 3‘>’cs=‘>’cs=‘cs 3’>‘cs=’‘ca=’ca 3‘>葡萄牙语，ca=’ca 3‘>罗马尼亚语，ca=’ca 3‘>俄语，ca=’ca 3‘>西班牙语，ca=’ca 3‘>瑞典语，ca=’ca 3‘>’加泰罗尼亚语，ca=‘ca=’ca 3‘>菲律宾人，ca=’ca=‘ca 3’>希伯来语，ca=‘ca 3’>印度尼西亚语，ca=‘lv’>拉脱维亚ca=‘>’ca=‘ca=’>‘ca=’>‘ca=’ca 3‘>’ca=‘>’ca=‘>’ca=‘ca 3’>‘ca=’>‘Irish=’Irish 3‘>’Irish=‘>’Irish=‘>’Irish=‘Irish=’Irish 3‘>’Irish=‘Irish=’>‘Irish=’Irish=‘>’Irish=‘>’Irish=‘Irish 3’>‘Irish=’Irish 3‘>’Irish=‘Irish=’>‘Irish=’>‘Irish=’Irish 3‘>’Irish=‘‘Welsh=’Welsh 3‘>’威尔士语，Welsh=‘Welsh 3’>白俄罗斯语，‘Welsh=’Welsh 3‘>’是‘冰岛语’，‘mk’=‘Welsh=’Welsh 3‘>’马其顿人‘，Welsh=’Welsh 2‘>’Welsh=‘Welsh 3’>‘Welsh=’Welsh 3‘>’Welsh=‘Welsh 5’>‘Welsh=’>‘Welsh=’>‘Welsh=’Welsh=‘Welsh 2’>‘Welsh=’>‘Welsh=

Answer 1

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

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

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

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

Answer 2

直观地查看回溯及其成本的一个好方法是使用Regexp：：调试器建模正则表达式。

一个很好的伙伴是Jeffrey的“掌握正则表达式”，它详细讨论了回溯。