字符串相似度算法（編輯距離算法 Levenshtein Distance）原理及C#代碼實(shí)現(xiàn)
發(fā)表于109 天前 ?
IT技術(shù) ?
暫無評(píng)論本文參考：
字符串相似度算法（編輯距離算法 Levenshtein Distance）編輯距離，又稱Levenshtein距離（也叫做Edit Distance），是指兩個(gè)字串之間，由一個(gè)轉(zhuǎn)成另一個(gè)所需的最少編輯操作次數(shù)，如果它們的距離越大，說明它們?cè)绞遣煌?。許可的編輯操作包括將一個(gè)字符替換成另一個(gè)字符，插入一個(gè)字符，刪除一個(gè)字符。
例如將kitten一字轉(zhuǎn)成sitting：
sitten （k→s）
sittin （e→i）
sitting （→g）
俄羅斯科學(xué)家Vladimir Levenshtein在1965年提出這個(gè)概念。因此也叫Levenshtein Distance。
例如
如果str1="ivan"，str2="ivan"，那么經(jīng)過計(jì)算后等于 0。沒有經(jīng)過轉(zhuǎn)換。相似度=1-0/Math.Max(str1.length,str2.length)
如果str1="ivan1"，str2="ivan2"，那么經(jīng)過計(jì)算后等于1。str1的"1"轉(zhuǎn)換"2"，轉(zhuǎn)換了一個(gè)字符，所以距離是1，相似度=1-1/Math.Max(str1.length,str2.length)
應(yīng)用
DNA分析
拼字檢查
語音辨識(shí)
抄襲偵測(cè)
算法過程
str1或str2的長(zhǎng)度為0返回另一個(gè)字符串的長(zhǎng)度。 if(str1.length==0) return str2.length; if(str2.length==0) return str1.length;
初始化(n+1)*(m+1)的矩陣d，并讓第一行和列的值從0開始增長(zhǎng)。
掃描兩字符串（n*m級(jí)的），如果：str1[i] == str2[j]，用temp記錄它，為0。否則temp記為1。然后在矩陣d[i,j]賦于d[i-1,j]+1 、d[i,j-1]+1、d[i-1,j-1]+temp三者的最小值。
掃描完后，返回矩陣的最后一個(gè)值d[n][m]即是它們的距離。
計(jì)算相似度公式：1-它們的距離/兩個(gè)字符串長(zhǎng)度的最大值。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
namespace DeepLeo.Library.String
{
public class LevenshteinSimilarity
{
public class LevenshteinDistance
{
/// <summary>
/// 取最小的一位數(shù)
/// </summary>
/// <param name="first"></param>
/// <param name="second"></param>
/// <param name="third"></param>
/// <returns></returns>
private int LowerOfThree(int first, int second, int third)
{
int min = Math.Min(first, second);
return Math.Min(min, third);
}
private int Levenshtein_Distance(string str1, string str2)
{
int[,] Matrix;
int n = str1.Length;
int m = str2.Length;
int temp = 0;
char ch1;
char ch2;
int i = 0;
int j = 0;
if (n == 0)
{
return m;
}
if (m == 0)
{
return n;
}
Matrix =
new int[n + 1, m + 1];
for (i = 0; i <= n; i++)
{
//初始化第一列
Matrix[i, 0] = i;
}
for (j = 0; j <= m; j++)
{
//初始化第一行
Matrix[0, j] = j;
}
for (i = 1; i <= n; i++)
{
ch1 = str1[i - 1];
for (j = 1; j <= m; j++)
{
ch2 = str2[j - 1];
if (ch1.Equals(ch2))
{
temp = 0;
}
else
{
temp = 1;
}
Matrix[i, j] = LowerOfThree(Matrix[i - 1, j] + 1, Matrix[i, j - 1] + 1, Matrix[i - 1, j - 1] + temp);
}
}
for (i = 0; i <= n; i++)
{
for (j = 0; j <= m; j++)
{
Console.Write(" {0} ", Matrix[i, j]);
}
Console.WriteLine("");
}
return Matrix[n, m];
}
/// <summary>
/// 計(jì)算字符串相似度
/// </summary>
/// <param name="str1"></param>
/// <param name="str2"></param>
/// <returns></returns>
public decimal LevenshteinDistancePercent(string str1, string str2)
{
//int maxLenth = str1.Length > str2.Length ? str1.Length : str2.Length;
int val = Levenshtein_Distance(str1, str2);return 1 - (decimal)val / Math.Max(str1.Length, str2.Length);
}
}
}
}
