正则表达式三种模式：贪婪模式、懒惰模式、独占模式
周末快到了，今天为⼤家送上⼀篇很有意思的⼩⽂章，具有提神醒脑之功效。作者是来⾃阿⾥巴巴LAZADA产品技术部的申徒童鞋。
1. ⾎案由来
近期我在为Lazada卖家中⼼做⼀个⾃助注册的项⽬，其中的shop name校验规则较为复杂，要求：
1. 英⽂字母⼤⼩写
2. 数字
3. 越南⽂
4. ⼀些特殊字符，如“&”，“-”，“_”等
看到这个要求的时候，⾃然⽽然地想到了正则表达式。于是就有了下⾯的表达式（写的⽐较龊）：
1. ^([A-Za-z0-9._()&'\- ]|
[aAàÀảẢãÃáÁạẠăĂằẰẳẲẵẴắẮặẶâÂầẦẩẨẫẪấẤậẬbBcCdDđĐeEèÈẻẺẽẼéÉẹẸêÊềỀểỂễỄếẾệỆfFgGhHiIìÌỉỈĩĨíÍịỊjJkKlLmMnNoOòÒỏỎõÕóÓọỌôÔồỒổỔỗỖốỐộỘơƠờỜởỞỡỠớỚợỢpPqQrRsStTuUùÙủỦũŨúÚụỤư
在测试环境，这个表达式从功能上符合业务⽅的要求，就被发布到了马来西亚的线上环境。结果上线之后，发现线上机器时有发⽣CPU飙到100%的情况，导致整个站点响应异
常缓慢。通过dump线程trace，才发现线程全部卡在了这个正则表达式的校验上：regex匹配
⼀开始难以置信，⼀个正则表达式的匹配过程怎么可能引发CPU飚⾼呢？抱着怀疑的态度去查了资料才发现⼩⼩的正则表达式⾥⾯竟然⼤有⽂章，平时写起来都是浅尝辄⽌，只
要能够满⾜功能需求，就认为达到⽬的了，完全忽略了它可能带来的性能隐患。
引发这次⾎案的就是所谓的正则“回溯陷阱（Catastrophic Backtracking）”。下⾯详细介绍下这个问题，以避免重蹈覆辙。
2. 正则表达式引擎
说起回溯陷阱，要先从正则表达式的引擎说起。正则引擎主要可以分为基本不同的两⼤类：⼀种是DFA（确定型有穷⾃动机），另⼀种是NFA（不确定型有穷⾃动机）。简单来
讲，NFA 对应的是正则表达式主导的匹配，⽽ DFA 对应的是⽂本主导的匹配。
DFA从匹配⽂本⼊⼿，从左到右，每个字符不会匹配两次，它的时间复杂度是多项式的，所以通常情况下，它的速度更快，但⽀持的特性很少，不⽀持捕获组、各种引⽤等等；
⽽NFA则是从正则表达式⼊⼿，不断读⼊字符，尝试是否匹配当前正则，不匹配则吐出字符重新尝试，通常它的速度⽐较慢，最优时间复杂度为多项式的，最差情况为指数级
的。但NFA⽀持更多的特性，因⽽绝⼤多数编程场景下（包括java，js），我们⾯对的是NFA。以下⾯的表达式和⽂本为例，
1. text ＝‘after tonight’ regex ＝‘to(nite|nighta|night)’
在NFA匹配时候，是根据正则表达式来匹配⽂本的，从t开始匹配a，失败，继续，直到⽂本⾥⾯的第⼀个t，接着⽐较o和e，失败，正则回退到 t，继续，直到⽂本⾥⾯的第⼆个
t，然后 o和⽂本⾥⾯的o也匹配，继续，正则表达式后⾯有三个可选条件，依次匹配，第⼀个失败，接着⼆、三，直到匹配。
⽽在DFA匹配时候，采⽤的是⽤⽂本来匹配正则表达式的⽅式，从a开始匹配t，直到第⼀个t跟正则的t匹配，但e跟o匹配失败，继续，直到⽂本⾥⾯的第⼆个 t 匹配正则的t，接着
o与o匹配，n的时候发现正则⾥⾯有三个可选匹配，开始并⾏匹配，直到⽂本中的g使得第⼀个可选条件不匹配，继续，直到最后匹配。
可以看到，DFA匹配过程中⽂本中的字符每⼀个只⽐较了⼀次，没有吐出的操作，应该是快于NFA的。另外，不管正则表达式怎么写，对于DFA⽽⾔，⽂本的匹配过程是⼀致
的，都是对⽂本的字符依次从左到右进⾏匹配，所以，DFA在匹配过程中是跟正则表达式⽆关的，⽽ NFA 对于不同但效果相同的正则表达式，匹配过程是完全不同的。
3. 回溯
说完了引擎，我们再来看看到底什么是回溯。对于下⾯这个表达式，相信⼤家很清楚它的意图，
1. ab{1,3}c
也就是说中间的b需要匹配1~3次。那么对于⽂本“abbbc”，按照第1部分NFA引擎的匹配规则，其实是没有发⽣回溯的，在表达式中的a匹配完成之后，b恰好和⽂本中的3个b完整
匹配，之后是c发⽣匹配，⼀⽓呵成。如果我们把⽂本换成“abc”呢？⽆⾮就是少了⼀个字母b，却发⽣了所谓的回溯。匹配过程如下图所⽰（橙⾊为匹配，黄⾊为不匹配），
1~2步应该都好理解，但是为什么在第3步开始，虽然已经⽂本中已经有⼀个b匹配了b{1,3}，后⾯还会拉着字母c跟b{1,3}做⽐较呢？这个就是我们下⾯将要提到的正则的贪婪特性，也就是说b{1,3}会竭尽所能的匹配最多的字符。在这个地⽅我们先知道它⼀直要匹配到撞上南墙为⽌。在这种情况下，第3步发⽣不匹配之后，整个匹配流程并没有⾛完，⽽是像栈⼀样，将字符c吐出来，然后去⽤正则表达式中
的c去和⽂本中的c进⾏匹配。这样就发⽣了⼀次回溯。
4. 贪婪、懒惰与独占
我们再来看⼀下究竟什么是贪婪模式。
下⾯的⼏个特殊字符相信⼤家都知道它们的⽤法：
i. ?: 告诉引擎匹配前导字符0次或⼀次。事实上是表⽰前导字符是可选的。
ii. +: 告诉引擎匹配前导字符1次或多次。
iii. *: 告诉引擎匹配前导字符0次或多次。
iv. {min, max}: 告诉引擎匹配前导字符min次到max次。min和max都是⾮负整数。如果有逗号⽽max被省略了，则表⽰max没有限制；如果逗号和max都被省略了，则表⽰重复min次。
默认情况下，这个⼏个特殊字符都是贪婪的，也就是说，它会根据前导字符去匹配尽可能多的内容。这也就解释了为什么在第3部分的例⼦中，第3步以后的事情会发⽣了。
懒惰模式，在该模式下，正则引擎尽可能少的重复匹配字符，匹配成功之后它会继续匹配剩余的字符
串。在上例中，如果将正则换在以上字符后加上⼀个问号（？）则可以开启懒惰模式
为
1. ab{1,3}?c
则匹配过程变成了下⾯这样（橙⾊为匹配，黄⾊为不匹配），
由此可见，在⾮贪婪模式下，第2步正则中的b{1,3}?与⽂本b匹配之后，接着去⽤c与⽂本中的c进⾏匹配，⽽未发⽣回溯。
独占模式。同贪婪模式⼀样，独占模式⼀样会匹配最长。不过在独占模式下，正则表达式尽可能长地去匹配字符串，⼀如果在以上四种表达式后加上⼀个加号（+），则会开启独占模式
旦匹配不成功就会结束匹配⽽不会回溯。我们以下⾯的表达式为例，
1. ab{1,3}+bc
如果我们⽤⽂本"abbc"去匹配上⾯的表达式，匹配的过程如下图所⽰（橙⾊为匹配，黄⾊为不匹配），
可以发现，在第2和第3步，b{1,3}+会将⽂本中的2个字母b都匹配上，结果⽂本中只剩下⼀个字母c。那么在第4步时，正则中的b和⽂本中的c进⾏匹配，当⽆法匹配时，并不进⾏回溯，这时候整个⽂本就⽆法和正则表达式发⽣匹配。如果将正则表达式中的加号（+）去掉，那么这个⽂本整体就是匹配的了。
把以上三种模式的表达式列出如下，
贪婪懒惰独占
X?X??X?+
X*X*?X*+
X+X+?X++
X{n}X{n}?X{n}+
X{n,}X{n,}?X{n,}+
X{n,m}X{n,m}?X{n,m}+
5. 总结
现在再回过头看看⽂章开头的那个很长的正则表达式，其实简化之后，就是⼀个形如
1. ^[允许字符集]+
的表达式。该字符集⼤⼩约为250，⽽+号表⽰⾄少出现⼀次。按照上⾯说到的NFA引擎贪婪模式，在⽤户输⼊⼀个过长字符串进⾏匹配时，⼀旦发⽣回溯，计算量将是巨⼤的。后来采⽤了独占模式，CPU 100%的问题也得到了解决。
因此，在⾃⼰写正则表达式的时候，⼀定不能⼤意，在实现功能的情况下，还要仔细考虑是否会带来性能隐患。
关于正则表达式，你有哪些想要分享的特殊技能？欢迎在下⾯留⾔，⼀起交流探讨。
转载⾃：wwwblogs/study-everyday/p/7426862.html
因怕这么好的⽂章因为⽹站问题或者被⼈恶意rm了就赶紧转载到⾃⼰的博客中了,⽂章nice

版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。