获取最接近的字符串匹配

大约一年前，当我在杂项信息数据库中查找用户输入的有关石油钻井平台的信息时，我遇到了这个问题。目标是进行某种模糊字符串搜索，以识别具有最常见元素的数据库条目。

部分研究涉及实现 Levenshtein distance 算法，该算法确定必须对字符串或短语进行多少更改才能将其转换为另一个字符串或短语。

我想出的实现比较简单，包括对两个短语的长度、每个短语之间的变化次数以及每个单词是否可以在目标条目中找到的加权比较。

该文章在私人网站上，因此我会尽力在此处附加相关内容：

模糊字符串匹配是对两个单词或短语的相似性进行类人估计的过程。在许多情况下，它涉及识别彼此最相似的单词或短语。本文描述了模糊字符串匹配问题的内部解决方案及其在解决各种问题中的有用性，这些问题可以让我们自动化以前需要繁琐的用户参与的任务。

介绍

在开发墨西哥湾验证器工具时，最初需要进行模糊字符串匹配。现有的是一个已知墨西哥湾石油钻井平台和平台的数据库，购买保险的人会给我们一些关于他们资产的错误输入信息，我们必须将其与已知平台的数据库相匹配。当提供的信息很少时，我们能做的最好的事情就是依靠承销商来“识别”他们所指的承销商并调用适当的信息。这就是这个自动化解决方案派上用场的地方。

我花了一天时间研究模糊字符串匹配的方法，最终偶然发现了维基百科上非常有用的 Levenshtein 距离算法。

执行

在阅读了它背后的理论之后，我实施并找到了优化它的方法。这就是我的代码在 VBA 中的样子：

'Calculate the Levenshtein Distance between two strings (the number of insertions,
'deletions, and substitutions needed to transform the first string into the second)
Public Function LevenshteinDistance(ByRef S1 As String, ByVal S2 As String) As Long
    Dim L1 As Long, L2 As Long, D() As Long 'Length of input strings and distance matrix
    Dim i As Long, j As Long, cost As Long 'loop counters and cost of substitution for current letter
    Dim cI As Long, cD As Long, cS As Long 'cost of next Insertion, Deletion and Substitution
    L1 = Len(S1): L2 = Len(S2)
    ReDim D(0 To L1, 0 To L2)
    For i = 0 To L1: D(i, 0) = i: Next i
    For j = 0 To L2: D(0, j) = j: Next j

    For j = 1 To L2
        For i = 1 To L1
            cost = Abs(StrComp(Mid$(S1, i, 1), Mid$(S2, j, 1), vbTextCompare))
            cI = D(i - 1, j) + 1
            cD = D(i, j - 1) + 1
            cS = D(i - 1, j - 1) + cost
            If cI <= cD Then 'Insertion or Substitution
                If cI <= cS Then D(i, j) = cI Else D(i, j) = cS
            Else 'Deletion or Substitution
                If cD <= cS Then D(i, j) = cD Else D(i, j) = cS
            End If
        Next i
    Next j
    LevenshteinDistance = D(L1, L2)
End Function

简单、快速且非常有用的指标。使用它，我创建了两个单独的指标来评估两个字符串的相似性。一种我称之为“valuePhrase”，一种我称之为“valueWords”。 valuePhrase 只是两个短语之间的 Levenshtein 距离，valueWords 根据分隔符（如空格、破折号和您想要的任何其他内容）将字符串拆分为单个单词，并将每个单词与其他单词进行比较，总结出最短的连接任意两个单词的 Levenshtein 距离。本质上，它衡量一个“短语”中的信息是否真的包含在另一个“短语”中，就像逐字排列一样。我花了几天时间作为一个附带项目，提出了基于分隔符拆分字符串的最有效方法。

valueWords、valuePhrase 和 Split 函数：

Public Function valuePhrase#(ByRef S1$, ByRef S2$)
    valuePhrase = LevenshteinDistance(S1, S2)
End Function

