碳基体

奋斗在产品安全第一线的安全妹子

NFA引擎正则优化TIPS、Perl正则技巧及正则性能评测方法

一、性能优化Tips

1. 优先选择最左端的匹配结果


2.标准量词优先匹配

比如'.*[0-9][0-9]' 来匹配字符串"abcd12efghijklmnopqrstuvw",这时候的匹配方式是‘.*’先匹配了整行,但是不能满足之后的两个数字的匹配,所以‘.*’就退还一个字符‘w’,还是无法匹配,继续退还一个‘v’,循环退还字符到‘2’发现匹配了一个,但是还是无法匹配两个数字,所以继续退还‘1’


3.谨慎使用捕获性括号(),选择使用非捕获性括号(?:expression)

捕获性括号需要消耗一部分内存


4.使用字符组代替分支(替换)条件

例如用[a-d] 代替 a|b|c|d避免不必要的回溯


5.不要滥用字符组(单个字符时不要用字符组)

\. 代替 [.]


6.使用锚点^ $ \b 加速定位


7.从两次中提取必须元素

a{2,4} 写成 aa{0,2}


8.提取多选结构开头的相同字符

the|this 改成th(?:e|is)


9.选择字符串中最常出现的字符串放到分支最前面


10.能懒则懒,不要贪婪

在 * + {m,n}后面加上问好?就会变成非贪婪模式


总结:引用CFC4N大牛的一句话 滥用. 点号  * 星号  +加号  ()括号 是不环保,不负责任的做法 !


11.简单字符串处理应避免使用正则表达式


二、Perl正则技巧

1)仅需分组时,用非捕获括号

圆括号在perl正则表达式中,有分组和捕获的作用

在split中使用非捕获括号,以关闭分隔符保留模式

让处理器花时间去捕获不需要的子字符串是一种浪费


2)能懒则懒,不要贪婪

perl正则表达式默认返回能找到的最左最长匹配

在 * + {m,n}后面加上问好?就会变成非贪婪模式


3)用零宽断言匹配字符串中的特定位置

用\b判断单词与非单词之间的边界

用\A或 \z匹配字符串的绝对起始或绝对末尾

在多行模式(/m)下,用^或$分别匹配每一行文本的行首或行尾


4)避免不必要的回溯

(1)用字符组[abc]代替多选结构

(2)避免量词*引起的不必要回溯

在任意量词后面加一个+号,该量词就变成占有优先量词,占有优先量词包括 *+  ++ ?+ {m,n}+ {m,}+ 目前仅Java和PCRE支持


5)仅编译正则表达式一次

可在正则表达式中用/o标示只需编译一次,但如果正则表达式中使用了内插变量(/$a/) ,需酌情考虑


6)预编译正则表达式

使用qr//操作符预编译正则表达式,用eval检测模式非法的正则表达式,如下所示

my $name = '(';
my $regex = eval { qr/\b$name\b/ } or die "Regex failed : $@";

由于左括号没有配对,所以报错

Regex failed : Unmatched ( in regex; marked by <-- HERE in m/\b( <-- HERE \b/ at ./re_qr.pl line 6.


7)正则表达式的调试及性能评测

使用use re ‘debugcolor’开启调试

benchmark模块比较正则表达式的效率

例子见三、正则调试及评测方法


8)不要滥造正则表达式,使用已封装好的常用正则表达式模块

use Regexp::Common;

例子见四、常用的正则匹配



三、正则调试及评测方法

1. 调试

以调试贪婪与懒惰模式为例

#!/usr/bin/perl
use strict;
use warnings;
use feature qw(say);
use re 'debugcolor';

my $re1 = '<div>.+</div>'; #贪婪匹配
my $re2 = '<div>.+?</div>';# 懒惰匹配

my $str = '<div>testtest</div><div>testtest2</div>';

$str =~ /$re1/;

$str =~ /$re2/;

运行结果

 有上图可以看出来,perl默认开启贪婪匹配模式,.+会一直定位到字符串末尾,然后开始往前回溯。


2.计算正则花费时间

以贪婪与懒惰模式为例

#!/usr/bin/perl
use strict;
use warnings;
use Time::HiRes qw(gettimeofday time);

my $str = "<div>testtest</div><div>testtest2</div>" x 10000;

my $re1 = '<div>.+</div>';

my $re2 = '<div>.+?</div>';


#计算<div>.+</div>花费时间

my $starttime = time();
         
$str =~ /$re1/;
         
my $endtime = time();
my $time_cost = $endtime - $starttime;
printf( "$re1 time costs:  %.6f seconds.\n",$time_cost);

#计算<div>.+?</div>花费时间
my $starttime2 = time();
    
$str =~ /$re2/;

my $endtime2 = time();
    
my $time_cost2 = $endtime2 - $starttime2;
    
printf("$re2 time costs: %.6f seconds . \n",$time_cost2);


运行结果

这里只是简单地进行估算,如果要更准确,需要多次计算花费时间,如下文介绍的。 


3. 正则性能计算

以查找拥有10w条访问日志的lighttpd 服务器为例

#!/usr/bin/perl
use strict;
use warnings;

use Benchmark qw(:all);

my @data = <>;

timethese(
     -5,
    {


        mem => q{
            foreach (@data){
                 /(\w+(\.\w+)+)/;
            }
        },

        memfree => q{
            foreach (@data){
                /(\w+(?:\.\w+)+)/;
            }
        },

    }


);


运行结果如下:

 测试拥有记录

 
 捕获性

四、Regexp::Common常用的正则匹配

以 匹配IP地址为例

#!/usr/local/bin/perl
use strict;
use warnings;
use Regexp::Common qw (net);

while (<>){
    chomp $_;
    print "$_ IPv4 address \n" if /$RE{net}{IPv4}/;
    print "$_ IPv6 address \n" if /$RE{net}{IPv6}/;

}

运行结果如下:

 



参考:

CFC4N 的PPT〈正则表达式〉

《perl高效编程》

《perl最佳实践》

正则cheatsheets 


来源:碳基体