Ars*_*yan 9 .net c# regex algorithm
来自MSDN 的正则表达式行为的文章细节说,.NET开发人员决定使用正则表达式传统的NFA引擎,因为它比POSIX NFA更快,但我不清楚,为什么这种模式的指数速度成倍增长呢？
var regex = new Regex("(a|aa)*b");
var b = regex.IsMatch("aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaac");
这种简单的模式匹配需要超过30分钟才能执行.但是如果.NET使用传统的NFA,则可以在最坏的情况下模拟它并在O(M*N)时间内找到匹配,其中M是模式长度而N是文本长度,在这种情况下肯定不是这样.
文章还解释了回溯是执行缓慢的原因,但我仍然有一些无法找到答案的问题
(a|b)c/1吗？您可以将正则表达式编译为 NFA 或 DFA，尽管从 NFA 计算出的 DFA 可能大得不切实际。您可以在有或没有回溯的情况下匹配 NFA，尽管无需回溯的方案通常会对正则表达式语言以及在存在许多可能的匹配时找到哪些匹配施加更多限制。
你的例子很慢，因为匹配器必须经常决定是与 a 还是 aa 匹配，以及是否尝试匹配最后的 b。回溯的工作原理类似于运行一个递归函数，该函数在每一步都会对每种可能性进行递归调用 - 递归地与 a 匹配，如果失败则递归地与 aa 匹配，如果失败则递归地与 b 匹配。
Microsoft 似乎在说他们的回溯比 POSIX 更快，因为 POSIX 回溯将安排递归搜索，直到确定已找到最长的可能匹配为止。Microsoft 版本仍然会回溯，但不会进行额外的检查，直到保证找到最长的可能匹配为止。http://msdn.microsoft.com/en-us/library/dsy130b4%28v=vs.110%29.aspx中有一个示例。
无需回溯的正则表达式匹配器可以通过一次接受一个字符的输入并跟踪当时 NFA 中的哪些状态处于活动状态来工作 - 可能有很多这样的状态。很难通过反向引用来完成这项工作，因为这样就不能仅通过状态是否活跃来描述 NFA 的状态。