将短信与数千个正则表达式进行高效匹配
我正在解决一个问题，那就是我的文本消息与成千上万的表单正则表达式匹配
<some string> {0 or 300 chars} <some string> {0 or 300 chars}
例如
"on"[ tr]*(.){0,300}"."[ tr]*(.){0,300}"from"
或者一个真实的例子可以
"Dear"[ tr]*"Customer,"[ tr]*"Your"[ tr]*"package"[ tr]*(.){0,80}[ tr]*"is"[ tr]*"out"[ tr]*"for"[ tr]*"delivery"[ tr]*"via"(.){0,80}[ tr]*"Courier,"[ tr]*(.){0,80}[ tr]*"on"(.){0,80}"."[ tr]*"Delivery"[ tr]*"will"[ tr]*"be"[ tr]*"attempted"[ tr]*"in"[ tr]*"5"[ tr]*"wkg"[ tr]*"days."
首先我使用Java的正则表达式引擎。 我一次将输入字符串与一个正则表达式匹配。 这个过程太慢了。 我发现Java的正则表达式引擎将正则表达式编译成NFA（非确定性有限自动机），由于灾难性的回溯，它可能变慢。 因此，我想使用flex-lexer将正则表达式转换为DFA（确定性有限自动机），以便将数百个正则表达式编译成一个DFA，从而得到O（n）中的匹配结果，n是输入字符串的长度。 但由于正则表达式中的固定重复计数，flex将永久编译，请参阅此处。
可能是我做的一切都错了。 有没有更好的方法来做到这一点？ 我能想到的一种方法是将固定重复次数转换为无限次重复（星形算符），如下所示
"on"[ tr]*(.)*"."[ tr]*(.)*"from"
这个正则表达式编译没有问题，只需要几毫秒。 如果输入字符串与此规则匹配，我知道输入字符串中存在来自规则("on", "." and "from")常量字符串。 现在iff flex支持正则表达式的命名组，我可以简单地计算这些组中的字符数并验证，但flex不是为此目的而设计的。
问题 - 有什么办法可以有效解决这个问题吗？
问题是正则表达式的其他部分是(.){0,80} ：
"Dear"[ tr]*"Customer,"[ tr]*"Your"[ tr]*"package"[ tr]*
(.){0,80}
[ tr]*"is"[ tr]*"out"[ tr]*"for"[ tr]*"delivery"[ tr]*"via"
(.){0,80}
[ tr]*"Courier,"[ tr]*
(.){0,80}
[ tr]*"on"
(.){0,80}"."
[ tr]*"Delivery"[ tr]*"will"[ tr]*"be"[ tr]*"attempted"[ tr]*"in"[ tr]*"5"[ tr]*"wkg"[ tr]*"days."
正则表达式很慢，当下一个单词在最后一个单词后没有正好出现80个字符时。 它需要回头看看79是否可行。 或78.或77 ...这不是全部或没有，（你似乎相信它是; 80或0个字符将是.{80}? ）。
引擎只是更加优化来处理.*因为它更常见
根据字符串中的内容，您可能可以通过懒惰获得更好的效果.{0,80}? 。 但这不是一个好的解决方案。
我认为这里的答案是使用多个正则表达式。
您可以找到匹配发生的索引，然后比较比较它以查看它是在第一次匹配前的短语之前还是之后。
它可以在多个区域中匹配更复杂的事物，而且每场比赛所需的距离不超过x个字符。 在这种情况下，你只需要收集多个匹配并稍微改变数学。
链接地址: http://www.djcxy.com/p/74801.html上一篇: Efficient matching of text messages against thousands of regular expressions