查找文本中所有关键字的有效算法

这似乎很合适” Algorithms using finite set of patterns "

这个 Aho–Corasick string matching 算法是字符串搜索 Alfred V.Aho发明的算法 还有玛格丽特科拉希克。这是一种 字典匹配算法 定位有限集的元素 字符串(“字典”)在 输入文本。它符合所有的模式 “立刻”,所以复杂性 算法的长度是线性的 图案加上 搜索文本加上 输出匹配。请注意,因为 找到匹配项,可能有 如果每 子字符串匹配(例如字典= a、 aa,aaa,aaaa输入字符串是 aaaa)。

这个 Rabin–Karp algorithm 是一个字符串 Michael创建的搜索算法 O、 1987年拉宾和理查德·M·卡普 使用散列来查找 文本中的一组模式字符串。为了 长度n和p的文本模式 组合长度m,其平均值和 最佳运行时间为O(n+m)in 空间O(p),但它的最坏情况是 O(纳米)。相比之下,阿霍·科拉希克 字符串匹配算法 渐近最坏时间复杂度 空间O(n+m)。

我将对每组关键字使用预编译的正则表达式进行匹配。在后台,它们被“编译”成有限自动机,因此它们识别字符串中的模式非常快,并且比 Contains 对于每个可能的字符串。

使用: System.Text.RegularExpressions .

在您的示例中:

• “schw.”、“schwa.”和“schwarz”
• new Regex(@"schw(a?\.|arz)", RegexOptions.Compiled)

此处提供更多文档: http://msdn.microsoft.com/en-us/library/system.text.regularexpressions.regexoptions(v=VS.90).aspx

如果您有一组固定的关键字,可以使用(f)lex, re2c 或 ragel

我建议采取以下措施:

1) 标记使用 string.Split 和你的钥匙字典比对

2) 使用 ReadToken() 方法,该方法将字符添加到缓冲区中,直到找到(拆分可能正在执行此操作)拆分字符并将其作为令牌输出。然后你对照你的字典。

也许有点力不从心,但你一定要看看 ANTLR .