我正在寻找一种有效算法的建议,用于在大量文本中查找所有匹配项。要搜索的术语将包含在列表中,并且可以有 1000 多种可能性。搜索词可以是 1 个或多个单词。
显然,我可以多次遍历文本并与每个搜索词进行比较。效率不太高。
我考虑过对搜索词进行排序并组合常见的子分段。这样我就可以快速消除大量术语。语言是C++,我可以使用boost。
搜索词的一个示例可以是财富 500 强公司名称列表。
Ideas?
不要重新发明轮子
这个问题已经被深入研究。奇怪的是,搜索一个模式/字符串的最佳算法并不能轻易推断到多字符串匹配。
The "grep"family 以非常有效的方式实现多字符串搜索。如果您可以将它们用作外部程序,请使用它们。
如果您确实需要实现该算法,我认为最快的方法是重现 agrep 的功能(agrep 在多字符串匹配方面表现出色!)。Here是源文件和可执行文件。
And here您会找到一篇描述所用算法、理论背景以及有关字符串匹配的大量信息和指南的论文。
请注意:Knuth、Boyer、Moore、Baeza-Yates 等人对多字符串匹配进行了大量研究。如果您需要一个真正快速的算法,请毫不犹豫地站在他们宽阔的肩膀上。不要重新发明轮子。
本文内容由网友自发贡献,版权归原作者所有,本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容,请联系:hwhale#tublm.com(使用前将#替换为@)