正则基础之——贪婪与非贪婪模式  转自：百度空间
3      贪婪还是非贪婪模式——再谈匹配效率
在正则表达式中.*和.*?是经常会用到的，可是具体的匹配过程很多人并不是很清楚。这里首先介绍一下他们的匹配过程，一般再这两个模式后面都还会带有其他的需要匹配的表达式，比如.*(a)和.*?(a)这两种正则表达式匹配下面的字符串：res/drawable/l  Side-by-Side Unified
.*(a)的匹配是先匹配的字符串的结尾，然后在字符串的末尾向前回溯一直到出现a的位置得到匹配的结果：res/drawable/add_ca；而.*?(a)表达式由于？的存在表示非贪婪所以将优先权让给a去进行匹配，a匹配到第一个a出现的位置停止，所以结果是：res/dra。
这个匹配过程在很多正则应用是很重要的，所以希望自己能记住，所以做了这个文本，也希望对大家有些帮助。
下面是一些其他的更具体的介绍：
一般来说，贪婪与非贪婪模式，如果量词修饰的 子表达式相同，比如“.*”和“.*?”，它们的应用场景通常是不同的，所以效率上一般不具有可比性。
而对于改变量词修饰的子表达式，以满足需 求时，比如把“.*”改为“[^”]*”，由于修饰的子表达式已不同，也不具有直接的可对比性。但是在相同的子表达式，又都可以满足需求的情况下，比如 “[^”]*”和“[^”]*?”，贪婪模式的匹配效率通常要高些。
同时还有一个事实就是，非贪婪模式可以实现的，通过优化量词修饰的子表达式 的贪婪模式都可以实现，而贪婪模式可以实现的一些优化效果，却未必是非贪婪模式可以实现的。
贪婪模式还有一点优势，就是在匹配失败时，贪婪模式 可以更快速的报告失败，从而提升匹配效率。下面将全面考察贪婪与非贪婪模式的匹配效率。
3.1    效率提升——演进过程
在 了解了贪婪与非贪婪模式的匹配基本原理之后，我们再来重新看一下正则效率提升的演进过程。
需求：取得两个“””中的子串，其中不能再包含 “””。
源字符串：The phrase "regular expression" is called "Regex" for short.
正则表达式一：”.*”
正则表达式一匹配的内容为“"regular expression" is called "Regex"”，不符合要求。
提出正则表达式二：”.*?”
首先“””取得控制权，由位置0位开始尝试匹配，直到位置11处匹配成 功，控制权交给“.*?”，匹配过程同2.2.1中非贪婪模
式的匹配过程。“.*?”匹配的内容为“Regex”，匹配过程中进行了四次回溯。
如 何消除回溯带来的匹配效率的损失，就是使用更小范围的子表达式，采用贪婪模式，提出正则表达式三：”[^”]*”
首先“””取得控制权，由位置 0位开始尝试匹配，直到位置11处匹配成功，控
制权交给“[^”]*”，匹配过程同2.2.2节中非贪婪模式的匹配过程。“[^”]*”匹配的内容为 “Regex”，匹配过程中没有进行回溯。
3.2    效率提升——更快的报告失败
以上讨论的是匹配成功的演进过 程，而对于一个正则表达式，在匹配失败的情况下，如果能够以最快的速度报告匹配失败，也会提升匹配效率，这或许是我们设计正则过程中最容易忽略的。而在源 字符串数据量非常大，或正则表达式比较复杂的情况下，是否能够快速报告匹配失败，将对匹配效率产生直接的影响。
下面将构建匹配失败的正则表达 式，对匹配过程进行分析。
以下匹配过程分析中，源字符串统一为：The phrase "regular expression" is called "Regex" for short.
3.2.1  非贪婪模式匹配失败过程分析
图3-1
构建匹配失败的非贪婪模式的正则表达式：”.*?”@
由 于最后的“@”的存在，这个正则表达式最后一定是匹配失败的，那么看一下匹配过程。
首先由“””取得控制权，由位置0处开始尝试匹配，匹配失 败，直到图中标示的A处匹配成功，控制权交给“.*?”。
“.*?”取得控制权后，由A后面的位置开始尝试匹配，由于是非贪婪模式，首先忽略匹 配，将控制权交给“””，同时记录一下回溯状态。“””取得控制权后，由A后面的位置开始尝试匹配，匹配字符“r”失败，查可供回溯的状态，将控制权交 给“.*?”，由“.*?”匹配字符“r”。重复以上过程，直到“.*?”匹配了B处前面的字符“n”，“””匹配了B处的字符“””，将控制权交给 “@”。由“@”匹配接下来的空格“ ”，匹配失败，查可供回溯的状态，控制权交给“.*?”，由“.*?”匹配空格。继续重复以上匹配过程，直到由“.*?”匹配到字符串结束位置，将控制 权交给“””。由于已经是字符串结束位置，匹配失败，报告整个表达式在位置11处匹配失败，一轮匹配尝试结束。正则匹配是什么
正则引擎传动装置使正则向前传 动，进入下一轮尝试。后续匹配过程与第一轮尝试匹配过程基本类似，可以参考图3-1。
从匹配过程中可以看到，非贪婪模式的匹配失败过程，几乎每 一步都伴随着回溯过程，对匹配效率的影响是很大的。
3.2.2  贪婪模式匹配失败过程分析——大范围子表达式
图3-2
注：以上分析过程图示参考了《精通正则表达式》一书相关章节图 示。
构建匹配失败的贪婪模式的正则表达式：”.*”@
其中量词修饰的子表达式为匹配范围较大的“.”，由于最后的“@”的存在，这个 正则表达式最后也是一定匹配失败的，看一下匹配过程。
首先由“””取得控制权，由位置0处开始尝试匹配，匹配失败，直到图中标示的A处匹配成
功，控制权交给“.*”。
“.*”取得控制权后，由A后面的位置开始尝试匹配，由于是贪婪模式，优化尝试匹配，一直匹配到字符串的结束位置，将 控制权交给“””。“””取得控制权后，由于已经是字符串的结束位置，匹配失败，查可供回溯的状态，将控制权交给“.*”，由“.*”让出已匹配字符 “.”。重复以上过程，直到后面“””匹配了C处后面的字符“””，将控制权交给“@”。由“@”匹配接下来D处的空格“ ”，匹配失败，查可供回溯的状态，控制权交给“.*”，由“.*”让出已匹配文本。继续重复以上匹配过程，直到由“.*”让出所有已匹配的文本到I处， 将控制权交给“””。“””匹配失败，由于已经没有可供回溯的状态，报告整个表达式在位置11处匹配失败，一轮匹配尝试结束。
正则引擎传动装置 使正则向前传动，进入下一轮尝试。后续匹配过程与第一轮尝试匹配过程基本类似，可以参考图3-2。
从匹配过程中可以看到，大范围子表达式贪婪模 式的匹配失败过程，从总体上看，与非贪婪模式没有什么区别，最终进行的回溯次数与非贪婪模式基本一致，对匹配效率的影响仍然很大。
3.2.3  贪婪模式匹配失败过程分析——改进的子表达式
图3-3
构建匹配失败的贪婪模式的正则表达式：”[^”]*”@
其 中量词修饰的子表达式，改为匹配范围较小的排除型字符组“[^”]”，由于最后的“@”的存在，这个正则表达式最后也是一定匹配失败的，看一下匹配过程。
首先由“””取得控制权，由位置0处开始尝试匹配，匹配失败，直到图中标示的A处匹配成功，控制权交给“[^”]*”。
“[^”]*” 取得控制权后，由A后面的位置开始尝试匹配，由于是贪婪模式，优先尝试匹配，一直匹配到B处，将控制权交给“””。“””匹配接下来的的字符“””，匹配 成功，将控制权交给“@”。由“@”匹配接下来的空格“ ”，匹配失败，查可供回溯的状态，控制权交给“[^”]*”，由“[^”]*”让出已匹配文本。继续重复以上匹配过程，直到由“[^”]*”让出所有已 匹配的文本到C处，将控制权交给“””。“””匹配失败，由于已经没有可供回溯的状态，报告整个表达式在位置11处匹配失败，一轮匹配尝试结束。
正 则引擎传动装置使正则向前传动，进入下一轮尝试。后续匹配过程与第一轮尝试匹配过程基本类似，可以参考图3-3。
从匹配过程中可以看到，使用了 排除型字符组的贪婪模式的匹配失败过程，从总体上看，大量减少了每轮回溯的次数，可以有效的提升匹配效率。
3.2.4  贪婪模式匹配失败过程分析——固化分组
通过3.2.3节的分析可
以知道，由于“[^”]*”使用了排除型字符组，那么图3-3中，在A和B之 间被匹配到的字符，就一定不会是字符“””，所以B到C之间回溯过程就是多余的，也就是说在这之间的可供回溯的状态完全可以不记录。.NET中可以使用固 化分组，Java中可以使用占有优先量词来实现这一效果。
图3-4
首先由“””取得控制权，由位置0处开始尝试匹配，匹配失败， 直到图中标示的A处匹配成功，控制权交给“(?>[^”]*)”。
“(?>[^”]*)”取得控制权后，由A后面的位置开始尝试匹 配，由于是贪婪模式，优先尝试匹配，一直匹配到B处，将控制权交给“””，在这一匹配过程中，不记录任何可供回溯的状态。“””匹配接下来的字符“””， 匹配成功，将控制权交给“@”。由“@”匹配接下来的空格“ ”，匹配失败，查可供回溯的状态，由于已经没有可供回溯的状态，报告整个表达式在位置11处匹配失败，一轮匹配尝试结束。
正则引擎传动装置使 正则向前传动，进入下一轮尝试。后续匹配过程与第一轮尝试匹配过程基本类似，可以参考图3-4。
从匹配过程中可以看到，使用了固化分组的贪婪模 式的匹配失败过程，没有涉及到回溯，可以最大限度的提升匹配效率。
3.3    非贪婪模式向贪婪模式的转换
使用匹 配范围较大的子表达式时，贪婪模式与非贪婪模式匹配到的内容会有所不同，但是通过优化子表达式，非贪婪模式可以实现的匹配，贪婪模式都可以实现。
比 如在实际应用中，匹配img标签的内容。
举例：
需求：取得img标签中的图片地址，src=后固定为“””
源字符 串：<img class=”test” src=”/img/logo.gif” title=”测试” />
正则表达式 一：<img\b.*?src=”(.*?)”.*?>
匹配结果中，捕获组1的内容即为图片地址。可以看到，这个例子中使用的都是 非贪婪模式，而根据上面章节的分析，后面两个非贪婪模式都可以使用排除型字符组，将非贪婪模式转换为贪婪模式。
正则表达式 二：<img\b.*?src=”([^”]*)”[^>]*>
注：“src=”…””和标签结束标记符“>”之间的 属性中，也可能出现字符“>”，但那是极端情况，这里不予讨论。
后两处非贪婪模式，可以通过排除型字符组转换为贪婪模式，提高匹配效率， 而“src=”前的非贪婪模式，由于要排除的是一个字符序列“src=”，而不是单独的某一个或几个字符，所以不能使用排除型字符组。当然也不是没有办 法，可以使用顺序环视来达到这一效果。
正则表达式三：<img\b(?:(?!src=).)*src=”([^”]*)”[^& gt;]*>
“(?!src=).”表示这样一个字符，从它开始，右侧不能是字符序列“src=”，而“(?:(?!src=).)*” 就表示符合上面规则的字符，有0
个或无限多个。这样就达到排除字符序列的目的，实现的效果同排除型字符组一样，只不过排除型字符组排除的是一个或多个字 符，而这种环视结构排除的是一个或多个有序的字符序列。
但是以顺序环视的方式排除字符序列，由于在匹配每一个字符时，都要进行较多的判断，所以 相对于非贪婪模式，是提升效率还是降低效率，要根据实际情况进行分析。对于简单的正则表达式，或是简单的源字符串，一般来说是非贪婪模式效率高些，而对于 数量较大源字符串，或是复杂的正则表达式，一般来说是贪婪模式效率高些。
比如上面取得img标签中的图片地址需求，基本上用正则表达二就可以 了；对于复杂的应用，如平衡组中，就需要使用结合环视的贪婪模式了。
以匹配嵌套div标签的平衡组为例：
Regex reg = new Regex(@"(?isx)                      #匹配模式，忽略大小写，“.”匹配任意字符
<div[^>]*>                      #开始标记“&>”
(?>                        #分组构造，用来限定量词“*”修饰范围
<div[^>]*>  (?<Open>)  #命名捕获组，遇到开始标记，入栈，Open计数加1
|                          #分支结构
</div>  (?<-Open>)      #狭义平衡组，遇到结束标记，出栈，Open计数减1
|                          #分支结构
(?:(?!</?div\b).)*      #右侧不为开始或结束标记的任意字符
)*                          #以上子串出现0次或任意多次
(?(Open)(?!))              #判断是否还有'OPEN'，有则说明不配对，什么都不匹配
</div>                          #结束标记“</div>”
");
“(?:(?!</?div\b).)*”这里使用的就是结合环视的贪婪模式，虽然每匹一个字符都要做很多判断，但这种判断是基于字符 的，速度很快，而如果这里使用非贪婪模式，那么每次要做的就是分支结构“|”的判断了，而分支结构是非常影响匹配效率的，其代价远远高于对确定字符的判 断。而另外一个原因，就是贪婪模式可以结合固化分组来提升效率，而对非贪婪模式使用固化分组却是没有意义的。
4      贪婪与非贪婪——最后的回顾
4.1    一个例子的匹配原理回顾
再回过头来看一下2.1.1节例子中正则，前面从应用角度进行了分析，但讨论过匹配原理后会发现，匹配过程并不是那么简单的，下面从匹配原理角 度分析的匹配过程。
图4-1
首先由“<”取得控制权，由位置0位开始尝试匹配，匹配 字符“a”，匹配失败，第一轮匹配结束。第二轮匹配从位置1开始尝试匹配，同样匹配失败。第三轮从位置3开始尝试匹配，匹配字符“<”，匹配成功， 控制权交给“d”。
“d”尝试匹配字符“d”，匹配成功，控制权交给“i”。重复以上过程，直到由“>”匹
配到字符“>”，控制权 交给“.*”。
“.*”属于贪婪模式，将从B处后的字符“t”开始，一直匹配到E处，也就是字符串结束位置，将控制权交给“<”。
“<” 从字符串结束位置尝试匹配，匹配失败，向前查可供回溯的状态，把控制权交给“.*”，由“.*”让出一个字符“c”，把控制权再交给“<”，尝试 匹配，匹配失败，向前查可供回溯的状态。一直重复以上过程，直到“.*”让出已匹配的字符“<”，实际上也就是让出了已匹配的子串 “</div>cc”为止，“<”才匹配字符“<”成功，控制权交给“/”。
接下来由“/”、“d”、“i”、“v” 分别匹配对应的字符成功，此时整个正则表达式匹配完毕。
4.2    贪婪与非贪婪——量词的细节
4.2.1  区间量词的非贪婪模式
前面提到的非贪婪模式，一直都是使用的“*?”，而没有涉及到其它的区间量词，对 于“*?”和“+?”这样的非贪婪模式，大多
数接触过正则表达式的人都可以理解，但是对于区间量词的非贪婪模式，比如“{m,n}?”，要么是没见过，要 么是不理解，主要是这种应用场景非常少，所以被忽略了。
首先需要明确的一点，就是量词“{m,n}”是匹配优先量词，虽然它有了上限，但是在达 到上限之前，能够匹配，还是要尽可能多的匹配的。而“{m,n}?”就是对应的忽略优先量词了，在可匹配可不匹配的情况下，尽可能少的匹配。
接 下来举一个例子说明这种非贪婪模式的应用。
举例（参考 限制字符长度与最小匹配）：
需求：如何限制在长度为100的字符串中，从头匹 配到最先出现的abc
csdn.{1,100}abc 这样写是最大匹配(1-100个字符串中，我需要最小的)
比如 csdnfddabckjdsfjabc，匹配结果应为：csdnfddabc
正则表达式：csdn.{1,100}?abc
或许对 这个例子还有人不是很理解，但是想想，其实“*”就等价于“{0,}”，“+”就等价于“{1,}”，“*?”也就是“{0,}?”，抽象出来也就是 “{m,}?”，即上限为无穷大。如果上限为一个固定值，那就是“{m,n}?”，这样应该也就可以理解了。
“{m}”没有放在匹配优先量词 中，同样的，“{m}?”虽然被部分语言所支持，但是也没有放在忽略优先量词中，主要是因为这两种量词，实现的效果是一样的，只有被修饰的子表达式匹配m 次才能匹配成功，且没有可供回溯的状态，所以也不存在是匹配优先还是忽略优先的问题，也就不在本文的讨论范围内。事实上即使讨论也没有意义的，只要知道它 们的匹配行为也就是了。
4.2.2  忽略优先量词的匹配下限
对于匹配优先量词的匹配下限很好理解，“?”等价于 “{0,1}”，它修饰的子表达式，最少匹配0次，最多匹配1次；“*”等价于“{0,}”

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