将字符串与多个模式相匹配的最快方法

我有一个字符串列表，它们是带有AND和OR运算符和通配符的模式。现在给出一个输入字符串，如果匹配任何模式则返回true，否则返回false。将字符串与多个模式相匹配的最快方法

说，我有'n'模式和长度'm'的查询现在，显而易见的方法是运行一个循环和grep为字符串中的每个模式。这需要O（nm）时间。

现在，我的问题是，是否有可能做得更好？我在想某种表达式评估有限状态机可能？有没有这样的名称/参考实现？

感谢

2016-11-15 Saksham Manchanda

请注意，现代CPU在线性数据结构上快速循环（特别是当循环适合片内存储器并且可以预测分支时），并且在指针之后和片外访问内存时要慢得多。无论你尝试什么，你都应该将它与一个愚蠢的蛮力算法进行比较。 –

您当然可以创建一个有限状态机来处理来自所有模式的合并搜索。有关将RegEx转换为FSM的讨论，请参阅http://stackoverflow.com/questions/525004/short-example-of-regular-expression-converted-to-a-state-machine。 –

您正在寻找Boyer–Moore string search algorithm。

如果您首先解析模式并将其构建为Abstract Syntax Tree，然后将查询字符串解析为另一个抽象语法树，然后使用节点搜索（对于根），您也可以获得好结果，树比较算法（而不是微不足道的）来查看在查询字符串中是否找到任何模式字符串。理论上，查询字符串的解析可以在O（n）中完成，但实际上我怀疑它会导致更好的性能。尽管这可能是一个有趣的练习。

来源

2016-11-15 22:52:31

我想你已经误解了OP（或者我有）;我认为OP *是*使用“模式”来指代正在搜索的内容。我认为有很多字符串搜索，并且只有一个字符串搜索。（此外，“模式”似乎比简单的子串复杂得多。） – ruakh

@ruakh你说得对。我将重新回答我的答案。 –

将字符串与多个模式相匹配的最快方法

回答

相关问题