转自：点击打开链接
正则表达式原理及性能研究报告
一、一个正则引发的血案：
前几天在更新的时候，监控到线上服务器的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"
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
"
/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 原文链接：https://www.f2er.com/regex/362036.html