回溯是如何产生的?
当遇到限定符时便会产生回溯,限定符例如*,+,?,{2,3}。并且懒惰回溯与贪婪回溯的规则也是不同的。下面将举例说明懒惰回溯与贪婪回溯的区别。
懒惰回溯
目标字符串: <p>Zhui.</p>
贪婪量词:<p>.*</p>
- <
- <p
- <p>
- <p>Zhui.</p>
- <p>Zhui.</p>(回溯)
- <p>Zhui.</p
- <p>Zhui.</p(回溯)
- <p>Zhui.</
- <p>Zhui.</(回溯)
- <p>Zhui.<
- <p>Zhui.<(回溯)
- <p>Zhui.
- <p>Zhui.<
- <p>Zhui.</
- <p>Zhui.</p
- <p>Zhui.</p>
懒惰回溯
目标字符串:<p>Zhui.</p>
懒惰量词:<p>.*?</p>
- <
- <p
- <p>
- <p>(0长度匹配)
- <p>(回溯)
- <p>Z
- <p>Z(回溯)
- <p>Zh
- <p>Zh(回溯)
- <p>Zhu
- <p>Zhu(回溯)
- <p>Zhui
- <p>Zhui(回溯)
- <p>Zhui.
- <p>Zhui.<
- <p>Zhui.</
- <p>Zhui.</p
- <p>Zhui.</p>
回溯失控
当我们想要匹配一个html代码,我们可能会写出这样的正则
<html>.*?<head>.*?<title>.*?<\/title>.*?<\/head>.*?<body>.*?<\/body>.*?<\/html>
正常情况下匹配是良好的,但若是文本缺失一个</html>标签,则会引发疯狂的回溯导致回溯失控。
解决回溯失控
/<html>(?:(?!<head>).)*<head>(?:(?!<title>).)*<title>)(?:(?!<\/title>).)*</title>(?:(?!<\/head>).)*)<\/head>(?:(?!<body>).)*<body>(?:(?!<\/body>).)*<\/body>(?:(?!<\/html>).)*<\/html>/
该方式使用了预查的方式解决了回溯失控的问题,当匹配失败时不会引发回溯失控,但每次触发预查还是会影响性能。
更好的方式
使用预查和反向引用模拟的原子组
(?=(pattern to make atomic))\1
/<html>(?=(.*?<head>))\1(?=(.*?<title>))\2(?=(.*?<\/title>))\3(?=(.*?<\/head>))\4(?=(.*?<body>))\5(?=(.*?<\/body>))\6.*?<\/html>/
当缺少最后一个html标签,最后一个.*会展开至结尾处,因为没有可返回的回溯点。正则每找到一个标签,就退出一个预查,并在预查过程中丢弃回溯位置。反向引用简单的匹配预查中发现的字符,并将它们作为实际匹配的一部分。