如何计算给定2个string的距离相似度量？
我需要计算给定的2个string的距离相似性度量。 那我究竟是什么意思？ 让我用例子来解释
- 真正的字眼：
hospital - 错误的词：
haspita
现在我的目标是，我需要修改错误的单词来获得真实的单词。 在这个例子中，我需要修改2个字母。 那么百分比是多less？ 我总是把真实的词汇的长度。 所以它变成2/8 = 25％，所以这2个stringDSM是75％。
我如何才能做到这一点，性能是一个关键的考虑因素？
你正在寻找的是所谓的编辑距离或Levenshtein距离 。 维基百科的文章解释了它是如何计算的，并且在底部有一个很好的伪代码，可以帮助你很容易地用C＃编写这个algorithm。
下面是第一个链接如下的实现：
private static int CalcLevenshteinDistance(string a, string b) { if (String.IsNullOrEmpty(a) || String.IsNullOrEmpty(b)) return 0; int lengthA = a.Length; int lengthB = b.Length; var distances = new int[lengthA + 1, lengthB + 1]; for (int i = 0; i <= lengthA; distances[i, 0] = i++); for (int j = 0; j <= lengthB; distances[0, j] = j++); for (int i = 1; i <= lengthA; i++) for (int j = 1; j <= lengthB; j++) { int cost = b[j - 1] == a[i - 1] ? 0 : 1; distances[i, j] = Math.Min ( Math.Min(distances[i - 1, j] + 1, distances[i, j - 1] + 1), distances[i - 1, j - 1] + cost ); } return distances[lengthA, lengthB]; }
几个星期前我刚才讲到这个完全相同的问题。 由于有人现在要求，我将分享代码。 在我详尽的testing中，即使没有提供最大距离，我的代码也比维基百科上的C＃示例快了10倍。 当提供最大距离时，此性能增益将增加到30x – 100x +。 注意性能的几个关键点：
- 如果您需要反复比较相同的单词，请首先将单词转换为整数数组。 Damerau-Levenshteinalgorithm包含许多>，<，==比较，并且
ints比较比chars快得多。 - 如果距离超过规定的最大值，则包括一个短路机构
- 像我在其他地方看到的所有实现一样，使用三个数组的旋转集合，而不是一个巨大的matrix
- 确保你的数组在较短的字宽上切片。
代码（如果在参数声明中用Stringreplaceint[] ，则工作原理完全相同：
/// <summary> /// Computes the Damerau-Levenshtein Distance between two strings, represented as arrays of /// integers, where each integer represents the code point of a character in the source string. /// Includes an optional threshhold which can be used to indicate the maximum allowable distance. /// </summary> /// <param name="source">An array of the code points of the first string</param> /// <param name="target">An array of the code points of the second string</param> /// <param name="threshold">Maximum allowable distance</param> /// <returns>Int.MaxValue if threshhold exceeded; otherwise the Damerau-Leveshteim distance between the strings</returns> public static int DamerauLevenshteinDistance(int[] source, int[] target, int threshold) { int length1 = source.Length; int length2 = target.Length; // Return trivial case - difference in string lengths exceeds threshhold if (Math.Abs(length1 - length2) > threshold) { return int.MaxValue; } // Ensure arrays [i] / length1 use shorter length if (length1 > length2) { Swap(ref target, ref source); Swap(ref length1, ref length2); } int maxi = length1; int maxj = length2; int[] dCurrent = new int[maxi + 1]; int[] dMinus1 = new int[maxi + 1]; int[] dMinus2 = new int[maxi + 1]; int[] dSwap; for (int i = 0; i <= maxi; i++) { dCurrent[i] = i; } int jm1 = 0, im1 = 0, im2 = -1; for (int j = 1; j <= maxj; j++) { // Rotate dSwap = dMinus2; dMinus2 = dMinus1; dMinus1 = dCurrent; dCurrent = dSwap; // Initialize int minDistance = int.MaxValue; dCurrent[0] = j; im1 = 0; im2 = -1; for (int i = 1; i <= maxi; i++) { int cost = source[im1] == target[jm1] ? 0 : 1; int del = dCurrent[im1] + 1; int ins = dMinus1[i] + 1; int sub = dMinus1[im1] + cost; //Fastest execution for min value of 3 integers int min = (del > ins) ? (ins > sub ? sub : ins) : (del > sub ? sub : del); if (i > 1 && j > 1 && source[im2] == target[jm1] && source[im1] == target[j - 2]) min = Math.Min(min, dMinus2[im2] + cost); dCurrent[i] = min; if (min < minDistance) { minDistance = min; } im1++; im2++; } jm1++; if (minDistance > threshold) { return int.MaxValue; } } int result = dCurrent[maxi]; return (result > threshold) ? int.MaxValue : result; }
哪里Swap是：
static void Swap<T>(ref T arg1,ref T arg2) { T temp = arg1; arg1 = arg2; arg2 = temp; }
有很多可以使用的string相似距离algorithm。 这里列出的一些（但没有详尽列出）：
- 莱文施泰因
- Needleman Wunch
- 史密斯沃特曼
- 史密斯沃特曼后藤
- Jaro， Jaro Winkler
- Jaccard相似性
- 欧几里德距离
- 骰子相似性
- 余弦相似性
- Monge Elkan
一个包含所有这些实现的库称为SimMetrics ，它具有java和c＃实现。
我发现Levenshtein和Jaro Winkler对于string之间的细微差别很有帮助，例如：
- 拼写错误; 要么
- ö而不是以某人的名义。
然而，当比较文章标题的重要块将是相同的，但与周围的“噪音”的东西， 史密斯沃特曼后藤非常棒：
比较这两个标题（这是相同的，但不同的来源措辞）：
来自大肠杆菌的内切核酸酶，其在紫外线照射的DNA中引入单个多核苷酸链剪切
内切核酸酶III： 来自大肠杆菌的内切核酸酶，其在紫外线照射的DNA中引入单个多核苷酸链剪切
这个提供stringalgorithm比较的站点显示：
- Levenshtein：81
- 史密斯 – 沃特曼后藤94
- Jaro Winkler 78
Jaro Winkler和Levenshtein不如Smith Waterman Gotoh在检测相似性方面的能力。 如果我们比较两篇不是同一篇文章的标题，但是有一些匹配的文本：
高等植物的脂肪代谢。 酰基硫酯酶在酰基辅酶 A和酰基酰基载体蛋白代谢中的作用
高等植物的脂肪代谢。 酰基 – 酰基载体蛋白和酰基辅酶 A在复合脂质混合物中的测定
贾罗·温克勒（Jaro Winkler）给出了一个误报，但是史密斯沃特曼后藤（Gotoh）并没有：
- Levenshtein：54
- 史密斯 – 沃特曼后藤49
- Jaro Winkler 89
正如Anastasiosyal指出的， SimMetrics拥有这些algorithm的java代码。 我使用SimMetrics的SmithWatermanGotoh java代码成功了。
这是另一种方法：
这太长了评论。
find相似性的典型方法是Levenshtein距离，毫无疑问，可用的代码库是可用的。
不幸的是，这需要比较每一个string。 如果距离大于某个阈值，您可能可以编写一个特定版本的代码来短路计算，但您仍然需要进行所有比较。
另一个想法是使用trigrams或n-gram的一些变体。 这些是n个字符的序列（或n个字或n个基因组序列或n个）。 保持trigrams到string的映射，并select具有最大重叠的那些。 n的典型select是“3”，因此名称。
例如，英文有这样的三条：
- 工程
- NGL
- GLI
- LIS
- ISH
而英格兰将有：
- 工程
- NGL
- GLA
- 兰
- 和
那么7个中的2个（或10个中的4个）匹配。 如果这对你有效，你可以索引trigram / string表并获得更快的search。
你也可以把它与Levenshtein结合起来，把那些具有最小n-gram共同数的那些比较。
这里是我实现的Damerau Levenshtein距离，它不仅返回相似系数，还返回纠正字中的错误位置（此function可用于文本编辑器）。 另外我的实现支持不同权重的错误（replace，删除，插入，换位）。
public static List<Mistake> OptimalStringAlignmentDistance( string word, string correctedWord, bool transposition = true, int substitutionCost = 1, int insertionCost = 1, int deletionCost = 1, int transpositionCost = 1) { int w_length = word.Length; int cw_length = correctedWord.Length; var d = new KeyValuePair<int, CharMistakeType>[w_length + 1, cw_length + 1]; var result = new List<Mistake>(Math.Max(w_length, cw_length)); if (w_length == 0) { for (int i = 0; i < cw_length; i++) result.Add(new Mistake(i, CharMistakeType.Insertion)); return result; } for (int i = 0; i <= w_length; i++) d[i, 0] = new KeyValuePair<int, CharMistakeType>(i, CharMistakeType.None); for (int j = 0; j <= cw_length; j++) d[0, j] = new KeyValuePair<int, CharMistakeType>(j, CharMistakeType.None); for (int i = 1; i <= w_length; i++) { for (int j = 1; j <= cw_length; j++) { bool equal = correctedWord[j - 1] == word[i - 1]; int delCost = d[i - 1, j].Key + deletionCost; int insCost = d[i, j - 1].Key + insertionCost; int subCost = d[i - 1, j - 1].Key; if (!equal) subCost += substitutionCost; int transCost = int.MaxValue; if (transposition && i > 1 && j > 1 && word[i - 1] == correctedWord[j - 2] && word[i - 2] == correctedWord[j - 1]) { transCost = d[i - 2, j - 2].Key; if (!equal) transCost += transpositionCost; } int min = delCost; CharMistakeType mistakeType = CharMistakeType.Deletion; if (insCost < min) { min = insCost; mistakeType = CharMistakeType.Insertion; } if (subCost < min) { min = subCost; mistakeType = equal ? CharMistakeType.None : CharMistakeType.Substitution; } if (transCost < min) { min = transCost; mistakeType = CharMistakeType.Transposition; } d[i, j] = new KeyValuePair<int, CharMistakeType>(min, mistakeType); } } int w_ind = w_length; int cw_ind = cw_length; while (w_ind >= 0 && cw_ind >= 0) { switch (d[w_ind, cw_ind].Value) { case CharMistakeType.None: w_ind--; cw_ind--; break; case CharMistakeType.Substitution: result.Add(new Mistake(cw_ind - 1, CharMistakeType.Substitution)); w_ind--; cw_ind--; break; case CharMistakeType.Deletion: result.Add(new Mistake(cw_ind, CharMistakeType.Deletion)); w_ind--; break; case CharMistakeType.Insertion: result.Add(new Mistake(cw_ind - 1, CharMistakeType.Insertion)); cw_ind--; break; case CharMistakeType.Transposition: result.Add(new Mistake(cw_ind - 2, CharMistakeType.Transposition)); w_ind -= 2; cw_ind -= 2; break; } } if (d[w_length, cw_length].Key > result.Count) { int delMistakesCount = d[w_length, cw_length].Key - result.Count; for (int i = 0; i < delMistakesCount; i++) result.Add(new Mistake(0, CharMistakeType.Deletion)); } result.Reverse(); return result; } public struct Mistake { public int Position; public CharMistakeType Type; public Mistake(int position, CharMistakeType type) { Position = position; Type = type; } public override string ToString() { return Position + ", " + Type; } } public enum CharMistakeType { None, Substitution, Insertion, Deletion, Transposition }
这个代码是我的项目的一部分： Yandex-Linguistics.NET 。
我写了一些testing ，在我看来，这种方法正在工作。
但是欢迎评论和评论。
这是一个VB.net实现：
Public Shared Function LevenshteinDistance(ByVal v1 As String, ByVal v2 As String) As Integer Dim cost(v1.Length, v2.Length) As Integer If v1.Length = 0 Then Return v2.Length 'if string 1 is empty, the number of edits will be the insertion of all characters in string 2 ElseIf v2.Length = 0 Then Return v1.Length 'if string 2 is empty, the number of edits will be the insertion of all characters in string 1 Else 'setup the base costs for inserting the correct characters For v1Count As Integer = 0 To v1.Length cost(v1Count, 0) = v1Count Next v1Count For v2Count As Integer = 0 To v2.Length cost(0, v2Count) = v2Count Next v2Count 'now work out the cheapest route to having the correct characters For v1Count As Integer = 1 To v1.Length For v2Count As Integer = 1 To v2.Length 'the first min term is the cost of editing the character in place (which will be the cost-to-date or the cost-to-date + 1 (depending on whether a change is required) 'the second min term is the cost of inserting the correct character into string 1 (cost-to-date + 1), 'the third min term is the cost of inserting the correct character into string 2 (cost-to-date + 1) and cost(v1Count, v2Count) = Math.Min( cost(v1Count - 1, v2Count - 1) + If(v1.Chars(v1Count - 1) = v2.Chars(v2Count - 1), 0, 1), Math.Min( cost(v1Count - 1, v2Count) + 1, cost(v1Count, v2Count - 1) + 1 ) ) Next v2Count Next v1Count 'the final result is the cheapest cost to get the two strings to match, which is the bottom right cell in the matrix 'in the event of strings being equal, this will be the result of zipping diagonally down the matrix (which will be square as the strings are the same length) Return cost(v1.Length, v2.Length) End If End Function