Public Function valueWords#(ByRef S1$, ByRef S2$)
    Dim wordsS1$(), wordsS2$()
    wordsS1 = SplitMultiDelims(S1, " _-")
    wordsS2 = SplitMultiDelims(S2, " _-")
    Dim word1%, word2%, thisD#, wordbest#
    Dim wordsTotal#
    For word1 = LBound(wordsS1) To UBound(wordsS1)
        wordbest = Len(S2)
        For word2 = LBound(wordsS2) To UBound(wordsS2)
            thisD = LevenshteinDistance(wordsS1(word1), wordsS2(word2))
            If thisD < wordbest Then wordbest = thisD
            If thisD = 0 Then GoTo foundbest
        Next word2
foundbest:
        wordsTotal = wordsTotal + wordbest
    Next word1
    valueWords = wordsTotal
End Function

''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''
' SplitMultiDelims
' This function splits Text into an array of substrings, each substring
' delimited by any character in DelimChars. Only a single character
' may be a delimiter between two substrings, but DelimChars may
' contain any number of delimiter characters. It returns a single element
' array containing all of text if DelimChars is empty, or a 1 or greater
' element array if the Text is successfully split into substrings.
' If IgnoreConsecutiveDelimiters is true, empty array elements will not occur.
' If Limit greater than 0, the function will only split Text into 'Limit'
' array elements or less. The last element will contain the rest of Text.
''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''
Function SplitMultiDelims(ByRef Text As String, ByRef DelimChars As String, _
        Optional ByVal IgnoreConsecutiveDelimiters As Boolean = False, _
        Optional ByVal Limit As Long = -1) As String()
    Dim ElemStart As Long, N As Long, M As Long, Elements As Long
    Dim lDelims As Long, lText As Long
    Dim Arr() As String

    lText = Len(Text)
    lDelims = Len(DelimChars)
    If lDelims = 0 Or lText = 0 Or Limit = 1 Then
        ReDim Arr(0 To 0)
        Arr(0) = Text
        SplitMultiDelims = Arr
        Exit Function
    End If
    ReDim Arr(0 To IIf(Limit = -1, lText - 1, Limit))

    Elements = 0: ElemStart = 1
    For N = 1 To lText
        If InStr(DelimChars, Mid(Text, N, 1)) Then
            Arr(Elements) = Mid(Text, ElemStart, N - ElemStart)
            If IgnoreConsecutiveDelimiters Then
                If Len(Arr(Elements)) > 0 Then Elements = Elements + 1
            Else
                Elements = Elements + 1
            End If
            ElemStart = N + 1
            If Elements + 1 = Limit Then Exit For
        End If
    Next N
    'Get the last token terminated by the end of the string into the array
    If ElemStart <= lText Then Arr(Elements) = Mid(Text, ElemStart)
    'Since the end of string counts as the terminating delimiter, if the last character
    'was also a delimiter, we treat the two as consecutive, and so ignore the last elemnent
    If IgnoreConsecutiveDelimiters Then If Len(Arr(Elements)) = 0 Then Elements = Elements - 1

    ReDim Preserve Arr(0 To Elements) 'Chop off unused array elements
    SplitMultiDelims = Arr
End Function

相似度测量

使用这两个指标，以及简单计算两个字符串之间距离的第三个指标，我有一系列变量，我可以运行优化算法来实现最大数量的匹配。模糊字符串匹配本身就是一门模糊科学，因此通过创建用于测量字符串相似性的线性独立指标，并拥有一组我们希望相互匹配的已知字符串，我们可以找到适合我们特定风格的参数字符串，给出最好的模糊匹配结果。

最初，该度量的目标是为精确匹配提供较低的搜索值，并为越来越多的排列度量增加搜索值。在一个不切实际的情况下，这很容易使用一组定义明确的排列来定义，并设计最终公式，以便它们根据需要增加搜索值结果。

https://i.stack.imgur.com/ltCIu.png

