高效的算法找出所有关键字的文本 [英] Efficient algorithm for finding all keywords in a text

问题描述

我有很多包含在许多不同拼法的文本字符串。我通过搜索关键字标记化这些字符串，如果一个关键字找到我使用assoicated文字的关键字。

比方说，搜索字符串可以包含文本SCHW，元音。和施瓦茨。我有三个关键词，所有解析文本施瓦茨。

现在我在寻找找到没有做string.Contains（关键字）为每一个关键字的所有关键字的有效途径。

样本数据：

  H-忙乱AHORN15厘米/ SH48cm
METALL大惊小怪CHROM9厘米/ SH42cm
METALL-Kufe alufbg.12厘米/ SH45c
METALL-Kufe verchr.12厘米/ SH45c
METALL-Zylind.aluf.12cm / SH45cm
Kufe alufarbig
METALL-Zylinder HOCH alufarbig
Kunststoffgl.schw。 -  HOCH
Kunststoffgl.schw。 - 标准
Kunststoffgleiter  - 施瓦茨献给Sitzhoehe42厘米
 

样的关键字（键，值）：

  H-做文章，霍尔兹
AHORN，Ahorn酒店
METALL，METALL
CHROM，的Chrom
verchr，的Chrom
明矾，铝
aluf，铝
kufe，Kufe
zylind，Zylinder
HOCH，霍克
kunststoffgl，格莱特
格莱特，格莱特
施瓦茨，施瓦茨
SCHW，施瓦茨
 

示例结果：

 霍尔兹，Ahorn酒店
METALL，的Chrom
METALL，Kufe，铝
METALL，Kufe，的Chrom
METALL，Zylinder，铝
Kufe，铝
METALL，Zylinder，霍克，铝
格莱特，施瓦茨，霍克
格莱特，施瓦茨
格莱特，施瓦茨
 

解决方案

这似乎符合<一href="http://en.wikipedia.org/wiki/String_searching_algorithm#Algorithms_using_finite_set_of_patterns">Algorithms利用有限组模式的

  

借助阿霍Corasick字符串匹配   算法是一个字符串检索   算法由Alfred V.阿霍发明   和Margaret J. Corasick。它是一种   词典匹配算法，   定位的有限集合的元素   字符串（说文解字）内   输入文本。它匹配所有的模式   一次，所以的复杂性   算法是线性的长度   图案加的长度   搜索文本以及数量   输出匹配。需要注意的是，因为所有的   被发现的比赛，可以有   比赛如果每二次数   子字符串匹配（例如字典=   A，AA，AAA，AAAA和输入字符串   AAAA）。

     

借助拉宾，卡普算法是一个字符串   由迈克尔·创建搜索算法   O.拉宾和理查德·卡普在1987年   使用散列找到的任何一个   在文本设置的模式字符串。对于   的长度为n的文本和p型态   结合长度为m，其平均   最好的情况下的运行时间为O（N + M）中   空间氧（对），但它的最坏情况下的时间是   O（NM）。与此相反，阿霍Corasick   字符串匹配算法   渐近最坏的时间复杂度   O（N + M）空间O（M）

I have lots of strings containing text in lots of different spellings. I am tokenizing these strings by searching for keywords and if a keyword is found I use an assoicated text for that keyword.

Let's say the search string can contain the text "schw.", "schwa." and "schwarz". I have three keywords that all resolve to the text "schwarz".

Now I'm searching for an effective way to find all the keywords without doing a string.Contains(keyword) for every single keyword.

Sample data:

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

Sample keywords (key, value):

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

Sample result:

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

解决方案

This seems to fit "Algorithms using finite set of patterns"

The Aho–Corasick string matching algorithm is a string searching algorithm invented by Alfred V. Aho and Margaret J. Corasick. It is a kind of dictionary-matching algorithm that locates elements of a finite set of strings (the "dictionary") within an input text. It matches all patterns "at once", so the complexity of the algorithm is linear in the length of the patterns plus the length of the searched text plus the number of output matches. Note that because all matches are found, there can be a quadratic number of matches if every substring matches (e.g. dictionary = a, aa, aaa, aaaa and input string is aaaa).

The Rabin–Karp algorithm is a string searching algorithm created by Michael O. Rabin and Richard M. Karp in 1987 that uses hashing to find any one of a set of pattern strings in a text. For text of length n and p patterns of combined length m, its average and best case running time is O(n+m) in space O(p), but its worst-case time is O(nm). In contrast, the Aho–Corasick string matching algorithm has asymptotic worst-time complexity O(n+m) in space O(m).

这篇关于高效的算法找出所有关键字的文本的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！