如何计算给定2个字符串的距离相似度？

你正在寻找的是所谓的 编辑距离或 莱文斯坦距离。Wikipedia 文章解释了它是如何计算的，并在底部提供了一段很好的伪代码来帮助您轻松地在 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];
}

有大量的字符串相似距离算法可以使用。这里列出了一些(但不是详尽列出的) :

• Levenstein
• 裁缝 Wunch
• 史密斯 · 沃特曼
• 史密斯 · 沃特曼 · 哥特
• Jaro Jaro Winkler
• Jaccard 相似度
• 欧几里得度量
• 骰子相似度
• 余弦距离
• 蒙哥 · 埃尔坎

包含所有这些内容的实现的库称为 < a href = “ http://sourceforge.net/Projects/SimMetrics/files/”rel = “ noReferrer”> SimMetrics 它同时具有 java 和 c # 实现。

几个星期前，我刚刚解决了同样的问题。既然有人问起，我就把密码告诉他们。在我的详尽测试中，即使没有提供最大距离，我的代码也比 Wikipedia 上的 C # 示例快10倍左右。当提供最大距离时，此性能增益增加到30x-100x + 。请注意性能方面的几个关键点:

• 如果您需要一遍又一遍地比较相同的单词，首先将单词转换为整数数组。Damerau-Levenshtein 算法包括许多 > 、 < 、 = = 比较，而且 ints比 chars快得多。
• 它包括一个短路机制退出，如果距离超过提供的最大值
• 使用一个由三个数组组成的旋转集合，而不是像我在其他地方看到的所有实现那样使用一个巨大的矩阵
• 确保您的数组横切较短的单词宽度。

代码(如果在参数声明中用 String替换 int[]，其工作原理完全相同:

/// <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;
}

这里有一个替代方法:

一个典型的寻找相似性的方法是莱文斯坦距离的，毫无疑问有一个带有可用代码的库。

不幸的是，这需要与每个字符串进行比较。如果距离大于某个阈值，您可以编写一个专门的代码版本来缩短计算，但是仍然需要进行所有的比较。

另一个想法是使用一些三角形或 n-gram 的变体。这些是 n 个字符的序列(或者 n 个单词或者 n 个基因组序列或者任何东西)。保持三角形到字符串的映射，并选择重叠最大的那些。N 的典型选择是“3”，因此得名。

例如，英语中有这样的三角形:

• 英格
• Ngl
• Gli
• Lis
• 差不多吧

而英格兰会:

• 英格
• Ngl
• Gla
• 伊恩
• 还有

嗯，七局两胜(或者十局四胜)。如果这对您有用，您可以索引三元/字符串表并获得更快的搜索。

您还可以将它与 Levenshtein 结合起来，以减少与那些具有一些共同的最小 n 克数的比较集。

下面是我对 Damerau 莱文斯坦距离的实现，它不仅返回相似系数，还返回纠正后的单词中的错误位置(这个特性可以在文本编辑器中使用)。我的实现还支持不同的错误权重(替换、删除、插入、转换)。

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的一部分。

我写了一些 测试，在我看来，这种方法是有效的。

不过，我们欢迎各界人士提出意见和评论。

下面是 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

我发现 Levenshtein和 Jaro Winkler对于字符串之间的小差异非常有效，例如:

• 拼写错误; 或
• Ö 而不是人名中的 哦。

然而，当比较像文章标题这样的东西时，如果文章的重要部分是相同的，但是边缘有“噪音”，史密斯-沃特曼-哥特就非常棒了:

比较这两个标题(它们是相同的，但不同来源的措辞不同) :

来自大肠桿菌的内切核酸酶在紫外线照射的 DNA 中引入单核苷酸链断裂

内切酶 III: 在紫外线照射的 DNA 中引入单核苷酸链断裂的大肠桿菌内切酶

这个提供字符串算法比较 的站点显示:

• Levenshtein: 81
• 史密斯-沃特曼公司
• Jaro Winkler 78岁

Jaro Winkler 和 Levenshtein 没有 Smith Waterman Gotoh 那样有能力发现这种相似性。如果我们比较两篇不是同一篇文章的标题，但有一些匹配的文字:

高等植物脂肪代谢。酰基硫代酯酶在 酰基辅酶 A 和 酰基-酰基载体蛋白质代谢中的作用

高等植物的脂肪代谢。 复合脂质混合物中 酰基-酰基载体蛋白质和 酰基辅酶酰基辅酶 A 的测定