正则表达式卡死问题

 最近在写个采集器调试过程中发现个别网页识别会卡很久,本来以为是网速问题,抓包看了下抓取正常,调试正则发现,一匹配就卡很久 cpu 占用也很高,最后确定是正则问题。

我是参考一下内容解决的,文章尾部有具体出处。

正则引擎匹配的过程:

概念说完了,下面开始讲过程。正则匹配时,有两条最重要的规则:

1、优先选择最左端的结果。

2、对标准匹配量词'{m,n}’、’+’、’*’、’?’优先使用贪婪模式。

例如:正则cat匹配"He captured a catfish for his cat."时,会匹配到catfish

那么,正则匹配的过程是怎么样的呢?[3]中讲解了一个详细的匹配过程,概括一下,就是从左到右每个字符依次匹配。

处理回溯:

在NFA正则匹配时,量词ca.*t等都可以使正则匹配出现多个选择:在匹配catfishfor his cat中的t时,是使用‘.*’还是‘t’i进行匹配? 一般情况下,正则表达式会按照规则2,优先贪婪匹配的,就是将t当作.*中的一个,然后匹配下一个字符t。而非贪婪模式下,会优先匹配’t’。但是无论哪种方式,都会留下另一种匹配的可能性,当匹配失败之后,仍然需要回到这个匹配点,尝试另一种可能。这就形成了回溯。

回到文章开始的地方,

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
var videoId2= 'XMTcyNTEzOTU2';
....此处约500行
<a title="转发到新浪微博" charset="400-03-10" id="s_sina"
684493555&amp;url=http://v.youku.com/v_show
/id_XMTcyNTEzOTU2.html&amp;title=%E5%8F%A4%E5%A2%93%E4%B8
%BD%E5%BD%B110%E5%91%A8%E5%B9%B4%E7%BA%AA%E5%BF%B5
%E7%89%88     %E8%A7%86%E9%A2%91%E5%85%A8%E6%94%BB%E7%95
%A5%E7%AC%AC%E4%B8%89%E9%9B%86&amp;ralateUid=1642904381&
amp;source=%E4%BC%98%E9%85%B7%E7%BD%91&amp;sourceUrl=http
%3A%2F%2     Fwww.youku.com%2F&amp;content=utf8"
target="_blank"&gt;&lt;img src="http://static.youku.com
/v1.0.0741/v/img/ico_sina.gif" /&gt;&lt;/a>;
                                                         
                                                         
...

可以看到,这里videoId2\\s*=\\s*'(.*?)’.*?很容易就匹配到了,然后s_sina匹配成功,但是后面的url=(.*?)&title=(.*?)&.*?也很容易就匹配成功,但是&pic=(.*?)没有了,然后匹配失败,不得已,只能继续搜索下面的,但是整个文章后面没有&pic了,所以本轮匹配失败,然后&title=会被回溯到下一个匹配点,然后继续回溯,直到尝试所有可能…统计了一下,整个文件s_sina出现6次,url出现24次,&title出现12次,所以基本上可以认为回溯了6*24*12次,而每次回溯都会匹配大半个文件。尝试将s_sina改为s_sina2(出现2次),运行时间变成了96632毫秒,大致符合假设。值得一提的是,经过测试,在匹配失败的情况下,贪婪模式和非贪婪模式的效率是没有明显区别的,将正则改为:

1
2
3
Pattern p = Pattern.compile("videoId2\\s*=\\s*'(.*)'.*" + //
  "s_sina.*url=(.*)&title=(.*)&.*?&pic=(.*)\"", Pattern.DOTALL);
Matcher m = p.matcher(html);

之后,运行时间为499551ms,与非贪婪模式的490760ms没有太大变化。

四、总结:

那么,最后的结论是什么呢?

个人观点,为了提高正则性能,最主要的还是仔细分析匹配的内容,尽量缩小匹配的范围。换成规范点的东西,就是尽量少用全字符 .,而使用[^]非结构。例如上面"s_sina.*url=(.*)&title=(.*)&.*?&pic=(.*)\""部分,整个匹配其实都是在一个<A>标签中进行,完全可以将所有.都换成[^<>],替换之后,在1416ms搞定(包括下载页面时间)。

其实呢,说到底,写这篇文章最主要的是想传达一个观念,正则这个东西的开销极大程度依赖于写的好不好,所以为了提高性能还是要仔细写的哦亲!

 

[1]精通正则表达式 Mastering Regular ExpressionsJeffrey E. F. Friedl

[2]http://zh.wikipedia.org/wiki/%E8%87%AA%E5%8A%A8%E6%9C%BA

本文引用内容出自:

http://progressdaily.diandian.com/post/how-regex-work

发表评论

您的电子邮箱地址不会被公开。