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

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(非确定性有限自动机)，由于灾难性的回溯，它可能会变慢。于是想到用flex-lexer将正则表达式转为DFA(Deterministic Finite Automata)，将数百个regex编译成一个DFA，得到的匹配结果复杂度为O(n)，n为输入字符串的长度。但是由于正则表达式中的固定重复计数，flex 需要永远编译 see here .

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

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

这个正则表达式编译没有问题，只需要几毫秒。如果输入字符串与此规则匹配，我知道输入字符串中存在规则 ("on", ". and "from") 中的常量字符串。现在 iff 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 个字符。在这种情况下，您只需要收集多个匹配项并稍微更改数学即可。