在上面的屏幕截图中，我调整了我的启发式方法，以提出一些我觉得可以很好地适应搜索词和结果之间的感知差异的东西。我在上述电子表格中用于 Value Phrase 的启发式是 =valuePhrase(A2,B2)-0.8*ABS(LEN(B2)-LEN(A2))。我有效地将 Levenstein 距离的惩罚减少了两个“短语”长度差异的 80%。这样，具有相同长度的“短语”会受到全部惩罚，但包含“附加信息”（更长）但除此之外仍然大部分共享相同字符的“短语”会受到减少的惩罚。我按原样使用 Value Words 函数，然后我的最终 SearchVal 启发式定义为 =MIN(D2,E2)*0.8+MAX(D2,E2)*0.2 - 加权平均值。两个分数中较低者的权重为 80%，较高分数的权重为 20%。这只是适合我的用例以获得良好匹配率的启发式方法。然后可以调整这些权重，以获得与测试数据的最佳匹配率。

https://i.stack.imgur.com/inSyO.png

https://i.stack.imgur.com/kCrqF.png

正如您所看到的，最后两个指标，即模糊字符串匹配指标，已经自然倾向于将低分给要匹配的字符串（对角线下方）。这是非常好的。

应用为了优化模糊匹配，我对每个度量进行加权。因此，模糊字符串匹配的每个应用程序都可以对参数进行不同的加权。定义最终分数的公式是指标及其权重的简单组合：

value = Min(phraseWeight*phraseValue, wordsWeight*wordsValue)*minWeight
      + Max(phraseWeight*phraseValue, wordsWeight*wordsValue)*maxWeight
      + lengthWeight*lengthValue

使用优化算法（神经网络在这里最好，因为它是一个离散的多维问题），现在的目标是最大化匹配的数量。我创建了一个函数来检测每组正确匹配的数量，如最终屏幕截图所示。如果将最低分数分配给要匹配的字符串，则列或行得到一个分数，如果最低分数相同，则给出部分分数，并且正确匹配在并列匹配的字符串中。然后我对其进行了优化。您可以看到绿色单元格是与当前行最匹配的列，而单元格周围的蓝色方块是与当前列最匹配的行。底角的分数大致是成功匹配的数量，这就是我们告诉优化问题最大化的值。

https://i.stack.imgur.com/XPglZ.png

该算法取得了巨大的成功，解决方案参数对这类问题说了很多。您会注意到优化后的分数是 44，最好的分数是 48。最后的 5 列是诱饵，与行值完全不匹配。诱饵越多，自然就越难找到最佳匹配。

在这种特殊的匹配情况下，字符串的长度是无关紧要的，因为我们期望代表更长单词的缩写，所以长度的最佳权重是 -0.3，这意味着我们不会惩罚长度不同的字符串。我们降低了对这些缩写的预期分数，为部分单词匹配提供了更多空间，以取代非单词匹配，因为字符串更短，因此只需要更少的替换。

单词权重为 1.0，而短语权重仅为 0.5，这意味着我们会惩罚从一个字符串中丢失的整个单词，并且更重视整个短语的完整性。这很有用，因为许多这些字符串都有一个共同的词（危险），真正重要的是是否保持组合（区域和危险）。

最后，最小权重优化为 10，最大权重优化为 1。这意味着如果两个分数（价值短语和价值词）中最好的不是很好，则匹配会受到很大的惩罚，但我们不会不要严重惩罚两个分数中最差的一个。从本质上讲，这强调要求 valueWord 或 valuePhrase 有一个好分数，但不能两者兼而有之。一种“拿走我们能得到的”的心态。

这 5 个权重的优化值说明了正在发生的模糊字符串匹配，这真是令人着迷。对于完全不同的模糊字符串匹配的实际情况，这些参数是非常不同的。到目前为止，我已经将它用于 3 个单独的应用程序。

虽然在最终优化中未使用，但建立了一个基准表，该表将列与其自身匹配以获得对角线下的所有完美结果，并允许用户更改参数以控制分数偏离 0 的速率，并注意搜索短语之间的内在相似性（理论上可以用来抵消结果中的误报）

https://i.stack.imgur.com/XV5Wp.png

进一步的应用

该解决方案有可能用于用户希望计算机系统识别一组字符串中不存在完美匹配的字符串的任何地方。 （就像字符串的近似匹配vlookup）。

