获得最接近的string匹配
我需要一种方法将多个string与testingstring进行比较，并返回与其非常相似的string：
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”最接近的string应该是“CHOICE C”。 什么是最简单的方法来做到这一点？
我计划将其实现为包括VB.net，Lua和JavaScript在内的多种语言。 在这一点上，伪代码是可以接受的。 如果你能提供一个特定语言的例子，这也是赞赏！
大约一年前，当我在一个杂项信息数据库中查询用户input的石油钻井平台的信息时，我遇到了这个问题。 目标是做一些模糊的stringsearch，可以识别最常见元素的数据库条目。
部分研究涉及实现Levenshtein距离algorithm，该algorithm确定必须对string或短语进行多less更改才能将其转换为另一个string或短语。
我提出的实现相对简单，包括两个短语长度的加权比较，每个短语之间的变化次数以及每个单词是否可以在目标条目中find。
文章是在一个私人网站上，所以我会尽我所能在这里附上相关的内容：
模糊string匹配是对两个单词或短语进行类似人类估计的过程。 在很多情况下，它涉及识别彼此最相似的词或短语。 本文介绍了模糊string匹配问题的内部解决scheme及其在解决各种问题方面的实用性，这些问题可以使我们自动执行以前需要繁琐的用户参与的任务。
介绍
开发模糊string匹配的需求最初是在开发墨西哥湾validation工具时才产生的。 现在已经有一个墨西哥湾石油钻井平台的数据库，购买保险的人会给我们一些关于他们资产的错误信息，我们必须把它与已知平台的数据库相匹配。 当信息非常less时，我们所能做的最好的就是依靠承销商来“认识”他们所指的那个人，并调出正确的信息。 这是自动化解决scheme派上用场的地方。
我花了一天的时间研究模糊string匹配的方法，最终偶然发现了维基百科上非常有用的Levenshtein距离algorithm。
履行
在阅读了它背后的理论之后，我实现并find了优化它的方法。 这是我的代码在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
简单，快速，是一个非常有用的指标。 使用这个，我创build了两个单独的度量来评估两个string的相似性。 一个我叫“valuePhrase”，另一个叫“valueWords”。 valuePhrase就是这两个短语之间的Levenshtein距离，valueWords将string分割成单独的单词，基于分隔符（如空格，破折号和其他任何您想要的），并将每个单词与每个单词进行比较，总结出最短连接任何两个单词的Levenshtein距离。 从本质上讲，它是衡量一个“短语”中的信息是否真的被包含在另一个中，就像一个词的置换一样。 我花了几天的时间做了一个侧面项目，以最有效的方式分割基于分隔符的string。
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
相似的措施
使用这两个度量和第三个简单的计算两个string之间的距离，我有一系列的variables，我可以运行一个优化algorithm，以实现最大数量的匹配。 模糊string匹配本身就是一门模糊科学，所以通过创build用于度量string相似度的线性独立度量标准，并且拥有一组我们希望彼此匹配的已知string集合，我们可以find参数，对于我们的特定样式string，给出最好的模糊匹配结果。
最初，该度量标准的目标是为了精确匹配而具有低search值，并且针对越来越多的置换度量而增加search值。 在不切实际的情况下，使用一组定义良好的置换来定义相当容易，并且devise最终公式以使得它们具有所期望的增加的search值结果。
在上面的屏幕截图中，我调整了启发式方法，想出了一些我觉得可以很好地缩放search词和search结果之间差异的东西。 在上面的电子表格中，我用于Value Phrase的启发式是=valuePhrase(A2,B2)-0.8*ABS(LEN(B2)-LEN(A2)) 。 我有效地将Levenstein距离的惩罚减less了两个“短语”长度的80％。 这样，长度相同的“短语”就会受到全面的惩罚，但是包含“附加信息”（更长）但除此之外大部分共享相同字符的“短语”受到的惩罚也会降低。 我使用Value Words函数，然后将我的最终SearchVal启发式定义为=MIN(D2,E2)*0.8+MAX(D2,E2)*0.2 – 一个加权平均值。 无论哪一个分数较低分别为80％和20％。 这只是一个适合我的用例，以获得良好的匹配率的启发式。 这些权重是一个可以调整，以获得与他们的testing数据的最佳匹配率的东西。
正如你所看到的，最后两个指标是模糊的string匹配度量标准，已经有一种自然的倾向，就是低的分数来匹配（匹配对angular线的）string。 这是非常好的。
应用为了允许模糊匹配的优化，我加权每个度量。 这样，模糊string匹配的每个应用都可以对参数进行不同的加权。 定义最终分数的公式是度量标准与其权重的简单组合：
value = Min(phraseWeight*phraseValue, wordsWeight*wordsValue)*minWeight + Max(phraseWeight*phraseValue, wordsWeight*wordsValue)*maxWeight + lengthWeight*lengthValue
使用优化algorithm（neural network在这里是最好的，因为它是一个离散的多维问题），现在的目标是最大化匹配的数量。 我创build了一个函数来检测每个集合相互之间的正确匹配的数量，在这个最终的截图中可以看到。 如果最低分数被指定为要匹配的string，则列或行获得一个分数，如果最低分数存在平局，则给出部分分数，并且匹配的匹配string之间是正确的匹配。 然后我优化了它。 您可以看到，绿色单元格是与当前行最匹配的列，而单元格周围的蓝色正方形是与当前列最匹配的行。 底angular的得分大概是成功的比赛数量，这就是我们告诉我们的优化问题最大化。
该algorithm是一个非常成功的解决scheme参数说了很多关于这种types的问题。 您会注意到优化的分数是44，最好的分数是48.最后的5列是诱饵，并且根本没有任何匹配的行值。 越多的诱饵越难find最好的匹配。
在这个特定的匹配情况下，string的长度是不相关的，因为我们期望代表较长字的缩写，所以长度的最佳权重是-0.3，这意味着我们不惩罚长度不同的string。 我们降低了预期这些缩写的分数，为部分词语匹配提供了更多的空间，取代了非单词匹配，因为string更短，所以只需要更less的replace。
词的权重是1.0，而词组的权重只有0.5，这意味着我们惩罚从一个string中缺less的整个单词，并更多的价值更完整的整个短语。 这是很有用的，因为很多这些string有一个共同的字（危险），真正重要的是组合（区域和危险）是否保持。
最后，最小权重优化为10，最大权重为1.这意味着，如果两个分数中最好的（价值词和价值词）不是很好，那么这个匹配就会受到很大的惩罚，但是我们不会对这两个分数中最糟糕的一点不会很大的惩罚。 实质上，这强调要求valueWord或valuePhrase具有良好的分数，但不是两者兼而有之。 一种“拿我们能得到”的心态。
这5个权重的优化值对于发生模糊string匹配的种类来说真的很吸引人。 对于模糊string匹配的完全不同的实际情况，这些参数是非常不同的。 到目前为止我已经使用了3个独立的应用程序。
虽然在最终的优化中没有使用，但build立了一个基准表，它可以与对angular线上的所有完美结果进行匹配，并允许用户通过改变参数来控制分数从0偏离的速率，并注意search短语之间的固有相似性这在理论上可以用来抵消结果中的误报）
其他应用
这个解决scheme有可能在用户希望有一个计算机系统识别没有完美匹配的一组string的string的任何地方使用。 （就像一个近似的匹配查找string）。
所以你应该从中得到什么，你可能想要结合使用高级启发式（从另一个短语中的一个短语中find单词，两个短语的长度等）以及Levenshtein距离algorithm的实现。 因为决定哪一个是“最佳”匹配是一个启发式（模糊）决定 – 您必须为您提出的任何度量提供一组权重来确定相似度。
通过适当的启发式和权重设置，您可以快速地进行比较程序，从而做出您将要做出的决定。
这个问题一直在生物信息学中出现。 上面所接受的答案（这很好）在生物信息学中被称为Needleman-Wunsch（比较两个string）和Smith-Waterman（在较长的string中find一个近似的子string）algorithm。 他们工作很好，几十年来一直在努力工作。
但是如果你有一百万个string比较呢？ 这是几万亿的两两比较，每一个都是O（n * m）！ 现代DNA测序仪容易产生十亿个短的DNA序列，每个DNA序列长约200个“字母”。 通常，我们希望find每个这样的string，与人类基因组（30亿字母）的最佳匹配。 显然，Needleman-Wunschalgorithm及其亲属不会这样做。
这个所谓的“alignment问题”是一个积极的研究领域。 目前最stream行的algorithm能够在合理的硬件上（例如，8核心和32 GB RAM）在数小时内find10亿个短string和人类基因组之间的不精确匹配。
大多数这些algorithm的工作原理是快速find简短的精确匹配（种子），然后使用较慢的algorithm（例如Smith-Waterman）将这些algorithm扩展为完整的string。 这样做的原因是我们真的只对几个近距离比赛感兴趣，所以它摆脱了99.9％没有任何共同点的对。
如何find精确匹配有助于find不精确的匹配？ 那么，说我们只允许查询和目标之间的一个单一的差异。 很容易看出，这种差异必须出现在查询的右半部分或左半部分，因此另一半必须完全匹配。 这个想法可以扩展到多个不匹配，并且是Illumina DNA测序仪常用的ELANDalgorithm的基础。
有很多非常好的algorithm来做精确的string匹配。 给定一个长度为200的查询string和一个长度为30亿（人类基因组）的目标string，我们希望在目标中find长度为k的子string与查询的子string完全匹配的任何地方。 一个简单的方法是从索引目标开始：取所有的k-long子串，把它们放在一个数组中并对它们进行sorting。 然后取查询的每个k长的子串并searchsorting的索引。 sorting和search可以在O（log n）时间完成。
但存储可能是一个问题。 30亿字目标的指标需要持有30亿个指针和30亿个长的字。 这似乎很难适应这less于几十千兆字节的RAM。 但令人惊讶的是，我们可以使用Burrows-Wheeler变换大大压缩索引，并且仍然可以高效查询。 人类基因组的索引可以适合于小于4GB的RAM。 这个想法是Bowtie和BWA等常用序列alignment的基础。
或者，我们可以使用一个只存储指针的后缀数组 ，但是它代表了目标string中所有后缀的同时索引（实质上是k的所有可能值的同时索引; Burrows-Wheeler变换也是如此）。 如果我们使用32位指针，人类基因组的后缀数组索引将需要12 GB的RAM。
上面的链接包含大量的信息和主要研究论文的链接。 ELAND链接转到一个PDF，其中有用的数字说明涉及的概念，并演示如何处理插入和删除操作。
最后，虽然这些algorithm已经基本解决了对单个人类基因组（十亿个短的string）进行（重新）测序的问题，但DNA测序技术的进步速度比摩尔定律更快，而且我们正在接近万亿字节的数据集。 例如，目前有一些项目正在进行10万个字母左右的脊椎动物的基因组测序。 当然，我们会想在数据上做成对的不精确string匹配…
我认为selectB更接近testingstring，因为它只有4个字符（和2个删除）不是原始string。 而你看到C更接近，因为它包括棕色和红色。 但是，它会有更大的编辑距离。
有一种称为Levenshtein距离的algorithm来测量两个input之间的编辑距离。
这是一个algorithm的工具。
- selectA的距离为15。
- 率selectB作为距离6。
- 率selectC作为距离9。
编辑：对不起，我不断在levenshtein工具中混合string。 更新为正确的答案。
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库，提供简单的距离度量，例如用于string匹配的Levenshtein距离。 它build立在标准库中的difflib之上，如果可用，将使用C实现Python-levenshtein。
你可能会觉得这个库很有用！ http://code.google.com/p/google-diff-match-patch/
它目前可用于Java，JavaScript，Dart，C ++，C＃，Objective C，Lua和Python
它工作得很好。 我在几个我的Lua项目中使用它。
而且我不认为把它移植到其他语言也不是太难。
如果您是在search引擎或前端对数据库的上下文中执行此操作，则可以考虑使用类似Apache Solr的工具和ComplexPhraseQueryParser插件。 这种组合使您能够根据Levenshtein距离所确定的结果按照相关性进行search。
当传入的查询可能有一个或多个拼写错误时，我们一直在使用它来对付大量的艺术家和歌曲标题，而且它工作得非常好（并且考虑到数百万string的集合，速度非常快）。
另外，通过使用Solr，您可以通过JSON按照索引进行search，因此您不必在所查看的不同语言之间重新创build解决scheme。
Simmetrics是这类algorithm的一个非常好的资源： http : //sourceforge.net/projects/simmetrics/
不幸的是，包含大量文档的真棒网站已经不存在了（如果它再次出现，它以前的地址是这样的： http : //www.dcs.shef.ac.uk/~sam/simmetrics.html
Voila（礼貌“Wayback机器”）： http ://web.archive.org/web/20081230184321/http: //www.dcs.shef.ac.uk/~sam/simmetrics.html
你可以研究代码的来源，有几十种这样的比较algorithm，每种都有不同的权衡。 这些实现在Java中。
要以高效的方式查询大量文本，您可以使用编辑距离/前缀编辑距离的概念。
编辑距离ED（x，y）：从术语x到术语y的最小转换次数
但是，计算每个术语与查询文本之间的ED是资源和时间密集型的。 因此，不是首先为每个术语计算ED，我们可以使用称为Qgram索引的技术来提取可能的匹配术语。 然后对这些选定的术语应用ED计算。
Qgram索引技术的一个优点是它支持模糊search。
适应QGram索引的一个可能的方法是使用Qgrams构build倒置索引。 在那里，我们存储所有与特定的Qgram组成的字，在这个Qgram下（而不是存储完整的string，你可以为每个string使用唯一的ID）。 你可以在Java中使用Tree Map的数据结构。 以下是存储术语的一个小例子
col： col mbia， col ombo，gan col a，ta col 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。
对于具有大量常见Qgram的术语，我们根据查询词计算ED / PED，然后向最终用户build议术语。
你可以在下面的项目中find这个理论的实现（参见“QGramIndex.java”）。 随意问任何问题。 https://github.com/Bhashitha-Gamage/City_Search
要了解更多关于编辑距离，前缀编辑距离Qgram指数，请观看以下教授汉娜巴斯特博士https://www.youtube.com/embed/6pUg2wmGJRo （课程从20:06开始）
如果input数据太大（比如数百万string），问题很难实现。 我用弹性search来解决这个问题。 只需将所有input数据插入到数据库中，您就可以快速search任何基于任何编辑距离的string。 这是一个C＃代码片段，它会给你一个按编辑距离sorting的结果列表（从小到大）
var res = client.Search<ClassName>(s => s .Query(q => q .Match(m => m .Field(f => f.VariableName) .Query("SAMPLE QUERY") .Fuzziness(Fuzziness.EditDistance(5)) ) ));
