正则式表达式是每个工程师都应该熟练掌握的工具，特别是前端包含着很多的数据表单的验证。正则表达式虽然功能强大，但其灵活多变，两个正则表达式匹配相同的文本并不意味着他们具有相同的速度，粗浅地编写正则表达式是造成性能瓶颈的主要原因。
《高性能JavaScript编程》中，介绍了正则表达式的优化，非常值得仔细学习。
##正则表达式优化
许多因素影响正则表达式的效率。首先，正则表达式适配的文本千差万别，部分匹配时比完全不匹配所用的时间要长。每种浏览器的正则表达式引擎也有不同的内部优化。
###正则表达式原理
- 编译
- 设置起始位置
- 匹配每个正则表达式的字元
- 匹配成功或失败
##回溯
回溯是匹配过程的基本组成部分，也是影响整体性能的唯一因素。
产生回溯的两种主要方式为量词和分支，量词分为贪婪量词和懒惰量词。
可以看到虽然贪婪量词和懒惰量词的结果可以一样，但其过程却是不同的。
回溯失控
看下面的正则表达式1
/<html>[\s\S]*?<head>[\s\S]*?<title>[\s\S]*?</title>[\s\S]*?<\/head>[\s\S]*?<body>[\s\S]*?<\/body>[\s\S]*?<\/html>/
此正则表达式匹配正常 HTML 字符串时工作良好，但是如果目标字符串缺少一个或多个标签时，它就变得十分糟糕。例如</html>标签缺失，那么最后一个[\s\S]*?将扩展到字符串的末尾，但那里没有发现</html>标签，之后正则表达式将查看此前的[\s\S]\*?队列记录的回溯位置，使它们进一步扩大。之后尝试扩展到第二个[\s\S]*?，依次类推，有点像往贪婪的方向进行，进行了大量的回溯。
解决方法
具体化，最大化的去限定范围，尽可能具体地指出分隔符之间的字符匹配形式，减少回溯。
1 | /<html>(?:(?!<head>)[\s\S])*<head>(?:(?!<title>)[\s\S])*<title> (?:(?!<\/title>)[\s\S])*<\/title>(?:(?!<\/head>)[\s\S])*<\/head> (?:(?!<body>)[\s\S])*<body>(?:(?!<\/body>)[\s\S])*<\/body> (?:(?!<\/html>)[\s\S])*<\/html>/ |
虽然上面使用了非捕获组、负向前瞻（(?!exp)匹配后面不是exp的位置）来消除潜在的回溯失控，并允许正则表达式匹配不完整的HTML字符串失败时，其使用时间与文本长度呈线性关系，但是其效率并没有提高。当匹配一个HTML 文件可能需要前瞻并测试上千次。
使用前瞻和后向引用列举原子组。一些正则表达式一种称作支持原子组（(?>...)）的属性，该属性可以丢弃原子组中正则表达式组中的任何回溯点。但 JavaScript 不支持该属性，不过你可以利用前瞻过程中一项鲜为人知的行为来模拟原子组：前瞻也是原子组。不同的是,前瞻在整个匹配过 程中,不消耗字符;它只是检查自己包含的模板是否能在当前位置匹配。然而,你可以避开这点,在捕获 组中包装一个前瞻模板,在前瞻之外向它添加一个后向引用。它看起来是下面这个样子:
1 | (?=(原子组表达式))\1 |
使用该技术后的
1 | /<html>(?=([\s\S]*?<head>))\1(?=([\s\S]*?<title>))\2(?=([\s\S]*? <\/title>))\3(?=([\s\S]*?<\/head>))\4(?=([\s\S]*?<body>))\5 (?=([\s\S]*?<\/body>))\6[\s\S]*?<\/html>/ |
现在如果没有尾随的</html>那么最后一个[\s\S]*?将扩展至字符串结束，正则表达式将立刻失败因为没有回溯点可以返回。正则表达式每次找到一个中间标签就退出一个前瞻，它在前瞻过程中丢弃所有回溯位 置。下一个后向引用简单地重新匹配前瞻过程中发现的字符，将他们作为实际匹配的一部分
###嵌套量词和回溯失控
使用(x+)*这样的表达式时，需要格外主要回溯失控的问题。假如你想匹配 HTML 标签，使用下面的正则表达式
1 | /<(?:[^>"']|"[^"]*"|'[^']*')*>/ |
这里看到非捕获组的第一个分支[^>'"]，每次只匹配一个字符，似乎效率低下。你可能认为在后面加一个+量词会好些，这样每次重复过程就可以匹配多余一个的字符。但会带来显而易见的负面效果。如果匹配一个< 但后面没有 > 却可以令匹配完成，回溯失控，内部量词和外部量词排列组合产生了数量巨大的分支路径（跟在非捕获组之后）用以匹配 > 之后的文本。正则表达式在最终放弃匹配之前尝试所有的排列组合。
关于嵌套量词导致回溯有个更极端的例子， 在一大串 A 上应用 /(A+A+)+B/，虽然写成 /AA+B/ 更好。当应用10个A组成的字符串上，正则表达式首先使用A+匹配了所有10个字符，然后回溯一个字符，让第二个A+匹配最后一个字符，然后这个分组试图重复，但是没有更多的A而且分组中的+量词已经符合匹配所需的最少一次，因此正则表达式开始查找B，虽然失败，但匹配会继续进行。两个A+的组合不计其数，只要两次之和可以被10整除即可，最坏情况的复杂度为O(2^n)。当n=25时，足以使浏览器崩溃。
预防此类问题的关键是确保正则表达式的两个部分不能对字符串的同一部分进行匹配，比如写成/AA+B/，但复杂的正则表达式可能难以避免此类问题，还可以增加一个模拟原子组来消除回溯，比如/((?=(A+A+))\2)+B/
###提高正则表达式效率的更多办法
- 关注如何让匹配更快失败。正则表达式处理慢往往因为是匹配失败过程慢，而不是匹配成功慢。如果修改使正则表达式使匹配成功更快但失败更慢，这通常是一个失败的修改。
- 正则表达式以简单的，必需的字元开始。最理想的情况，应当尽可能快速地测试并排除明显不匹配的位置。用于此目的好的起始字元通常是一个锚（^或$）,特定字符（x或\u363A）,字符类（例如，[a-z]或速记符如\d），和单词边界（\b）。如果可能的话，避免以分组或选择字元开头，避免顶级分支例如
/one|/two，因为它强迫正则表达式识别多种起始字元。 - 编写量词模板，使它们后面的字元互相排斥。尽量具体化你的模板，当你想表达
[^"\r\n]*时不要使用.*?（依赖回溯）。 减少分支的数量，缩小它们的范围。通常可通过使用字符类和选项组减少对分支的需求。
Insteand of | Use
— | —
cat|bat | [cb]at
red|read | rea?d
red|raw r(?:ed|aw)
(.|\r|\n) | [\s\S]字符类比分支更快，因为他们使用位向量实现而不是回溯。当分支必不可少时，将常用分支放在最前面，因为分支选项从左向右进行匹配。
- 使用非捕获组。捕获组花费时间和内存用于记录向后引用，并保持它们是最新的。
- 捕获感兴趣的文字，减少后处理。比如想匹配引号中的字符串内容，使用
/"[^"]*"/，然后使用一次向后引用，而不是使用/"[^"]*"/然后从结果中手工剥离引号。 - 暴露所需的字元。为了帮助正则表达式引擎在如何优化查询例程时做出明智的决策，应尽量简单地判断出那些必需的字元。当字元应用在子表达式或者分支中，正则表达式引擎很难判断他们是不是必需的。比如
/^(ab|cd)/暴露它的字符串起始锚，而/(^ab|^cd)/不暴露它的^锚。 - 使用适当的量词。贪婪量词和懒惰量词即使匹配同样的字符串，其查找匹配过程也是不同的。使用合适的量词类型，可以显著提高性能。
- 将正则表达式赋给变量，以重用它们。避免在循环体重重复编译正则表达式。
- 将复杂的正则表达式拆分成简单的片段。