为什么正则表达式完成3000行的XML文件非常慢？

Question

我注意到Regex用3000行完成XML文件的速度很慢[1]:

\(<Annotation\(\s*\w\+="[^"]\{-}"\s\{-}\)*>\)\@<=\(\(<\/Annotation\)\@!\_.\)\{-}"MATCH\_.\{-}\(<\/Annotation>\)\@=

我一直以为Regexes很有效率.为什么完成正则表达式需要这么长时间？

[1] 如何在VIM中重复匹配A到B？

Answer 1

如果它是有效的,它取决于正则表达式本身.它效率低下的是回溯.为避免这种情况,正则表达式必须尽可能明显.

我们以正则表达式a.*b为例,将其应用于字符串abcdef.该算法将首先匹配文本a中a.*b的a中abcdef.接下来.*将处理表达式.在正常贪婪模式,在乘数膨胀到最大,它会匹配到所有的剩余bcdef在abdef.比上字面b的a.*b将被处理.但是,由于已经到达字符串的末尾并且正在使用mulpliplier,算法将尝试回溯以匹配整个模式..*(bcdef)的匹配将减少一个字符(bcde),并且算法尝试遵守模式的其余部分.但是,b在a.*b没有该不匹配f的abcdef.所以.*将减少一个字符,直到它匹配空字符串(因此.重复零次)并且bin a.*b匹配bin abcdef.

正如您所看到的,a.*b应用于abdef需要6个回溯方法,.*直到整个正则表达式匹配.但是如果我们改变正则表达式并通过使用a[^b]*b而使其变得明显,则不需要回溯,并且正则表达式可以在第一种方法中匹配.

如果您现在考虑使用延迟修饰符,我会告诉您,此规则适用于每个修饰符,包括贪婪修饰符和延迟修饰符.不同之处在于,首先将匹配扩展到最大值,而不是通过一次减少一个字符(贪婪)来进行回溯,延迟修饰符将首先扩展到最小匹配,而不是一次增加一个字符.