因此，您应该从中得到的，是您可能希望结合使用高级启发式算法（从另一个短语中的一个短语中查找单词、两个短语的长度等）以及 Levenshtein 距离算法的实现。因为决定哪个是“最佳”匹配是一种启发式（模糊）确定 - 您必须为您提出的任何指标提出一组权重以确定相似性。

使用适当的启发式方法和权重，您可以让您的比较程序快速做出您可能做出的决定。

---

这个问题在生物信息学中一直存在。上面接受的答案（顺便说一句很棒）在生物信息学中被称为 Needleman-Wunsch（比较两个字符串）和 Smith-Waterman（在更长的字符串中找到近似子字符串）算法。他们工作得很好，几十年来一直是主力。

但是如果你有一百万个字符串要比较呢？这是一万亿次成对比较，每一个都是 O(n*m)！现代 DNA 测序仪很容易生成十亿个短 DNA 序列，每个序列大约 200 个 DNA“字母”长。通常，我们希望为每个这样的字符串找到与人类基因组（30 亿个字母）的最佳匹配。显然，Needleman-Wunsch 算法及其相关算法不会这样做。

这个所谓的“对齐问题”是一个活跃的研究领域。目前最流行的算法能够在合理的硬件（例如 8 个内核和 32 GB RAM）上在几个小时内找到 10 亿个短字符串与人类基因组之间的不精确匹配。

大多数这些算法的工作原理是快速找到短的完全匹配（种子），然后使用较慢的算法（例如，Smith-Waterman）将它们扩展到完整的字符串。这样做的原因是我们真的只对少数几场比赛感兴趣，所以摆脱 99.9...% 的没有共同点的配对是值得的。

查找完全匹配项如何帮助查找 inexact 项匹配项？好吧，假设我们只允许查询和目标之间存在单一差异。很容易看出，这种差异必须出现在查询的右半部分或左半部分，因此另一半必须完全匹配。这个想法可以扩展到多个错配，并且是 Illumina DNA 测序仪常用的 ELAND 算法的基础。

有许多非常好的算法可以进行精确的字符串匹配。给定一个长度为 200 的查询字符串和一个长度为 30 亿的目标字符串（人类基因组），我们希望在目标中找到与查询的子字符串完全匹配的长度为 k 的子字符串的任何位置。一种简单的方法是从对目标进行索引开始：获取所有 k 长子字符串，将它们放入一个数组中并对其进行排序。然后获取查询的每个 k 长子字符串并搜索排序索引。排序和搜索可以在 O(log n) 时间内完成。

但是存储可能是个问题。 30 亿个字母目标的索引需要包含 30 亿个指针和 30 亿个 k-long 单词。在不到几十 GB 的 RAM 中安装它似乎很困难。但令人惊讶的是，我们可以使用 Burrows-Wheeler transform 大大压缩索引，并且它仍然可以有效地查询。人类基因组的索引可以容纳在不到 4 GB 的 RAM 中。这个想法是流行的序列比对器（例如 Bowtie 和 BWA）的基础。

或者，我们可以使用 suffix array，它只存储指针，但表示目标字符串中所有后缀的同时索引（本质上，k 的所有可能值的同时索引；Burrows-Wheeler 也是如此转换）。如果我们使用 32 位指针，人类基因组的后缀数组索引将占用 12 GB 的 RAM。

上面的链接包含大量信息和指向主要研究论文的链接。 ELAND 链接指向一个 PDF，其中包含说明所涉及概念的有用图表，并展示了如何处理插入和删除。

最后，虽然这些算法已经基本解决了（重新）测序单个人类基因组（十亿个短字符串）的问题，但 DNA 测序技术的改进速度甚至超过了摩尔定律，我们正在快速接近万亿字母的数据集。例如，目前正在进行对 10,000 vertebrate species 的基因组进行测序的项目，每个基因组长约十亿个字母。自然，我们会希望对数据进行成对的不精确字符串匹配......

---

我认为选项 B 更接近测试字符串，因为它距离原始字符串只有 4 个字符（和 2 个删除）。而您认为 C 更接近，因为它包括棕色和红色。但是，它将具有更大的编辑距离。

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

Here 是该算法的工具。

将选项 A 评为距离 15。将选项 B 评为距离 6。将选项 C 评为距离 9。

