我需要一种方法来将多个字符串与测试字符串进行比较，并返回与其非常相似的字符串：
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。此时，伪代码是可以接受的。如果您可以提供特定语言的示例，这也是值得赞赏的！
大约一年前，当我查找用户在杂项信息数据库中输入有关石油钻井平台的信息时，我遇到了这个问题。目标是进行某种模糊字符串搜索，以便识别具有最常见元素的数据库条目。
部分研究涉及实施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
相似度量
使用这两个指标，第三个只是计算两个字符串之间的距离，我有一系列变量，我可以运行一个优化算法来实现最大数量的匹配。模糊字符串匹配本身就是一种模糊科学，因此通过创建线性独立的度量来测量字符串相似性，并且我们希望彼此匹配的已知字符串集合，我们可以找到针对我们特定样式的参数。字符串，给出最佳的模糊匹配结果。
最初，度量标准的目标是为完全匹配提供较低的搜索值，并为越来越多的置换度量增加搜索值。在一个不切实际的情况下，使用一组明确定义的排列很容易定义，并且设计最终公式使得它们具有所需的增加的搜索值结果。
在上面的截图中，我调整了我的启发式，以便得出一些我觉得可以很好地缩放到我在搜索项和结果之间的感知差异的东西。我在上面的电子表格中用于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距离算法的实现。因为决定哪个是“最佳”匹配是一种启发式（模糊）确定 - 你必须为你提出的任何指标提出一组权重来确定相似性。
通过适当的启发式和权重集，您可以让您的比较程序快速做出您可能做出的决定。
如果输入数据太大（例如数百万字符串），则难以实现该问题。我使用弹性搜索来解决这个问题。
快速入门：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))
)
));
这个问题一直在生物信息学中出现。上面接受的答案（顺便提一下）在生物信息学中被称为Needleman-Wunsch（比较两个字符串）和Smith-Waterman（在较长字符串中找到近似子字符串）算法。他们工作得很好，几十年来一直在努力。
但是如果你有一百万个字符串要比较呢？这是一个万亿的成对比较，每个都是O（n * m）！现代DNA测序仪很容易产生十亿个短DNA序列，每个DNA序列长约200个DNA。通常，我们希望为每个这样的字符串找到与人类基因组最佳匹配（30亿个字母）。显然，Needleman-Wunsch算法及其亲属不会这样做。
这种所谓的“对齐问题”是一个积极研究的领域。最流行的算法目前能够在合理的硬件（例如，8个核心和32 GB RAM）上在几个小时内找到10亿个短串和人类基因组之间的不精确匹配。
这些算法中的大多数通过快速找到短精确匹配（种子）然后使用较慢的算法（例如，Smith-Waterman）将它们扩展到完整字符串来工作。这样做的原因是我们真的只对一些近距离比赛感兴趣，所以摆脱99.9％没有共同点的对的成功是值得的。
如何找到完全匹配有助于找到不精确的匹配？好吧，假设我们只允许查询和目标之间的单一差异。很容易看出，这种差异必须出现在查询的右半部分或左半部分，因此另一半必须完全匹配。这个想法可以扩展到多个不匹配，并且是Illumina DNA测序仪常用的ELAND算法的基础。
有许多非常好的算法可以进行精确的字符串匹配。给定长度为200的查询字符串和长度为30亿的目标字符串（人类基因组），我们希望找到目标中存在长度为k的子字符串的任何位置，该子字符串与查询的子字符串完全匹配。一个简单的方法是从索引目标开始：获取所有k-long子串，将它们放入一个数组中并对它们进行排序。然后获取查询的每个k-long子字符串并搜索已排序的索引。 排序和 搜索可以在O（log n）时间内完成。
但存储可能是个问题。一个30亿字母目标的指数需要拥有30亿个指针和30亿个k字长。看起来很难将其安装在不到几十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是该算法的工具。
编辑：对不起，我在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://seatgeek.com/blog/dev/fuzzywuzzy-fuzzy-string-matching-in-python
Fuzzywuzzy是一个Python库，提供简单的距离测量，例如Levenshtein距离，用于字符串匹配。它构建在标准库中的difflib之上，如果可用的话，它将使用C实现Python-levenshtein。
您可能会发现此库很有用！ http://code.google.com/p/google-diff-match-patch/
它目前提供Java，JavaScript，Dart，C ++，C＃，Objective C，Lua和Python
它的效果也很好。我在几个Lua项目中使用它。
而且我认为将它移植到其他语言并不太难！
如果您在搜索引擎或数据库前端的上下文中执行此操作，您可以考虑使用Apache Solr插件等ComplexPhraseQueryParser工具。此组合允许您搜索字符串索引，其结果按相关性排序，由Levenshtein距离确定。
当传入的查询可能有一个或多个拼写错误时，我们一直在对大量的艺术家和歌曲集合使用它，并且它的工作非常好（并且考虑到集合数百万字符串，速度非常快）。
此外，使用Solr，您可以通过JSON按需搜索索引，因此您不必在您正在查看的不同语言之间重新构建解决方案。
这些算法的非常非常好的资源是Simmetrics：http://sourceforge.net/projects/simmetrics/
不幸的是，包含大量文档的精彩网站已经不见了:(如果它再次出现，它之前的地址是：http://www.dcs.shef.ac.uk/~sam/simmetrics.html
Voila（由“Wayback Machine”提供）：http://web.archive.org/web/20081230184321/http://www.dcs.shef.ac.uk/~sam/simmetrics.html
您可以研究代码源，这些类型的比较有很多算法，每种算法都有不同的权衡。实现是Java。
要以有效的方式查询大量文本，可以使用“编辑距离/前缀编辑距离”的概念。
编辑距离ED（x，y）：从术语x到术语y的最小变换数
但是，在每个术语和查询文本之间计算ED是资源和时间密集的。因此，我们不是首先计算每个项的ED，而是使用称为Qgram Index的技术提取可能的匹配项。然后对这些选定的术语应用ED计算。
Qgram索引技术的一个优点是它支持模糊搜索。
调整QGram索引的一种可能方法是使用Qgrams构建倒置索引。在那里，我们存储在Qgram下包含特定Qgram的所有单词。（而不是存储完整字符串，您可以为每个字符串使用唯一ID）。您可以在Java中使用Tree Map数据结构。以下是存储术语的一个小例子
col：colmbia，colombo，gancola，tacolama
然后在查询时，我们计算查询文本和可用术语之间的常见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开始）