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

Question

我有很多字符串包含许多不同拼写的文本.我通过搜索关键字来标记这些字符串,如果找到关键字,我会使用该关键字的关联文本.

假设搜索字符串可以包含文本"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

Answer 1

这似乎适合" 使用有限模式集的算法 "

该阿霍Corasick字符串匹配 算法是由Alfred V.阿霍和Margaret J. Corasick发明了一种字符串搜索算法.它是一种字典匹配算法,它在输入文本中定位有限字符串集("字典")的元素.它"同时"匹配所有模式,因此算法的复杂性在模式的长度加上搜索文本的长度加上输出匹配的数量是线性的.请注意,因为找到了所有匹配项,所以如果每个子字符串匹配,则可以存在二次匹配数(例如,dictionary = a,aa,aaa,aaaa和输入字符串是aaaa).

在拉宾,卡普算法是由迈克尔·拉宾和理查德·卡普在1987年创建的字符串搜索算法,使用散列来查找文本的设置模式字符串中的任何一个.对于组合长度为m的长度为n和p的模式的文本,其平均和最佳情况运行时间在空间O(p)中为O(n + m),但其最坏情况时间为O(nm).相反,Aho-Corasick字符串匹配算法在空间O(m)中具有渐近最差时间复杂度O(n + m).