高性能的正则表达式效率优化

  • Post author:
  • Post category:其他



前言

编写高性能的正则表达式,有如下几条规则,这几条规则是本人总结出来的:

1、使用正确的边界匹配器(^、$、\b、\B等)

2、使用具体的元字符、字符类(\d、\w、\s等)

3、使用正确的量词(+、*、?、{n,m})

4、使用非捕获组、原子组

5、注意量词的嵌套

其实正则表达式的很多优化技巧都是围绕着“减少回溯”这样一个原则进行优化的。

至于什么是“回溯”,笔者就不在这里重复了,以下通过具体的例子理解这样的过程。


示例

一、以下是一则匹配电子邮件地址的正则表达式:

^\w+([\.-]?\w+)*@\w+([\.-]?\w+)*(\.\w{2,3})+$

先一步步的解析:

1、^\w+:表示必须以字符

开始

, 且是一个或者多个;

2、([\.-]?\w+)*中的“[\.-]?”表示匹配“.”或者“-”,零次或者一次;

3、([\.-]?\w+)*中的“\w+”则表示匹配一个或者多个的字符;

4、([\.-]?\w+)*整个则表示匹配.xxx、-xxx或者xxx这样的字符,且零次或者多次;

5、第1-4步,则匹配sunny或者sunny.yang这样的字符;

6、“@”则是具体元,匹配具体的@;

7、 \w+:则表示匹配的一个或者多个的字符,因为email不可能这样嘛:sunny@.gmail.com;

8、 ([\.-]?\w+)*:则跟第2-4步一样,匹配.163、-lib、.gd这样的字符,且零次或者多次;

9、 (\.\w{2,3})+$:则匹配.com、.cc这样

结尾

的域名,且因为\w{2,3}限定了长度必须为2-3位,所以不能匹配.c、.n这样的字符。

乍看这样一个解析过程没问题,逻辑正确,但其实暗藏很多问题,看看以下的一个匹配图,backtrack则表示回溯(使用RegexBuddy可以很清晰的看到这过程)

整个成功的匹配过程经历了55步,我们先分析下整个匹配过程:

1、图中的第1和2步,匹配^\w+,匹配成功,匹配了“admin”;

2、图中第3步,匹配[\.-]?,当然由于不存在“.”和“-”,因此没匹配上具体的字符,但又由于“?”的限定,可以匹配零或者一次,因此这个子表达式匹配成功,虽然没匹配上具体的字符。

3、图中第4步,匹配\w+,由于“+”限定一个或者多个以上字符,但后续已经没[a-zA-Z0-9]可以匹配了,因此产生回溯,回溯到上次匹配成功的位置,也就admin;

4、图中第5步,因为上一步产生了回溯,所以“[\.-]?\w+”匹配了零次,由于([\.-]?\w+)*中限定零次或者多次,因此也匹配成功,也没匹配上具体的字符;

以下步骤,匹配该过程:

^\w+([\.-]?\w+)*@\w+([\.-]?\w+)*(\.\w{2,3})+$

5、图中第6步,匹配了“@” ,第7步匹配了“\w+”,即匹配了“open”;

6、图中第8-13步,匹配“([\.-]?\w+)*” ,匹配了“-lib”、“.com”,匹配“.com”可能与我们期望不相符,我们期望这子表达式匹配的是www.xx.gd.cn中的“.gd”;

7、图中第7-10步,匹配了open-lib,第7-13步则匹配了open-lib.com;

8、因为“([\.-]?\w+)*”中的量词是“*”,则继续重复这个过程;

9、 图中第14步,匹配“([\.-]?\w+)*”中的“[\.-]?”,因为此时指针已经位于@open-lib.com之后了,但由于量词“?”,因此也匹配成功,但没匹配上字符,也没字符可匹配;

10、 图中第15步,匹配“([\.-]?\w+)*”中的“\w+”,此时指针仍位于字符串末尾,没任何字符能匹配,所以匹配失败,产生回溯,回到上次成功的位置,即图中的第13步,继续下个表达式的匹配;

11、 图中第16步,匹配(\.\w{2,3})+中的“\.”,由于没有任何字符能匹配,匹配失败,进行回溯;

12、图中第17步 ,(\.\w{2,3})+中量词“+”,表示该表达式必须匹配一次或者多次,由于上一步匹配失败了,所以匹配零次,但不符合一次或者多次的限定,因此继续回溯;

