文本消息与数千个正则表达式的有效匹配

Question

我正在解决一个问题，在这个问题中，我需要将文本消息与成千上万的正则表达式进行匹配，其形式为

<some string> {0 or 300 chars} <some string> {0 or 300 chars}

例如：

"on"[ \t\r]*(.){0,300}"."[ \t\r]*(.){0,300}"from"

或者一个真实的例子可以是

"Dear"[ \t\r]*"Customer,"[ \t\r]*"Your"[ \t\r]*"package"[ \t\r]*(.){0,80}[ \t\r]*"is"[ \t\r]*"out"[ \t\r]*"for"[ \t\r]*"delivery"[ \t\r]*"via"(.){0,80}[ \t\r]*"Courier,"[ \t\r]*(.){0,80}[ \t\r]*"on"(.){0,80}"."[ \t\r]*"Delivery"[ \t\r]*"will"[ \t\r]*"be"[ \t\r]*"attempted"[ \t\r]*"in"[ \t\r]*"5"[ \t\r]*"wkg"[ \t\r]*"days."

首先，我使用了Java的正则表达式引擎。我一次将输入字符串与一个正则表达式进行匹配。这个过程太慢了。我发现Java的正则表达式引擎将正则表达式编译成NFA (非确定性有限自动机)，由于灾难性的回溯，NFA可能会变得很慢。因此，我考虑使用flex-lexer将正则表达式转换为DFA (确定性有限自动机)，以便将数百个正则表达式编译成一个DFA，从而得到O(n)的匹配结果，n是输入字符串的长度。但是由于正则表达式中固定的重复计数，flex永远需要花费大量时间来编译see here。

也许我做的一切都错了。有没有更好的方法来做到这一点？我能想到的一种方法是将固定的重复计数转换为不确定的重复(星号运算符)，如下所示

"on"[ \t\r]*(.)*"."[ \t\r]*(.)*"from"

这个正则表达式编译时没有问题，而且只需要几毫秒。如果输入字符串与此规则匹配，我知道规则("on", "." and "from")中的常量字符串出现在输入字符串中。现在，如果flex支持命名的正则表达式组，我可以简单地计算这些组中的字符数并进行验证，但flex不是为了这个目的。

问题--有没有办法有效地解决这个问题？

Answer 1

问题是正则表达式的所有其他部分都是(.){0,80}

"Dear"[ \t\r]*"Customer,"[ \t\r]*"Your"[ \t\r]*"package"[ \t\r]*
(.){0,80}
[ \t\r]*"is"[ \t\r]*"out"[ \t\r]*"for"[ \t\r]*"delivery"[ \t\r]*"via"
(.){0,80}
[ \t\r]*"Courier,"[ \t\r]*
(.){0,80}
[ \t\r]*"on"
(.){0,80}"."
[ \t\r]*"Delivery"[ \t\r]*"will"[ \t\r]*"be"[ \t\r]*"attempted"[ \t\r]*"in"[ \t\r]*"5"[ \t\r]*"wkg"[ \t\r]*"days."

当下一个单词没有恰好出现在最后一个单词之后的80个字符时，正则表达式的执行速度会很慢。它需要回溯以查看79是否可以工作。或者78岁。或者77...这并不是全部或没有(正如您所认为的那样；80个或0个字符将是.{80}?)。

该引擎只是针对.*进行了更多优化，因为它更常见

根据内容在字符串中的位置，您可以使用惰性.{0,80}?获得更好的性能。但这不是一个很好的解决方案。

我认为这里的答案是使用多个正则表达式。

你可以find the index the match happened at，然后比较它，看看它是出现在短语第一次匹配的位置之前还是之后。

它变得更加复杂，可以在多个区域进行匹配，并且每次匹配的距离不超过x个字符。在这种情况下，您只需要收集多个匹配项，并稍微更改一下数学运算。