正则表达式文字优化（或如何欺骗基准）

正则表达式文字优化可避免在输入文本的某些部分（可能无法与正则表达式匹配）上运行正则表达式引擎。

可以应用的正则表达式的一个示例是\ w + @ \ w + \。\ w +，其中算法快速找到第一个@，然后向后匹配\ w +以找到匹配的开始，然后匹配\ w + \。 \ w +向前查找比赛结束。然后，从上一个匹配项的末尾开始，找到第二个@，依此类推。这是一个相当幼稚的（并且不正确的）实现，但是它给出了其工作原理的想法。

我最近在我的宠物项目nim-regex中实现了它，这是一个基于NFA的正则表达式引擎，可以在（超）线性时间内运行。结果表明，在某些基准测试中，它的速度比以前快了约100倍。进行优化后，它的速度比PCRE快60倍。测试基于mariomka / regex-benchmark。

由于nim-regex必须保证线性时间，因此我将介绍保证线性时间的优化。我们还必须确保比赛不重叠。

我认为了解这种优化方式的最佳方法是通过示例。但是，这是该算法的高级描述：

我们选择一个用于跳过部分文本的文字。

前缀是文字前的正则表达式部分；前缀中的任何字符或符号都不得与文字匹配。

从匹配开始到完全扫描，直到找到无法匹配的字符（安全断点）或到达末尾。扫描尝试在每个字符处开始匹配（NFA可以在线性时间内执行此操作）。

转到第一步，并从最后扫描的字符开始重复。进行前缀匹配，直到前一个最后扫描的字符为止。

“前缀内的任何字符或符号都不得与文字匹配”，为什么？考虑正则表达式：\ d \ w + x，输入文本：xxxxxxxxxxx;这将花费二次时间，因为前缀将一直匹配到每次字符串的开头。限制呢？虽然限制确实避免了过度匹配，但有时我们需要匹配超出限制，例如：正则表达式：\ d \ w + x，文本：1xxx。如果添加此约束，则文字将成为分母，并且将解决这些情况。

文字不能是重复的一部分，也不能是替代的一部分。例如：（abc）* def第一个文字候选对象是d，因为（abc）*可能是匹配项，也可能不是匹配项的一部分。交替也一样。

func findAll（matchs：var Matches，text：string，regex：Regex，start：int）：int = var i =起始var limit =在i ＜时开始文字。 len：limit = i＃相当没有意义，因为文字是定界符i = memchr（text，regex。lit，i）如果i ==-1：返回-1 var litIdx = ii = matchPrefix（text，regex，i，limit ）如果i ==-1：i = litIdx + 1；否则：i = findSome（匹配项，文本，正则表达式，i）；如果i ==-1：如果匹配项则返回-1。伦＆gt; 0：返回i＃用作＆＃34; start＆＃34;恢复匹配的收益-1

给定字符只能使用两次，一次通过后向前缀匹配，第二次通过前向扫描。因此，该算法以线性时间运行。

我可能会描述matchPrefix和findSome的工作原理，如何以正确的顺序构造反向NFA，以及如何在以后的文章中选择原义。但是，nim-regex代码包含算法的描述。

基准正则表达式基于mariomka / regex-benchmark。唯一的区别是正则表达式是预编译的，因此仅测试匹配项。结果显示，nim-regex在电子邮件测试中比PCRE快约63倍，在URI和IP测试中快约2倍。

为什么nim-regex在电子邮件中如此之快？正则表达式引擎运行频率不高。匹配的IP / URI候选数比电子邮件候选数（文本中的@字符）大得多。在前一种情况下，时间由正则表达式引擎控制，而在后一种情况下，时间由搜索字符常量控制。

================================================== GlobalBenchmark相对时间/迭代次数/ s ========================================== ========全球基准294.86ps 3.39G ==================================== ============ bench.nim相对时间/迭代次数/ s =========================== ========================= pcre_email 21.76ms 45.96nim_regex_email 3247.14％670.02us 1.49Knim_regex_email_macro 6335.93％343.38us 2.91Kpcre_uri 22.15ms 45.14nim_regex_uri 87.82ms。 256.29％8.64ms 115.68pcre_ip 5.73ms 174.58nim_regex_ip 88.70％6.46ms 154.84nim_regex_ip_macro 214.75％2.67ms 374.91

注意Nim的PCRE位于mariomka / regex基准的顶部。我运行了这些基准测试，而IIRC nim-regex只是快了一点，主要是因为非宏regex引擎较慢（请参见上面的结果），并且还测试了regex编译。

选择一个文字（即使前缀与之匹配）也应花费线性时间，只要前缀是有界的（即：不包含重复项），例如：\ d \ wx。

因为（abc）+与abc（abc）*相同，所以应该可以在“一个或多个”重复/重复组中选择一个文字。

最好在第一个文字序列中选择最后一个文字，因为这样一来，我们总是尽早匹配尽可能多的文字，并且可能会尽早失败。我们希望前缀regex尽可能短，因此在第一个序列中选择文字是最好的。

在某些情况下，交替可以以相同的方式进行优化，例如：bar | baz，由于两个交替都有ba相同，因此可以选择a作为文字。

在其他情况下，可以优化替代方案。 PCRE似乎使用memchr或类似词来表示最多两个交替项。 DFA可以用来快速匹配候选人而不是memchr，因为这是更通用的解决方案。

文字优化不是通用优化，因为它不适用于每个正则表达式，但是当它适用时，可以大大提高匹配速度。

像PCRE这样的回溯者可以实现吗？特别是PCRE已经进行了某种类似的优化，但是不如优化。回溯者无法完全按照此处的描述来实现此目的，但是他们可以执行需要回溯的类似操作。如果它们提供可恢复的查找功能，则可能是。

希望更多的正则表达式引擎将实现这类优化，因此它们是PCRE等回溯者的更有吸引力的替代方案。