怎么理解回溯?回溯失控是什么?
正则表达式在匹配字符串时会从左到右测试表达式的组成部分,当遇到量词(* + ? {2})和分支(|)时需要做决策。
做出决策之后,可能会记录其它的选择,以备返回时使用。
如果当前匹配成功,则继续测试后面的表达式。如果都成功则结束。
如果当前找不到匹配值或者后面匹配失败,则正则表达式会回溯到最后一个决策点,并选择一个记录过的选择。
过程会一直进行,直到找到匹配项或者分支的排列组合全部失败。它将放弃匹配转而移动到字符串的下一个字符。
回溯失控是正则表达式导致浏览器假死的情况。
举一个例子:
用一个匹配标签的正则
let reg = /<html>[\s\S]*?<head>[\s\S]*?<title>[\s\S]*?<\/title>[\s\S]*?<\/head>[\s\S]*?<body>[\s\S]*?<\/body>[\s\S]*?<\/html>/
对字符串
let str = `<html><head><title></title></head><body></body>`
进行匹配,当最后一个[\s\S]*?扩展到字符串末尾,因为最后 html 闭合标签的缺失,正则表达式会尝试扩展到倒数第二个[\s\S]*?来匹配最后的 body 闭合标签,然后继续查找第二个闭合的 body 标签,直到字符串末尾,以此类推
惰性量词和贪婪量词
贪婪量词(*)表示重复 0 次或者多次,并尽可能匹配多次。
惰性量词(*?)会重复匹配 0 次会多次,并尽可能匹配 0 次
例子:
let reg1 = /<html>[\s\S]*?<\/html>/
let reg2 = /<html>[\s\S]*<\/html>/
let str = `<html><html>sdasds<\/html><\/html>`
str.match(reg1)//['<html><html>sdasds</html>']
str.match(reg2)//['<html><html>sdasds</html></html>']
使用正则表达式去除首尾空白?
使用两个正则
String.prototype.$trim = function() {
return this.replace(/^\s+/,"").replace(/\s+$/,"")
}
使用了两个子表达式,一个去除头部的空白,另一个去除尾部的空白。
相同的思路,可以用一个表达式
String.prototype.$trim = function() {
return this.replace(/^\s+|\s+$/g, "")
}
这个会比上面的方法要慢,因为两个分支选项在每个字符串匹配都会被测试一遍
使用捕获组
String.prototype.$trim = function() {
return this.replace(/^\s*([\s\S]*?)\s*$/, "$1")
}
捕获数组中的惰性量词会导致正则表达式进行回溯,因为[\s\S]类的惰性量词*?要求尽可能减少重复次数,因此正则表示式每匹配一个字符都要停下来尝试匹配剩下的\s*?。考虑一下优化方案
String.prototype.$trim = function() {
return this.replace(/^\s*([\s\S]*\S)?\s*$/, "$1")
}
考虑到上一个的性能原因,把惰性量词替换成了贪婪量词,为了保证捕获组匹配到最后的非空字符,末尾需要\S。
这个表达式的过程,[\s\S]*中的贪婪量词*表示重复任意字符类直到字符串末尾,然后正则表达式每次回溯一个字符,直到匹配到后面的\S,或者回溯到第一个字符。
不使用正则表达式
String.prototype.$trim = function() {
var start = 0,
end = this.length - 1
ws = " \n\r\t\f"
// 一些空白字符,不包括全部
while (ws.indexOf(this.charAt(start)) > -1) {
start ++
}
while (end > start && ws.indexOf(this.charAt(end)) > -1) {
end --
}
return this.slice(start, end + 1)
//slice方法返回的数组项不包括第二个参数下标的项
}
这个版本的优点是不受字符串总长度的影响,缺点是不宜处理前后大段的空白字符,因为循环遍历的效率比不上正则表达式。(记不全空白字符也是一个缺点)
混合解决方案
可以使用正则表达式过滤头部空白,使用非正则表达式的方法去除尾部字符
String.prototype.$trim = function() {
var str = this.replace(/^\s+/,""),
end = str.length - 1,
ws = /\s/;
while (ws.test(str.charAt(end))) {
end --
}
return str.slice(0,end + 1)
}
该方案在循环中使用一个正则表达式来检查字符串的末尾是否为空白,能直接使用浏览器定义的空白字符列表。
结论
在基于正则表达式的方案中,字符串的总长度比修剪掉的字符数量更加影响性能。非正则表达式从末尾开始查找,不受字符总长的影响,但是受到修剪空格数量的影响。
简单的使用两次正则是不错的方案,混合方案在处理长字符串的时候特别快,代价是代码稍长,在处理尾部长空白时稍有不足。
有哪些提高正则表达式效率的方法?
正则表达式以简单,必须的字元开始
好的起始标记通常是一个锚(^或$),特定字符串,字符类([a-z]或\d 速记符)。
避免以分组或者选择字元开头/one|two/
减少分支数量,缩小分支范围
可以通过使用字符集来减少对分支的需求比如将(.|\r|\n)替换成[\s\S],因为字符集比分支更快。当分支必不可少时,将常用分支放在最前面,这样可能可以被尽快检测到。
使用非捕获数组
捕获数组小号时间和内存记录反向引用
只捕获感兴趣的文本以减少后续处理
如果需要引用匹配的一部分,应该捕获那些必要的部分再用反向引用处理。
比如需要匹配引号括起来的字符串内容,应该使用/“([^"]*)"/
而不是/“[^"]*“/再从结果中处理引号。
使用合适的量词
贪婪和惰性量词的匹配过程有很大的区别
将正则表达式赋值给变量并重用
避免在循环体内重复编译正则表达式
将复杂正则表达式拆分成简单的片段
比如去除首尾空字符的两次 replace