x-note
Search…
正则表达式的悲观回溯
正则表达式中*表示匹配日前面的子表达式0次或多次(且尽可能多的匹配)。
假设有正则表达式/^(a*)b$/a和字符串aaaaab
二者匹配,此时捕获组(a*)捕获到的字符串为aaaaa
改写正则表达式为/^(a*)ab$/
此时与字符串依然匹配,但是捕获到的字符串为aaaa
仔细剖析这个表达式/^(a*)ab$/的匹配过程:
  1. 1.
    匹配开始,(a*)匹配尽可能多的字符a
  2. 2.
    (a*)一直捕获,直到遇到字符b。此时(a*)已经捕获了aaaaa
  3. 3.
    正则表达式继续执行(a*)之后的ab匹配,此时字符串仅剩一个b,导致无法完成匹配;
  4. 4.
    (a*)当前捕获的字符串中”吐出“一个字符a,这时捕获结果为aaaa,剩余字符串为ab;
  5. 5.
    重新执行正则中的ab匹配。完成匹配。捕获组捕获结果为aaaa
暂时的无法匹配并不会立即导致整体匹配的失败。而是会从捕获组中吐出字符后继续尝试,直到成功或者完全失败。这个“吐出“的过程就叫做回溯
假设这个表达式/^(a*)b$/匹配字符串aaaaaa.
尽管能够一眼看出来无法匹配,但是正则表达式依旧会逐一回溯所有可能性,才能确定最终结果。这中“傻傻的”回溯过程就叫做悲观回溯
这种悲观回溯,很可能会导致性能问题。

解决方案

1. 禁止回溯

有两种语法可以防止回溯
  • 有限量词
  • 原子分组
不过在 JavaScript 中均不被支持

2. 避免导致性能问题的回溯

以下两种模式的正则表达式很可能导致有性能问题的回溯
  • 前后重复模式,例如/x*x*/
  • 嵌套量词,例如/(x*)*/

3. 不使用正则

例如匹配字符串aaaaa,bbbbbb,ccccc,分割的部分,使用split()对字符串进行切割即可,还能保证代码的性能是线性的。

4. 避免性能问题影响页面响应

在必须使用正则表达式,且这个表达式有潜在的性能问题的情况下。可以吧匹配操作放到 Service Worker 中进行。尽量的不影响页面响应