分类
regex

正则-消除不必要的回溯

回溯是如何产生的?

当遇到限定符时便会产生回溯,限定符例如*,+,?,{2,3}。并且懒惰回溯与贪婪回溯的规则也是不同的。下面将举例说明懒惰回溯与贪婪回溯的区别。

懒惰回溯

目标字符串: <p>Zhui.</p>

贪婪量词:<p>.*</p>

  1. <
  2. <p
  3. <p>
  4. <p>Zhui.</p>
  5. <p>Zhui.</p>(回溯)
  6. <p>Zhui.</p
  7. <p>Zhui.</p(回溯)
  8. <p>Zhui.</
  9. <p>Zhui.</(回溯)
  10. <p>Zhui.<
  11. <p>Zhui.<(回溯)
  12. <p>Zhui.
  13. <p>Zhui.<
  14. <p>Zhui.</
  15. <p>Zhui.</p
  16. <p>Zhui.</p>

懒惰回溯

目标字符串:<p>Zhui.</p>

懒惰量词:<p>.*?</p>

  1. <
  2. <p
  3. <p>
  4. <p>(0长度匹配)
  5. <p>(回溯)
  6. <p>Z
  7. <p>Z(回溯)
  8. <p>Zh
  9. <p>Zh(回溯)
  10. <p>Zhu
  11. <p>Zhu(回溯)
  12. <p>Zhui
  13. <p>Zhui(回溯)
  14. <p>Zhui.
  15. <p>Zhui.<
  16. <p>Zhui.</
  17. <p>Zhui.</p
  18. <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标签,最后一个.*会展开至结尾处,因为没有可返回的回溯点。正则每找到一个标签,就退出一个预查,并在预查过程中丢弃回溯位置。反向引用简单的匹配预查中发现的字符,并将它们作为实际匹配的一部分。

分类
regex

正则表达式-判断不具有某些字段的字符串

做了一个安全中心项目,里面有一些密码验证,比较难的部分就是验证是否不具有某些字段的字符串了。

/^((?!boy|gril).)*$/

解析

/^((?!boy|gril).)*$/

这个星星举足轻重,有了它我们才能从开始到结尾,每一个位置都进行一次正则判定。

/^((?!boy|gril).)*$/

这个小点举足轻重,有了它才有了占位符,有了占位符才能做零宽度负预测先行断言(负前瞻,向后看看是否是我们不想要的内容,若是我们不想要的内容,则不通过此次正则判定)

/^((?!boy|gril).)*$/

负前瞻

/^((?!boy|gril).)*$/

如果没有开始它无法进行负预测,如果没有结尾它只要有一个位置符合后面没有boy或gril就会生效。

执行过程

  • 在^处判定后方是否有boy或gril,无保留占位符,
  • 在^.处判定后方是否有boy或gril
  • ……
  • 在^….$处判定后方是否有boy或gril,无,执行结束

在上方的某个步骤中判定中出现了boy或gril,则不符合正则的条件,跳出并返回false

(完)

2020-10-27补充

上述正则判断的是字符串在不具有boy的同时也不具有girl,要是我们想要判断的是可以有girl和boy但两者只能出现一个。

第一种情况,先遇到boy后不遇到gril

/^(?=(.boy))\1((?!gril).)$/

第二种情况,先遇到gril后不遇到boy

/^(?=(.gril))\1((?!boy).)$/

最终情况,遇到boy后不遇到gril或者遇到gril后不遇到boy结合在一起

/^((?=(.boy))\1((?!gril).)|(?=(.gril))\1((?!boy).))$/