我需要一种方法来比较多个字符串到一个测试字符串,并返回与它非常相似的字符串:

TEST STRING: THE BROWN FOX JUMPED OVER THE RED COW

CHOICE A   : THE RED COW JUMPED OVER THE GREEN CHICKEN
CHOICE B   : THE RED COW JUMPED OVER THE RED COW
CHOICE C   : THE RED FOX JUMPED OVER THE BROWN COW

(如果我做对了)最接近“TEST string”的字符串应该是“CHOICE C”。最简单的方法是什么?

我计划将其实现为多种语言,包括VB.net、Lua和JavaScript。此时,伪代码是可以接受的。如果你能提供一个特定语言的例子,这也是非常感谢的!


当前回答

你可能会对这篇博客感兴趣。

http://seatgeek.com/blog/dev/fuzzywuzzy-fuzzy-string-matching-in-python

Fuzzywuzzy是一个Python库,它提供了简单的距离度量,例如用于字符串匹配的Levenshtein距离。它构建在标准库中的difflib之上,并将使用Python-levenshtein(如果可用的话)的C实现。

http://pypi.python.org/pypi/python-Levenshtein/

其他回答

如果您在搜索引擎上下文中执行此操作,或者在数据库前端执行此操作,则可以考虑使用类似Apache Solr的工具,并使用ComplexPhraseQueryParser插件。这种组合允许您搜索字符串索引,并根据相关性(由Levenshtein距离确定)对结果进行排序。

当传入的查询可能有一个或多个拼写错误时,我们一直在对大量艺术家和歌曲标题的集合使用它,并且它工作得非常好(考虑到集合包含数百万个字符串,它的速度非常快)。

此外,使用Solr,您可以根据需要通过JSON根据索引进行搜索,因此不必在不同的语言之间重新设计解决方案。

我怀疑选项B更接近测试字符串,因为它距离原始字符串只有4个字符(和2个删除)。而C更接近,因为它同时包含棕色和红色。但是,它有一个更大的编辑距离。

有一种叫做Levenshtein Distance的算法可以测量两个输入之间的编辑距离。

这里有一个算法工具。

选择A的距离是15。 选择B的距离是6。 选择C的距离为9。

编辑:对不起,我一直在levenshtein工具混合字符串。更新到正确的答案。

你可能会对这篇博客感兴趣。

http://seatgeek.com/blog/dev/fuzzywuzzy-fuzzy-string-matching-in-python

Fuzzywuzzy是一个Python库,它提供了简单的距离度量,例如用于字符串匹配的Levenshtein距离。它构建在标准库中的difflib之上,并将使用Python-levenshtein(如果可用的话)的C实现。

http://pypi.python.org/pypi/python-Levenshtein/

你可能会发现这个图书馆很有用! http://code.google.com/p/google-diff-match-patch/

目前可以在Java, JavaScript, Dart, c++, c#, Objective C, Lua和Python中使用

它也运行得很好。我在我的几个Lua项目中使用了它。

而且我认为将其移植到其他语言并不困难!

要以有效的方式查询大量文本,可以使用编辑距离/前缀编辑距离的概念。

编辑距离ED(x,y):从项x到项y的最小变换数

但是计算每个术语和查询文本之间的ED是资源和时间密集型的。因此,我们可以使用一种称为Qgram Index的技术提取可能匹配的项,而不是首先计算每个项的ED。然后对这些选定的项进行ED计算。

Qgram索引技术的优点是支持模糊搜索。

采用QGram索引的一种可能的方法是使用QGram构建倒排索引。在那里,我们存储了所有与特定Qgram组成的单词,在那个Qgram之下。(而不是存储完整的字符串,您可以为每个字符串使用唯一的ID)。为此,您可以使用Java中的Tree Map数据结构。 下面是存储术语的一个小示例

科尔姆比亚,科伦坡,甘科拉,塔科拉马

然后,在查询时,我们计算查询文本和可用术语之间的公共Qgrams的数量。

Example: x = HILLARY, y = HILARI(query term)
Qgrams
$$HILLARY$$ -> $$H, $HI, HIL, ILL, LLA, LAR, ARY, RY$, Y$$
$$HILARI$$ -> $$H, $HI, HIL, ILA, LAR, ARI, RI$, I$$
number of q-grams in common = 4

共有q-gram数= 4。

对于具有大量常见Qgrams的术语,我们根据查询术语计算ED/PED,然后向最终用户建议该术语。

你可以在下面的项目中找到这个理论的实现(参见“QGramIndex.java”)。请随意提问。https://github.com/Bhashitha-Gamage/City_Search

要了解更多关于编辑距离,前缀编辑距离Qgram索引,请观看Hannah Bast教授的视频https://www.youtube.com/embed/6pUg2wmGJRo(课程从20:06开始)