我需要计算两个字符串之间的相似度。那我具体是什么意思呢？让我举个例子：
- 正确单词:
hospital - 错误单词:
haspita
现在我的目标是确定我需要修改多少个字符才能得到正确单词。在这个例子中，我需要修改2个字母。那么百分比是多少呢？我总是使用正确单词的长度作为分母。所以它变成了 2 / 8 = 25%，因此这两个给定的字符串 DSM 的相似度为 75%。
如何在性能成为关键考虑因素的情况下实现这一点呢？
如何计算给定两个字符串的距离相似度？
81
- Furkan Gözükara
4
循环遍历字符串中的字符并逐一检查它们，这已经是最快的方法了。由于每个字符至少需要在两个字符串中的较短者中被检查，因此没有真正的优化机会。 - Dervall
谢谢Dervall。这是程序员首先想到的，但我看到了许多优化的例子:D所以最好询问并确保专家的答案。 - Furkan Gözükara
1@Dervall 循环遍历字符如何足够？即使对于这个问题的O(n^2)算法也不是微不足道的。 - CodesInChaos
@Dervall 相对于什么来说，没有真正的优化机会？标准的字符串距离算法是O(n^2)。楼主试图用O(n)的算法来做得更好，但是它不起作用。例如，它会认为"ospital"是100%错误的。也许有可能比O(n^2)更好...证明它不是这样的。 - undefined
7个回答
85
我几周前刚解决了这个问题。既然有人现在正在问，我将分享代码。在我的详尽测试中，即使没有提供最大距离，我的代码也比维基百科上的C#示例快约10倍。当提供最大距离时，这种性能增益增加到30倍-100倍以上。请注意一些关键点以提高性能：
- 如果您需要反复比较相同的单词，请先将单词转换为整数数组。Damerau-Levenshtein算法包括许多 >，<，== 比较，而
ints比chars更快。 - 它包括一种短路机制，用于在距离超过提供的最大值时退出。
- 与其他所有实现中的大型矩阵不同，使用三个旋转数组集。
- 确保您的数组跨越较短的单词宽度。
代码（如果在参数声明中将int []替换为String，则代码完全相同）：
/// <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;
}
- Joshua Honig
5
2我比较了几种实现方式，你的似乎是表现最佳的，并且结果似乎很准确。非常感谢！ - AFract
我将它移植到了Java（这里：http://gist.github.com/cordje/bd13c781337d8ffc30bf），以便与各种现有的实现进行性能比较。这个实现比https://github.com/tdebatty/java-string-similarity/blob/master/src/main/java/info/debatty/java/stringsimilarity/Levenshtein.java中的实现慢了约40%。因此，我的选择是将初始阈值长度检查添加到该算法中。 - Richard EB
4你认为整数比字符比较快的原因是什么？它们基本上是相同的东西。
在计算算法速度时，你是否考虑了字符串-> int[] 的转换？对于Richard EB - 在Java中，许多内存分配和操作都不同，因此您无法进行此类比较。 - Bojidar Stanchev
可以确认。将字符串转换为
int[]是一场噩梦。http://i.imgur.com/mkW0aWw.png - hyankov59
你所需要的是称为编辑距离或Levenshtein距离的内容。维基百科文章解释了它的计算方式，并在底部提供了一段漂亮的伪代码，帮助你轻松地在C#中编写此算法的代码。
以下是来自下面第一个链接网站的实现：
以下是来自下面第一个链接网站的实现：
private static int CalcLevenshteinDistance(string a, string b)
{
if (String.IsNullOrEmpty(a) && String.IsNullOrEmpty(b)) {
return 0;
}
if (String.IsNullOrEmpty(a)) {
return b.Length;
}
if (String.IsNullOrEmpty(b)) {
return a.Length;
}
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];
}
- Sergey Kalinichenko
6
2@MonsterMMORPG 这里是一个相当简单的C#实现，可以在此链接（http://www.dotnetperls.com/levenshtein）中找到。它使用了`(M*N)`的空间，而更好的实现可以使用`2*MAX(M,N)`的空间。 - Sergey Kalinichenko
也许你可以适应 http://www.biorecipes.com/DynProgBasic/code.html 上的算法。 - Jeow Li Huan
@dasblinkenlight非常感谢您的回答。您是否想到了更好的解决方案？或者说，这不值得为了不重要的性能提升而麻烦吗？ - Furkan Gözükara
1@MonsterMMORPG 如果你的话很短（比如50个字符或更少），我就不会费心去理会。 - CodesInChaos
1@MonsterMMORPG 这里有一篇文章，使用了
[m+1][2] 数组。然而，它只在您的字符串变得相当长时才开始起作用，比如说一百个字符左右。 - Sergey Kalinichenko是的，它们少于25个字符。 - Furkan Gözükara
37
有许多可以使用的字符串相似度距离算法，以下列出了一些（但不是详尽列表）：
- Levenshtein（编辑距离）
- Needleman Wunch（尼德曼-温奇算法）
- Smith Waterman（史密斯-沃特曼算法）
- Smith Waterman Gotoh（史密斯-沃特曼-戈托算法）
- Jaro，Jaro Winkler（贾卡德，贾卡德-温克勒算法）
- Jaccard 相似度
- 欧几里得距离
- Dice 相似度
- 余弦相似度
- Monge Elkan
一个包含所有这些实现的库称为SimMetrics，它有 java 和 c# 实现。
- Anastasiosyal
2
谢谢，我将在那个文件中使用Levenstein类 :) - Furkan Gözükara
也可以尝试使用Jaro Winkler。我发现它能够产生很好的结果。 - Anastasiosyal
28
我发现Levenshtein和Jaro Winkler非常适合处理字符串之间的小差异，例如：
- 拼写错误；或者
- ö代替人名中的o。
然而，当比较文章标题时，文本的大部分内容相同，但是“噪声”在边缘上时，Smith-Waterman-Gotoh效果非常好：
比较这两个标题（它们来自不同来源，但是意思相同）：
一种来自大肠杆菌的内切酶，可在紫外线照射的DNA中引入单个多核苷酸链断裂
内切酶III：一种来自大肠杆菌的内切酶，可在紫外线照射的DNA中引入单个多核苷酸链断裂
此网站提供字符串算法比较结果如下：
- Levenshtein：81
- Smith-Waterman Gotoh：94
- Jaro Winkler：78
Jaro Winkler和Levenshtein在检测相似性方面不如Smith Waterman Gotoh。如果我们比较两个标题，它们不是同一篇文章，但有一些匹配的文本：
高等植物中的脂肪代谢。酰基辅酶A和酰基载体蛋白的代谢中酰基硫酯酶的功能。 高等植物中的脂肪代谢。在复杂的脂质混合物中确定酰基载体蛋白和酰基辅酶A。Jaro Winkler会给出错误的结果，但Smith Waterman Gotoh不会：
- Levenshtein：54 - Smith-Waterman Gotoh 49 - Jaro Winkler：89
正如Anastasiosyal所指出的那样，这些算法的Java代码可以在SimMetrics中找到。我成功地使用了SimMetrics中的SmithWatermanGotoh Java代码。
- joshweir
2
C#或VB.NET版本的Smith WaterMan源代码在哪里可以找到？ - Jamisco
2找到了，这里是C#的实现：http://jaligner.sourceforge.net/naligner/ - Jamisco
8
这是我的Damerau-Levenshtein距离实现，它不仅返回相似系数，还会返回已更正单词中的错误位置（这个特性可以在文本编辑器中使用）。此外，我的实现支持不同类型错误的权重（替换、删除、插入、转置）。
这段代码是我项目的一部分：Yandex-Linguistics.NET。
我写了一些测试用例，看起来这个方法是可行的。
但如果有评论和建议，欢迎分享。
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。
我写了一些测试用例，看起来这个方法是可行的。
但如果有评论和建议，欢迎分享。
- Ivan Kochurkin
4
以下是一种替代方法：
通常用于查找相似性的方法是Levenshtein距离，可以使用相应代码的库来实现。
不幸的是，这需要将每个字符串都进行比较。您可能能够编写一个特殊版本的代码，以便在距离大于某个阈值时终止计算，但仍需要进行所有比较。
另一个想法是使用一些变体的三元组或n-gram。这些是n个字符（或n个单词或n个基因组序列或n个其他内容）的序列。保留三元组到字符串的映射，并选择具有最大重叠的三元组。一个典型的n值的选择是“3”，因此得名。
例如，英文会有以下三元组：
Eng
ngl
gli lis
ish
而England则会有以下三元组：
Eng
ngl
gla lan
and
好的，2个匹配7个（或4个匹配10个）。如果对您有用，则可以将三元组/字符串表索引化并获得更快的搜索。
您还可以将其与Levenshtein结合使用，以减少那些具有一定数量共同n-gram的比较集合。
通常用于查找相似性的方法是Levenshtein距离，可以使用相应代码的库来实现。
不幸的是，这需要将每个字符串都进行比较。您可能能够编写一个特殊版本的代码，以便在距离大于某个阈值时终止计算，但仍需要进行所有比较。
另一个想法是使用一些变体的三元组或n-gram。这些是n个字符（或n个单词或n个基因组序列或n个其他内容）的序列。保留三元组到字符串的映射，并选择具有最大重叠的三元组。一个典型的n值的选择是“3”，因此得名。
例如，英文会有以下三元组：
Eng
ngl
gli lis
ish
而England则会有以下三元组：
Eng
ngl
gla lan
and
好的，2个匹配7个（或4个匹配10个）。如果对您有用，则可以将三元组/字符串表索引化并获得更快的搜索。
您还可以将其与Levenshtein结合使用，以减少那些具有一定数量共同n-gram的比较集合。
- Gordon Linoff
1
很遗憾，这需要与每个字符串进行比较。你可能是指每个子字符串，这是O(n×n×m)的复杂度，但这是错误的...例如，Levenshtein算法的复杂度是O(n×m)（请参考Sergey的回答，比你的回答早两年）。而你的三元组方法是无用的...就像原帖中试图通过比较两个字符串来实现O(n)一样，它会认为"ospital"与"hospital"完全不同。如果你不是指循环遍历字符串O(n)并比较三元组，那么你的意思就不太清楚了。Levenshtein算法才是正确的答案，这个回答应该被删除。 - undefined
0
这是一个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
- GHC
网页内容由stack overflow 提供, 点击上面的可以查看英文原文，
原文链接
原文链接