JS正则引擎NFA回溯机制与trim性能优化

NFA引擎机制与性能问题

通常情况下，正则表达式的编写方式如下：

当处理包含大量数据的变长字符串时，上述写法会暴露出资源消耗过大、效率低下的问题，甚至在某些场景下性能差到无法接受。

<!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.01//EN" "http://www.w3.org/TR/html4/strict.dtd"><html><head><meta http-equiv="Content-Type" content="text/html; charset=utf-8" /><title></title><meta http-equiv="Pragma" content="no-cache" /> <meta http-equiv="Cache-Control" content="no-cache" /> <meta http-equiv="Expires" content="0" /><meta http-equiv="ImageToolbar" content="no" /><style type="text/css" title="default" media="screen">/*<![CDATA[*//*]]>*/</style></head><body><textarea>请在这里写足够多的空格或者tab字符。<&#47textarea></body></html>

在剖析这一现象的原因时，联想到《Master Regular Expression》一书中曾提及NFA（非确定有限状态自动机）与DFA（确定有限状态自动机）引擎的区别。JavaScript、Perl、PHP、Java以及.NET等主流语言的正则引擎均属于NFA类型。

DFA与NFA在机制上的差异主要带来以下五点影响：

1. DFA对文本串中的每个字符仅需扫描一次，速度较快但功能特性较少；NFA则需要反复“吃”入和“吐”出字符，速度较慢但功能丰富，因此应用更为广泛。当今主要的正则表达式引擎，包括Perl、Ruby、Python的re模块、Java和.NET的regex库，均采用NFA架构。

2. 只有NFA引擎才支持lazy（惰性）匹配和backreference（后向引用）等高级特性；

3. NFA倾向于尽快匹配成功，因此遵循“最左子正则式优先”原则，这可能导致错过最佳匹配结果；而DFA遵循“最长的左子正则式优先”原则。

4. NFA默认采用greedy（贪婪）量词，即对于类似/.*/、/\w+/这样的重复模式，会尽可能多地匹配字符，直到不得不为止，NFA会优先处理量词部分。

5. NFA可能会陷入递归调用的陷阱，导致性能表现极差。

backtracking（回溯）

当NFA发现自己匹配过多时，会逐个字符地“吐”出来，边吐边寻找匹配，这个过程称为backtracking（回溯）。由于存在这一机制，在NFA匹配过程中，尤其是编写不合理的正则表达式时，文本会被反复扫描，造成显著的效率损失。理解这一原理对于编写高效的正则表达式至关重要。

回溯原理与原因分析

定位/分析原因

在解释前述trim原型方法时，经过测试发现，无论结果是否正确，有几种方法可以有效减少JS NFA引擎的回溯次数：

a. 去掉限定的量词，即改为：

String.prototype.trim = function () {
return this.replace(/^[\s\t ]+|[\s\t ]$/g, '');
}

b. 去掉字符串尾部的匹配。即改为：

String.prototype.trim = function () {
return this.replace(/^[\s\t ]+/g, '');
} 

c. 加入多行匹配模式。即改为：

String.prototype.trim = function () {
return this.replace(/^[\s\t ]+|[\s\t ]+$/mg, '');
}

结合上述三种改法以及前文关于NFA的资料，我们可以大致推断出trim性能出现问题的根本原因。

量词限定会优先进行匹配。

量词限定在字符串末尾可能会导致JS正则引擎不断进行回溯，从而陷入递归陷阱。如果递归深度过深，对于更大的字符串可能会出现栈溢出错误。

多行模式既然能够匹配且性能消耗不大，说明在性能上没有明显问题。从编写正则程序的角度来看，多行模式显然比单行模式替换的空串更多。因此，第二点的结论应该是正确的。

正则与常规方法结合的改良方案

改良

首先确定匹配字符串开头的正则表达式没有效率问题，而匹配结尾时会出现性能瓶颈。因此，可以采用正则表达式与传统字符串方法相结合的方式，来改善trim的性能问题。

例如：