概述
转自：点击打开链接
正则表达式原理及性能研究报告
一、一个正则引发的血案：
前几天在更新的时候，监控到线上服务器的CPU占用非常高，响应速度也变慢了很多，后来大家检查才发现，竟然卡在正则匹配那里了。因为网站的视频分享是用正则表达式分析页面的，而刚好前一天优酷的网站改了格式，结果正则匹配就卡死了。这个正则是这么写的（反正现在也没用了，贴出来做个反面教材）：
|
1
2
3
|
Pattern p = Pattern.compile(
"videoId2\s*=\s*'(.*?)'.*?"
+
//
"s_sina.*?url=(.*?)&title=(.*?)&.*?&pic=(.*?)""
, Pattern.DOTALL);
Matcher m = p.matcher(html);
|
后来，本着研究的态度，我对这个正则进行了本地测试，用于分析优酷页面："http://v.youku.com/v_show/id_XMTcyNTEzOTU2=.html"。经过漫长的等待，终于在490760毫秒之后，匹配失败了。
由此可见，正则表达式的效率必须重视。在优化之前，需要先了解它的原理。完成这篇文章，主要参考了《精通正则表达式》[1]这本书。这方面的参考资料本来也不太多，这本书算是比较全面了，不过讲得稍微啰嗦了点。
二、正则表达式引擎：
正则表达式的匹配都是通过正则表达式引擎实现的。正则表达式引擎分为两类：基于NFA ( Nondeterministic Finite Automata，非确定型有穷状态自动机)和基于DFA ( Deterministic Finite Automaton，确定型有穷状态自动机)的引擎。关于自动机理论，可以简单参考维基百科[2]。DFA和NFA的区别在于，DFA对于一个状态和一个输入，一定会有一个唯一的后续状态，而NFA可能有多个状态，也可能没有。一般来说，DFA正则在编译的时候花的时间会多一点，但是在匹配的时候会更快一点。NFA出现较早，JAVA、.NET、php、Ruby、Perl、Python、GNU Emacs、ed、sec、vi、grep都是使用NFA，而DFA只有egrep awk lex flex这些支持。NFA引擎在生产环境里使用较多，重点介绍一下。
三、正则引擎匹配的过程：
概念说完了，下面开始讲过程。正则匹配时，有两条最重要的规则：
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"
href="http://v.t.sina.com.cn/share/share.php?
appkey
=
2
684493555&
url
=
http
://v.youku.com/v_show
/id_XMTcyNTEzOTU2.html&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&
ralateUid
=
1642904381
&
amp;source=%E4%BC%98%E9%85%B7%E7%BD%91&
sourceUrl
=
http
%3A%2F%2 Fwww.youku.com%2F&
content
=
utf8
"
target
=
"_blank"
><img src="http://static.youku.com
/v1.0.0741/v/img/ico_sina.gif" /></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
[3]http://www.regular-expressions.info/engine.html最后
以上就是失眠宝贝为你收集整理的正则表达式原理及性能研究报告的全部内容，希望文章能够帮你解决正则表达式原理及性能研究报告所遇到的程序开发问题。
如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。
发表评论 取消回复