13、由于上一步匹配失败,需要进行回溯,因此表达式没有更多的分支了,只能将指针回退一个字符,回溯上次成功的位置,即([\.-]?\w+)*中\w+的位置(这是上次产生分支的位置);

14、图中剩下的步骤,就重复着匹配([\.-]?\w+)*,回退字符,匹配(\.\w{2,3})+这样的过程,直到匹配成功。

二、以下看看另外一则同样匹配邮件地址的正则表达式:

^\w+([-\.]\w+)*@\w+([-\.]\w+)*\.\w+([-\.]\w+)*$

这个正则跟上面的看起来貌似差不多,不过细看还是有区别的,也先一步步来解析:

1、^\w+:表示必须以字符

开始

, 且是一个或者多个(这一步与上面的一样);

2、 ([-\.]\w+)*中的“[-\.]”表示匹配“-”或者“.”;

3、 ([-\.]\w+)*中的“\w+”则表示匹配一个或者多个的字符;

4、([-\.]\w+)*整个则表示匹配.xxx、-xxx这样的字符,且零次或者多次;

5、第1-4步,则匹配sunny或者sunny.yang这样的字符;

6、“@”则是具体元,匹配具体的“@”;

7、 \w+:则表示匹配的一个或者多个的字符,因为email不可能这样嘛:sunny@.gmail.com;

8、([-\.]\w+)*:则跟第2-4步一样,匹配.163、-lib、.gd这样的字符,且零次或者多次;

9、“\.”则是具体元,匹配“.”;

10、\w+:则匹配一个或者多个字符;

11、([-\.]\w+)*:则匹配“.com”、“-lib”、“.c”这样的字符,且可以零次或者多次;

12、$ :则表示结尾

乍看这个正则的步骤过程貌似比上一则长,其实不然,同时这个正则也存在着问题,先看看匹配图,同样backtrack表示回溯:

对的,你没看错,整个正确的匹配过程用了

19

步,对比前面的

55

步,简直天与地的差别。,我们继续分析下匹配过程:

1、图中的第1和2步,匹配^\w+,匹配成功,匹配了“admin”;

2、图中第3步,匹配[-\.],当然由于不存在“.”和“-”,因此没匹配上具体的字符,

也没具体的量词允许匹配零次

,所以不用继续往下匹配了,因此直接产生了回溯;

3、图中第4步,因为上一步产生了回溯,所以“[-\.]\w+”匹配了零次,由于([-\.]\w+)*中限定零次或者多次,因此也匹配成功,也没匹配上具体的字符;

以下步骤,匹配该过程:

^\w+([-\.]\w+)*@\w+([-\.]\w+)*\.\w+([-\.]\w+)*$

4、图中第6步\w+,匹配了open;

5、图中第7-12步匹配([-\.]\w+)*,匹配了“-lib”和“.com”;

6、因为“([-\.]\w+)*”中的量词是“*”,则继续重复这个过程;

7、图第13步,匹配([-\.]\w+)* ,因为此时指针已经位于@open-lib.com之后了,

也没具体的量词允许匹配零次

,因此匹配失败,回溯到上次成功的位置;

8、图第14步,匹配 ([-\.]\w+)*$中的“[-\.]”,此时指针仍位于字符串末尾,没任何字符能匹配,所以匹配失败,产生回溯,回到

上次成功且还没尝试过

的位置,即图中的第9步;

9、经过上面的回溯,指针已经位于@open-lib之后的位置了;

10、图第15步匹配了“.”,第16步\w+则匹配了“com” ;

11、图第17步匹配([-\.]\w+)*,由于此时指针又位于字符串末尾,因此[-\.]部分没匹配上任何字符,因此产生回溯;

12、图第18步,由于 ([-\.]\w+)*的量词是“*”,表示匹配零次或多次,虽然子表达式[-\.]匹配失败,所以整个表达式匹配了零次,也是匹配成功;

13、最后一步第19步,“$”表示末尾匹配,因为此时指针位于字符串末尾,故符合,因此也匹配成功。


分析

整个匹配过程关键优化地方,还是回溯,两个示例表达式看起来相近,匹配过程也部分类似,但两个例子的效率却如此大的分别,现在来分析一下造成回溯的原因。

对比下两个表达式不同的部分:

^\w+([\.-]?\w+)*@\w+([\.-]?\w+)*(\.\w{2,3})+$

^\w+([\.-]\w+)*@\w+([\.-]\w+)*\.\w+([-\.]\w+)*$

转载于:https://my.oschina.net/u/3147332/blog/807081