用于查找文本中所有关键字的高效算法
我有很多字符串包含许多不同拼写的文本。 我通过搜索关键字来标记这些字符串，如果找到关键字，我会使用该关键字的关联文本。
假设搜索字符串可以包含文本“schw。”，“schwa”。 和“施瓦茨”。 我有三个关键字都解析为文本“schwarz”。
现在我正在寻找一种有效的方法来查找所有关键字，而无需执行string.Contains（关键字）为每个关键字。
样本数据：
H-Fuss ahorn 15 cm/SH48cm Metall-Fuss chrom 9 cm/SH42cm Metall-Kufe alufbg.12 cm/SH45c Metall-Kufe verchr.12 cm/SH45c Metall-Zylind.aluf.12cm/SH45cm Kufe alufarbig Metall-Zylinder hoch alufarbig Kunststoffgl.schw. - hoch Kunststoffgl.schw. - Standard Kunststoffgleiter - schwarz für Sitzhoehe 42 cm 示例关键字（键，值）：
h-fuss, Holz ahorn, Ahorn metall, Metall chrom, Chrom verchr, Chrom alum, Aluminium aluf, Aluminium kufe, Kufe zylind, Zylinder hoch, Hoch kunststoffgl, Gleiter gleiter, Gleiter schwarz, Schwarz schw., Schwarz
样本结果：
Holz, Ahorn Metall, Chrom Metall, Kufe, Aluminium Metall, Kufe, Chrom Metall, Zylinder, Aluminium Kufe, Aluminium Metall, Zylinder, Hoch, Aluminium Gleiter, Schwarz, Hoch Gleiter, Schwarz Gleiter, Schwarz
这似乎适合“ 使用有限模式集的算法 ”
Aho-Corasick字符串匹配算法是由Alfred V. Aho和Margaret J. Corasick发明的字符串搜索算法。 它是一种字典匹配算法，它在输入文本中定位有限字符串集（“字典”）的元素。 它“同时”匹配所有模式，因此算法的复杂性在模式的长度加上搜索文本的长度加上输出匹配的数量是线性的。 请注意，因为找到了所有匹配项，所以如果每个子字符串匹配，则可以存在二次匹配数（例如，dictionary = a，aa，aaa，aaaa和输入字符串是aaaa）。
Rabin-Karp算法是由Michael O. Rabin和Richard M. Karp于1987年创建的字符串搜索算法，它使用散列来查找文本中的一组模式字符串中的任何一个。 对于组合长度为m的长度为n和p的模式的文本，其平均和最佳情况运行时间在空间O（p）中为O（n + m），但其最坏情况时间为O（nm）。 相反，Aho-Corasick字符串匹配算法在空间O（m）中具有渐近最差时间复杂度O（n + m）。
我会为每组关键字使用预编译的正则表达式来匹配。 在后台这些被“编译”到有限自动机，因此它们在识别字符串中的模式方面非常快，并且比每个可能字符串的Contains快得多。
使用： System.Text.RegularExpressions 。
在你的例子中：
- “schw。”，“schwa。” 和“施瓦茨”
-
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进行string.Split并匹配您拥有的键字典
2）使用ReadToken()方法自己实现tokeniser，它将字符添加到缓冲区，直到找到（Split可能会这样做）一个拆分字符并将其作为标记输出。 然后你检查你的字典。
也许它有点过于强大，但你一定要看看ANTLR 。