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

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。此时,伪代码是可以接受的。如果你能提供一个特定语言的例子,这也是非常感谢的!


当前回答

还有一个相似度测量,我曾经在我们的系统中实施,并给出了令人满意的结果:-

用例

有一个用户查询需要与一组文档进行匹配。

算法

从用户查询中提取关键字(相关POS TAGS -名词,专有名词)。 现在根据下面的公式计算分数,用于测量用户查询和给定文档之间的相似性。

对于从用户查询中提取的每个关键字:-

开始在文档中搜索给定的单词,并在文档中每出现一次该单词就减少奖励点数。

从本质上讲,如果第一个关键字在文档中出现了4次,则得分将计算为:-

第一次出现将获取'1'点。 第二次出现将在计算分数上加1/2 第三次会增加总数的1/3 第四次得到1/4

总相似度= 1 + 1/2 + 1/3 + 1/4 = 2.083

类似地,我们为用户查询中的其他关键字计算它。

最后,总分将表示用户查询与给定文档之间的相似程度。

其他回答

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

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/

如果输入数据太大(比如数百万个字符串),这个问题就很难实现。我用弹性搜索来解决这个问题。

快速入门:https://www.elastic.co/guide/en/elasticsearch/client/net-api/6.x/elasticsearch-net.html

只需将所有输入数据插入到DB中,您就可以根据任何编辑距离快速搜索任何字符串。下面是一个c#代码片段,它会给你一个按编辑距离排序的结果列表(从小到大)

var res = client.Search<ClassName>(s => s
    .Query(q => q
    .Match(m => m
        .Field(f => f.VariableName)
        .Query("SAMPLE QUERY")
        .Fuzziness(Fuzziness.EditDistance(5))
    )
));

还有一个相似度测量,我曾经在我们的系统中实施,并给出了令人满意的结果:-

用例

有一个用户查询需要与一组文档进行匹配。

算法

从用户查询中提取关键字(相关POS TAGS -名词,专有名词)。 现在根据下面的公式计算分数,用于测量用户查询和给定文档之间的相似性。

对于从用户查询中提取的每个关键字:-

开始在文档中搜索给定的单词,并在文档中每出现一次该单词就减少奖励点数。

从本质上讲,如果第一个关键字在文档中出现了4次,则得分将计算为:-

第一次出现将获取'1'点。 第二次出现将在计算分数上加1/2 第三次会增加总数的1/3 第四次得到1/4

总相似度= 1 + 1/2 + 1/3 + 1/4 = 2.083

类似地,我们为用户查询中的其他关键字计算它。

最后,总分将表示用户查询与给定文档之间的相似程度。

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

编辑距离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开始)

Lua实现,为子孙后代:

function levenshtein_distance(str1, str2)
    local len1, len2 = #str1, #str2
    local char1, char2, distance = {}, {}, {}
    str1:gsub('.', function (c) table.insert(char1, c) end)
    str2:gsub('.', function (c) table.insert(char2, c) end)
    for i = 0, len1 do distance[i] = {} end
    for i = 0, len1 do distance[i][0] = i end
    for i = 0, len2 do distance[0][i] = i end
    for i = 1, len1 do
        for j = 1, len2 do
            distance[i][j] = math.min(
                distance[i-1][j  ] + 1,
                distance[i  ][j-1] + 1,
                distance[i-1][j-1] + (char1[i] == char2[j] and 0 or 1)
                )
        end
    end
    return distance[len1][len2]
end