编辑：对不起，我一直在 levenshtein 工具中混合字符串。更新为正确答案。

---

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

---

你可能会发现这个库很有帮助！ http://code.google.com/p/google-diff-match-patch/

它目前可用于 Java、JavaScript、Dart、C++、C#、Objective C、Lua 和 Python

它也很好用。我在几个 Lua 项目中使用它。

而且我认为将其移植到其他语言不会太难！

---

您可能对这篇博文感兴趣。

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

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

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

---

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

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

此外，使用 Solr，您可以通过 JSON 按需搜索索引，因此您不必在正在查看的不同语言之间重新设计解决方案。

---

Simmetrics 是此类算法的一个非常非常好的资源：http://sourceforge.net/projects/simmetrics/

不幸的是，包含大量文档的很棒的网站已经消失了 :( 如果它再次出现，它之前的地址是这样的：http://www.dcs.shef.ac.uk/~sam/simmetrics.html

瞧（由“Wayback Machine”提供）：http://web.archive.org/web/20081230184321/http://www.dcs.shef.ac.uk/~sam/simmetrics.html

您可以研究代码源，有数十种算法可用于此类比较，每种算法都有不同的权衡。实现是在 Java 中的。

---

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

编辑距离 ED(x,y)：从术语 x 到术语 y 的最小转换次数

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

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

调整 QGram 索引的一种可能方法是使用 Qgram 构建倒排索引。在那里，我们将所有包含特定 Qgram 的单词存储在该 Qgram 下。（而不是存储完整的字符串，您可以为每个字符串使用唯一的 ID）。为此，您可以使用 Java 中的 Tree Map 数据结构。以下是一个关于存储术语的小例子

col : colmbia, colombo, gancola, tacolama

然后在查询时，我们计算查询文本和可用术语之间的常见 Qgram 数量。

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。

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

您可以在以下项目中找到该理论的实现（参见“QGramIndex.java”）。随意问任何问题。 https://github.com/Bhashitha-Gamage/City_Search

要了解更多关于编辑距离、前缀编辑距离 Qgram 索引的信息，请观看 Hannah Bast 教授的以下视频https://www.youtube.com/embed/6pUg2wmGJRo（课程从 20:06 开始）

---

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

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

只需将所有输入数据插入数据库，您就可以根据任何编辑距离快速搜索任何字符串。这是一个 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))
    )
));

---

在这里，您可以使用 golang POC 来计算给定单词之间的距离。您可以针对其他范围调整 minDistance 和 difference。

游乐场：https://play.golang.org/p/NtrBzLdC3rE

package main

import (
    "errors"
    "fmt"
    "log"
    "math"
    "strings"
)

var data string = `THE RED COW JUMPED OVER THE GREEN CHICKEN-THE RED COW JUMPED OVER THE RED COW-THE RED FOX JUMPED OVER THE BROWN COW`

const minDistance float64 = 2
const difference float64 = 1

type word struct {
    data    string
    letters map[rune]int
}

type words struct {
    words []word
}

// Print prettify the data present in word
func (w word) Print() {
    var (
        lenght int
        c      int
        i      int
        key    rune
    )
    fmt.Printf("Data: %s\n", w.data)
    lenght = len(w.letters) - 1
    c = 0
    for key, i = range w.letters {
        fmt.Printf("%s:%d", string(key), i)
        if c != lenght {
            fmt.Printf(" | ")
        }
        c++
    }
    fmt.Printf("\n")
}

func (ws words) fuzzySearch(data string) ([]word, error) {
    var (
        w      word
        err    error
        founds []word
    )
    w, err = initWord(data)
    if err != nil {
        log.Printf("Errors: %s\n", err.Error())
        return nil, err
    }
    // Iterating all the words
    for i := range ws.words {
        letters := ws.words[i].letters
        //
        var similar float64 = 0
        // Iterating the letters of the input data
        for key := range w.letters {
            if val, ok := letters[key]; ok {
                if math.Abs(float64(val-w.letters[key])) <= minDistance {
                    similar += float64(val)
                }
            }
        }

        lenSimilarity := math.Abs(similar - float64(len(data)-strings.Count(data, " ")))
        log.Printf("Comparing %s with %s i've found %f similar letter, with weight %f", data, ws.words[i].data, similar, lenSimilarity)
        if lenSimilarity <= difference {
            founds = append(founds, ws.words[i])
        }
    }

    if len(founds) == 0 {
        return nil, errors.New("no similar found for data: " + data)
    }

    return founds, nil
}

