查找多个字符串匹配的算法

Question

我正在寻找一种有效算法的建议,以便在大量文本中查找所有匹配项.要搜索的术语将包含在列表中,并且可以有1000多种可能性.搜索项可以是1个或更多个单词.

显然,我可以通过文本进行多次传递,比较每个搜索词.效率不高.

我想过订购搜索词并组合常见的子段.这样我就可以快速消除大量术语.语言是C++,我可以使用boost.

搜索术语的示例可以是财富500强公司名称的列表.

想法？

Answer 1

不要重新发明轮子

已经深入研究了这个问题.奇怪的是,搜索一个模式/字符串的最佳算法不容易外推到多字符串匹配.

该"grep的"家庭实现了非常高效的方式多字符串搜索.如果您可以将它们用作外部程序,请执行此操作.

如果您确实需要实现该算法,我认为最快的方法是重现agrep所做的事情(agrep在多字符串匹配方面表现优异!). 这是源文件和可执行文件.

而在这里,你会发现描述关于字符串匹配使用的算法,理论背景,以及大量的信息和指针的论文.

值得注意的是:Knuth,Boyer,Moore,Baeza-Yates和其他人都在大力研究多字符串匹配.如果你需要一个非常快的算法,请不要犹豫站在他们宽阔的肩膀上.不要重新发明轮子.

Answer 2

与单个模式的情况一样,有多种算法可用于多模式匹配,您必须找到最适合您目的的算法.本文一种用于多模式搜索(存档副本)的快速算法对其中的大多数进行了回顾,包括Aho-Corasick(这是Knuth-Morris-Pratt算法的多模式版本,具有线性复杂度)和Commentz-Walter(Boyer-Moore和Aho-Corasick的组合),并引入了一个新的,它使用Boyer-Moore的想法来完成匹配多个模式的任务.

另一种基于散列的算法是该论文中没有提到的,它是Rabin-Karp算法,它具有比其他算法更大的最坏情况复杂度,但通过散列减少线性因子来补偿它.哪一个更好取决于您的用例.如果要选择最快的,可能需要实现其中的几个并在应用程序中进行比较.