获取最接近的字符串匹配

Question

我需要一种方法来将多个字符串与测试字符串进行比较并返回与其非常相似的字符串：（

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。此时，伪代码是可以接受的。如果您可以提供特定语言的示例，我们也将不胜感激！

Answer 1

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

研究的一部分涉及实施 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 根据分隔符（例如空格、破折号和任何您想要的其他内容）将字符串拆分为单个单词，并将每个单词与其他单词进行比较，总结出最短的单词连接任意两个单词的编辑距离。本质上，它衡量一个“短语”中的信息是否真正包含在另一个“短语”中，就像按单词排列一样。我花了几天时间作为一个业余项目，想出了根据分隔符分割字符串的最有效方法。

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

相似度测量

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

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

在上面的屏幕截图中，我调整了我的启发式方法，得出了一些我认为可以很好地适应我的感知的东西搜索词和结果之间的差异。我在上述电子表格中用于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%。这只是一个适合我的用例以获得良好匹配率的启发式方法。然后可以调整这些权重以获得与其测试数据的最佳匹配率。

正如您所看到的，最后两个指标（模糊字符串匹配指标）已经自然倾向于为要匹配的字符串（沿对角线）提供低分。这很好。

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

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

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

该算法取得了巨大的成功，解决方案参数充分说明了此类问题。您会注意到优化分数是 44，最佳分数是 48。最后的 5 列是诱饵，与行值根本没有任何匹配。诱饵越多，自然就越难找到最佳匹配。

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

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

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

这 5 个权重的优化值对所发生的模糊字符串匹配的描述非常有趣。对于完全不同的模糊字符串匹配的实际情况，这些参数有很大不同。到目前为止我已经将它用于 3 个独立的应用程序。

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

其他应用

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

---

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

通过适当的启发式和权重集，您的比较程序将快速做出您本来会做出的决定。

Answer 2

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

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

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

大多数这些算法的工作原理是快速查找短的精确匹配（种子），然后使用较慢的算法（例如 Smith-Waterman）将它们扩展为完整字符串。这样做的原因是我们实际上只对一些势均力敌的比赛感兴趣，因此消除 99.9...% 没有任何共同点的配对是值得的。

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

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

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

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

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

最后，虽然这些算法基本上解决了对单个人类基因组（十亿个短字符串）进行（重新）测序的问题，但 DNA 测序技术的进步速度甚至比摩尔定律还要快，而且我们正在快速接近万亿字母的数据集。例如，目前正在进行的项目对10,000 个脊椎动物物种进行基因组测序，每个物种大约有十亿个字母长。当然，我们希望对数据进行成对的不精确字符串匹配......

Answer 3

我认为选项 B 更接近测试字符串，因为它与原始字符串只有 4 个字符（和 2 个删除）。而您认为 C 更接近，因为它同时包含棕色和红色。然而，它会有更大的编辑距离。

有一种名为 Levenshtein Distance 的算法，用于测量两个输入之间的编辑距离。

这里是该算法的工具。

1. 将选择 A 的距离设为 15。
2. 将选择 B 的距离设为 6。
3. 将选择 C ​​的距离设为 9。

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

Answer 4

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

Answer 5

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

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

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

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

Answer 6

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

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/

Answer 7

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

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

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

Answer 8

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

快速入门：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))
    )
));

Answer 9

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 实现的。

Answer 10

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

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

Answer 11

在这里你可以有一个 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)

}

Answer 12

使用 C# 的示例位于此处。

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

Answer 13

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

用例

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

算法

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

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

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

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

• 第一次出现将获取“1”分。
• 第二次出现将在计算得分中添加 1/2
• 第三次出现将在总得分中添加 1/3
• 第四次出现将获得 1/4

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

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

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

Answer 14

这是一个不依赖于任何库的快速解决方案，并且对于自动完成表单之类的事情来说效果很好：

function compare_strings(str1, str2) {
    arr1 = str1.split("");
    arr2 = str2.split("");
    res = arr1.reduce((a, c) => a + arr2.includes(c), 0);
    return(res)
}

可以在自动完成输入中使用，如下所示：

HTML：

<div id="wrapper">
    <input id="tag_input" placeholder="add tags..."></input>
    <div id="hold_tags"></div>
</div>

CSS：

body {
  background: #2c2c54;
  display: flex;
  justify-content: center;
  align-items: center;
}

input {
  height: 40px;
  width: 400px;
  border-radius: 4px;
  outline: 0;
  border: none;
  padding-left: 5px;
  font-size: 18px;
}

#wrapper {
  height: auto;
  background: #40407a;
}

.tag {
  background: #ffda79;
  margin: 4px;
  padding: 5px;
  border-radius: 4px;
  box-shadow: 2px 2px 2px black;
  font-size: 18px;
  font-family: arial;
  cursor: pointer;
}

JS：

const input = document.getElementById("tag_input");
const wrapper = document.getElementById("wrapper");
const hold_tags = document.getElementById("hold_tags");
const words = [
  "machine",
  "data",
  "platform",
  "garbage",
  "twitter",
  "knowledge"
];
input.addEventListener("input", function (e) {
  const value = document.getElementById(e.target.id).value;
  hold_tags.replaceChildren();
  if (value !== "") {
    words.forEach(function (word) {
      if (compare_strings(word, value) > value.length - 1) {
        const tag = document.createElement("div");
        tag.className = "tag";
        tag.innerText = word;
        hold_tags.append(tag);
      }
    });
  }
});

function compare_strings(str1, str2) {
  arr1 = str1.split("");
  arr2 = str2.split("");
  res = arr1.reduce((a, c) => a + arr2.includes(c), 0);
  return res;
}

结果：