func initWords(data []string) []word {
    var (
        err   error
        words []word
        word  word
    )
    for i := range data {
        word, err = initWord(data[i])
        if err != nil {
            log.Printf("Error in index [%d] for data: %s", i, data[i])
        } else {
            words = append(words, word)
        }
    }
    return words

}

func initWord(data string) (word, error) {
    var word word

    word.data = data
    word.letters = make(map[rune]int)
    for _, r := range data {
        if r != 32 { // avoid to save the whitespace
            word.letters[r]++
        }

    }
    return word, nil
}
func main() {
    var ws words
    words := initWords(strings.Split(data, "-"))
    for i := range words {
        words[i].Print()
    }
    ws.words = words

    solution, _ := ws.fuzzySearch("THE BROWN FOX JUMPED OVER THE RED COW")
    fmt.Println("Possible solutions: ", solution)

}

---

使用 C# is here 的示例。

public static void Main()
{
    Console.WriteLine("Hello World " + LevenshteinDistance("Hello","World"));
    Console.WriteLine("Choice A " + LevenshteinDistance("THE BROWN FOX JUMPED OVER THE RED COW","THE RED COW JUMPED OVER THE GREEN CHICKEN"));
    Console.WriteLine("Choice B " + LevenshteinDistance("THE BROWN FOX JUMPED OVER THE RED COW","THE RED COW JUMPED OVER THE RED COW"));
    Console.WriteLine("Choice C " + LevenshteinDistance("THE BROWN FOX JUMPED OVER THE RED COW","THE RED FOX JUMPED OVER THE BROWN COW"));
}

public static float LevenshteinDistance(string a, string b)
{
    var rowLen = a.Length;
    var colLen = b.Length;
    var maxLen = Math.Max(rowLen, colLen);

    // Step 1
    if (rowLen == 0 || colLen == 0)
    {
        return maxLen;
    }

    /// Create the two vectors
    var v0 = new int[rowLen + 1];
    var v1 = new int[rowLen + 1];

    /// Step 2
    /// Initialize the first vector
    for (var i = 1; i <= rowLen; i++)
    {
        v0[i] = i;
    }

    // Step 3
    /// For each column
    for (var j = 1; j <= colLen; j++)
    {
        /// Set the 0'th element to the column number
        v1[0] = j;

        // Step 4
        /// For each row
        for (var i = 1; i <= rowLen; i++)
        {
            // Step 5
            var cost = (a[i - 1] == b[j - 1]) ? 0 : 1;

            // Step 6
            /// Find minimum
            v1[i] = Math.Min(v0[i] + 1, Math.Min(v1[i - 1] + 1, v0[i - 1] + cost));
        }

        /// Swap the vectors
        var vTmp = v0;
        v0 = v1;
        v1 = vTmp;
    }

    // Step 7
    /// The vectors were swapped one last time at the end of the last loop,
    /// that is why the result is now in v0 rather than in v1
    return v0[rowLen];
}

输出是：

Hello World 4
Choice A 15
Choice B 6
Choice C 8

---

我曾经在我们的系统中实施了另一种相似性度量并给出了令人满意的结果：-

用例

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

算法

从用户查询中提取关键字（相关词性标签 - 名词、专有名词）。现在根据以下公式计算分数，以测量用户查询与给定文档之间的相似性。

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

开始在文档中搜索给定的单词，并且对于文档中该单词的每一次后续出现，都会减少奖励积分。

本质上，如果第一个关键字在文档中出现 4 次，则分数将计算为：-

第一次出现将获取“1”点。

第二次出现将增加 1/2 到计算的分数

第三次出现将使总数增加 1/3

第四次出现得到 1/4

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

同样，我们为用户查询中的其他关键字计算它。

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

---