获得最接近的字符串匹配

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“应该是”选择C“。什么是最简单的方法来做到这一点？

我打算将其实现为包括VB.net，Lua和JavaScript在内的多种语言。在这一点上，伪代码是可以接受的。如果你可以提供一个特定语言的例子，这也是赞赏！

Answer 1

大约一年前，当我在一个杂项信息的数据库中查询用户输入的石油钻井平台信息时，出现了这个问题。目标是做一些模糊的字符串搜索，可以用最常见的元素来标识数据库条目。

部分研究涉及实现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和斯普利特功能：类似的

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偏离的比率，并注意天生的相似性搜索短语（在理论上可以被用来抵消误报的结果）之间

进一步应用

该解决方案有潜力成为在用户希望有一个计算机系统识别一组字符串中没有完美匹配的字符串时使用。 （就像一个近似的匹配查找字符串）。

---

所以，你应该采取什么样的从这个，就是你可能要与执行一起使用的高级启发式组合（找到的话从其他词组一个词组，无论短语的长度等）的Levenshtein距离算法。因为决定哪一个是“最佳”匹配是一个启发式（模糊）决定 - 您必须为您提出的任何度量提供一组权重来确定相似度。

与适当的启发和权重的，你有你比较程序快速进行，你会作出的决定。

Answer 2

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

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

Here是该算法的工具。

1. 价格选择A作为作为6.
2. 价格选项C的距离为9

EDIT的距离15.

价格选择B的距离：对不起，我继续在levenshtein工具中混合字符串。更新为正确的答案。

Answer 3

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 4

您可能会感兴趣的这篇博客。

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 5

这个问题变成了生物信息学中所有的时间。上述接受的答案（这是由伟大的方式）的生物信息学作为尼德曼 - 翁施（比较两个字符串）和史密斯 - 沃特曼是已知的算法（在更长的字符串进行粗略子）。他们工作得很好，几十年来一直是工人。

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

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

大部分通过快速查找短精确匹配（种子），然后使用较慢的算法（例如对，Smith-沃特曼）这些延伸至所述完整的字符串这些算法的工作。这样做的原因是我们真的只对几次近距离比赛感兴趣，因此可以摆脱99.9％没有任何共同点的球队。

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

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

但存储可能是一个问题。 30亿信件目标的指标需要持有30亿个指针和30亿个长的字。这似乎很难适应这少于几十千兆字节的RAM。但令人惊讶的是，我们可以使用Burrows-Wheeler transform大大缩减索引，并且仍然可以高效查询。人类基因组的索引可以适用于小于4 GB的RAM。这个想法是流行的序列对齐方法的基础，例如Bowtie和BWA。

可替代地，我们可以使用一个suffix array，仅存储指针，但表示在目标串（所有后缀的同时指数基本上，对于k的所有可能值的同时索引;同样是挖洞的真 - 惠勒变换）。如果我们使用32位指针，人类基因组的后缀数组索引将需要12 GB的RAM。

上述链接包含丰富的信息和主要研究论文的链接。 ELAND链接转到PDF，其中包含说明涉及的概念的有用数字，并演示如何处理插入和删除操作。最后，尽管这些算法已经基本解决了单个人类基因组（测序数十亿个短字符串）的（重新）排序问题，但DNA测序技术的改进速度比摩尔定律更快，而且我们正在快速接近万亿字母数据集。例如，目前有一些项目正在进行序列号为10,000 vertebrate species的基因组测序，每个基因组长度为十亿字左右。当然，我们将要进行数据的配对不精确的字符串匹配...

Answer 6

一个非常，对于这些类型的算法非常好的资源是Simmetrics：http://sourceforge.net/projects/simmetrics/

不幸的是含有大量文档的网站真棒走了:( 如果它再回来了，它以前的地址是这样的： http://www.dcs.shef.ac.uk/~sam/simmetrics.html

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

你可以学习的代码，以便urce，这些比较有几十种算法，每种算法都有不同的权衡。这些实现使用Java。

Answer 7

如果您是在搜索引擎或前端对数据库的上下文中执行此操作，则可以考虑使用Apache Solr之类的工具和ComplexPhraseQueryParser插件。这种组合使您能够根据Levenshtein距离确定的结果按照相关性排序的字符串索引进行搜索。

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

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

Answer 8

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

这是目前的Java，JavaScript中，飞镖，C++，C＃，目标C，Lua和Python的

可用它工作得很好了。我在几个我的Lua项目中使用它。

而且我不认为将其转换为其他语言会太困难！

Answer 9

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

编辑距离ED（X，Y）：transfroms的最少数量从项x到达长期Ÿ

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

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

适应QGram索引的一种可能方法是使用Qgrams构建倒转索引。在那里，我们存储所有包含特定Qgram的单词，在该Qgram下（不是存储完整的字符串，您可以为每个字符串使用唯一的ID）。你可以在Java中使用Tree Map数据结构来实现这一点。 以下是对条款

的存储一个小例子

西：山坳 MBIA，山坳姆翁布，甘山坳一个，TA 山坳 AMA

然后查询，我们什么时候计算查询文本和可用条款之间常见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-克普通= 4

对于具有高数量的公共Qgrams的方面，我们计算对所述查询术语的ED/PED然后建议的术语给终端用户。

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

研究更多关于编辑距离，前缀编辑距离Qgram指数敬请观看汉娜麻类https://www.youtube.com/embed/6pUg2wmGJRo教授博士（课程从20:06开始）

Answer 10

的问题是很难的以下视频如果输入实现数据太大（说数百万字符串）。我用弹性搜索来解决这个问题。只需将所有输入数据插入到数据库中，并且可以根据任何编辑距离快速搜索任何字符串。这里是一个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)) 
    ) 
));