计算两个中文字符串相似度——编辑距离算法

淩亂°似流年 2022-08-10 04:49 277阅读 0赞

Levenshtein 距离，又称编辑距离，指的是两个字符串之间，由一个转换成另一个所需的最少编辑操作次数。

许可的编辑操作包括将一个字符替换成另一个字符，插入一个字符，删除一个字符。

编辑距离的算法是首先由俄国科学家Levenshtein提出的，故又叫Levenshtein Distance。

1、Java

**\[java\]** [view plain][] [copy][view plain] [![在CODE上查看代码片][CODE]][CODE_CODE] [![派生到我的代码片][ico_fork.svg]][ico_fork.svg 1]

1. **public****static****void** levenshtein(String str1, String str2) \{ 
2. // 计算两个字符串的长度。
3. **int** len1 = str1.length(); 
4. **int** len2 = str2.length(); 
5. // 建立上面说的数组，比字符长度大一个空间
6. **int**\[\]\[\] dif = **new****int**\[len1 + 1\]\[len2 + 1\]; 
7. // 赋初值，步骤B。
8. **for** (**int** a = 0; a <= len1; a++) \{ 
9. dif\[a\]\[0\] = a; 
10. \} 
11. **for** (**int** a = 0; a <= len2; a++) \{ 
12. dif\[0\]\[a\] = a; 
13. \} 
14. // 计算两个字符是否一样，计算左上的值
15. **int** temp; 
16. **for** (**int** i = 1; i <= len1; i++) \{ 
17. **for** (**int** j = 1; j <= len2; j++) \{ 
18. 
19. System.out.println("i = " \+ i + " j = " \+ j + " str1 = "
20. \+ str1.charAt(i - 1) + " str2 = " \+ str2.charAt(j - 1)); 
21. **if** (str1.charAt(i - 1) == str2.charAt(j - 1)) \{ 
22. temp = 0; 
23. \} **else** \{ 
24. temp = 1; 
25. \} 
26. // 取三个值中最小的
27. dif\[i\]\[j\] = min(dif\[i - 1\]\[j - 1\] + temp, dif\[i\]\[j - 1\] + 1, 
28. dif\[i - 1\]\[j\] + 1); 
29. 
30. System.out.println("i = " \+ i + ", j = " \+ j + ", dif\[i\]\[j\] = "
31. \+ dif\[i\]\[j\]); 
32. \} 
33. \} 
34. System.out.println("字符串\\"" \+ str1 + "\\"与\\"" \+ str2 + "\\"的比较"); 
35. // 取数组右下角的值，同样不同位置代表不同字符串的比较
36. System.out.println("差异步骤：" \+ dif\[len1\]\[len2\]); 
37. // 计算相似度
38. **float** similarity = 1 \- (**float**) dif\[len1\]\[len2\] 
39. / Math.max(str1.length(), str2.length()); 
40. System.out.println("相似度：" \+ similarity); 
41. \} 
42.

2、LotusScript

**\[plain\]** [view plain][] [copy][view plain] [![在CODE上查看代码片][CODE]][CODE_CODE] [![派生到我的代码片][ico_fork.svg]][ico_fork.svg 1]

1. Function toCompute(str1 As String ,str2 As String) As Double 
2. 
3. Dim len1 As Integer 
4. Dim len2 As Integer 
5. Dim maxlen As Integer 
6. Dim i As long 
7. Dim j As long 
8. Dim temp As long 
9. Dim similarity As Double 
10. 
11. 
12. If str1= "" Or str2 = "" Then 
13. 
14. toCompute = 0 
15. 
16. Else 
17. 
18. len1 = Len(str1) 
19. len2 = Len(str2) 
20. 
21. Dim dif(0 To 120, 0 To 120) As Integer 
22. 
23. If len1 > 120 Then 
24. len1 = 120 
25. End If 
26. 
27. If len2 > 120 Then 
28. len2 = 120 
29. End If 
30. 
31. If len1 > len2 Then 
32. maxlen = len1 
33. Else 
34. maxlen = len2 
35. End If 
36. 
37. For i = 0 To len1 Step 1 
38. dif(i,0) = i 
39. Next 
40. 
41. For i = 0 To len2 Step 1 
42. dif(0,i) = i 
43. Next 
44. 
45. For i = 1 To len1 Step 1 
46. 
47. For j = 1 To len2 Step 1 
48. 
49. 'Print "i = "& i & " j = " & j &" str1 = " & Right$(Left$(str1,i),1) &" str2 = " &Right$(Left$(str2,j),1) 
50. 
51. If Right$(Left$(str1,i),1) = Right$(Left$(str2,j),1) Then 
52. temp = 0 
53. Else 
54. temp = 1 
55. End If 
56. 
57. dif(i,j) = min(dif(i-1,j-1)+ temp ,dif(i,j-1)+1,dif(i-1,j)+1) 
58. 
59. Next 
60. Next 
61. 
62. 'Print "差异步骤： " & dif(len1 ,len2) 
63. similarity = 1 - dif(len1 ,len2 )/maxlen 
64. 'Print "差异度：" & similarity 
65. toCompute = similarity 
66. 
67. 
68. 'Call toLogFile("str1 = " & str1 &" str2 = " &str2 & " 相似度： " & similarity) 
69. End If 
70. End Function 
71.

优化

1、Visual Basic

**\[vb\]** [view plain][] [copy][view plain] [![在CODE上查看代码片][CODE]][CODE_CODE] [![派生到我的代码片][ico_fork.svg]][ico_fork.svg 1]

1. **Module** Module1 
2. 
3. **Sub** Main() 
4. **Dim** str1 **As****String**
5. 
6. **Dim** str2 **As****String**
7. 
8. str1 = "今天是星期五"
9. str2 = "明天星期四"
10. 
11. **Dim** dis **As****New** clsDistance(str1, str2) 
12. **Dim** result **As****Integer**
13. 
14. result = dis.CacuDistance() 
15. 
16. Console.WriteLine(result) 
17. 
18. 
19. 
20. **End****Sub**
21. 
22. 
23. **Public****Class** clsDistance 
24. **Private** mCharA() **As****Char**
25. **Private** mCharB() **As****Char**
26. **Private** mCharALen **As****Integer**
27. **Private** mCharBLen **As****Integer**
28. 
29. 
30. **Public****Sub****New**(**ByVal** StrA **As****String**, **ByVal** StrB **As****String**) 
31. 
32. 
33. mCharA = StrA.ToCharArray 
34. mCharB = StrB.ToCharArray 
35. mCharALen = mCharA.Length 
36. mCharBLen = mCharB.Length 
37. 
38. 
39. **End****Sub**
40. 
41. 
42. **Public****Function** CacuDistance() **As****Integer**
43. **Dim** i **As****Integer**
44. 
45. 
46. **If** mCharALen = 0 **Then****Return** mCharBLen 
47. **If** mCharBLen = 0 **Then****Return** mCharALen 
48. 
49. Console.WriteLine(mCharALen) 
50. Console.WriteLine(mCharBLen) 
51. 
52. **Dim** j **As****Integer** = Min(mCharALen, mCharBLen) - 1 
53. **Dim** tP1 **As****Integer**, tP2 **As****Integer**
54. 
55. 
56. tP1 = -1 
57. tP2 = -1 
58. 
59. 
60. **For** i = 0 **To** j 
61. **If** mCharA(i) <> mCharB(i) **Then**
62. tP1 = i 
63. **Exit****For**
64. **End****If**
65. **Next**
66. 
67. 
68. **If** tP1 = -1 **Then****Return** Math.Abs(mCharALen - mCharBLen) 
69. 
70. 
71. **For** i = 0 **To** j - tP1 
72. **If** mCharA(mCharALen - i - 1) <> mCharB(mCharBLen - i - 1) **Then**
73. tP2 = i 
74. **Exit****For**
75. **End****If**
76. **Next**
77. 
78. 
79. **If** tP2 = -1 **Then****Return** Math.Abs(mCharALen - mCharBLen) 
80. Console.WriteLine("tp1: = " & tP1) 
81. Console.WriteLine("tp2 : = " & tP2) 
82. 
83. 
84. 
85. **Dim** tA(mCharALen - tP1 - tP2) **As****Integer**
86. 
87. 
88. **For** i = 0 **To** tA.GetUpperBound(0) 
89. tA(i) = i 
90. **Next**
91. **For** i = 0 **To** tA.GetUpperBound(0) **Step** 1 
92. Console.WriteLine(" i = " \+ **CStr**(i) + " " & tA(i)) 
93. **Next**
94. 
95. Console.WriteLine("Bound: = " & tA.GetUpperBound(0)) 
96. 
97. **Dim** tN1 **As****Integer**, tN2 **As****Integer**, tN3 **As****Integer**
98. 
99. 
100. **For** i = 0 **To** mCharBLen - tP1 - tP2 - 1 
101. tN1 = tA(0) 
102. tN2 = tN1 + 1 
103. Console.WriteLine("i = " & i & " " & mCharB(mCharBLen - tP2 - i - 1)) 
104. 
105. **For** j = 1 **To** tA.GetUpperBound(0) 
106. 
107. Console.WriteLine("j = " & j & " " & mCharA(mCharALen - tP2 - j)) 
108. 
109. **If** mCharA(mCharALen - tP2 - j) = mCharB(mCharBLen - tP2 - i - 1) **Then**
110. tN3 = tN1 
111. **Else**
112. tN3 = Min(tA(j), tN1, tN2) + 1 
113. **End****If**
114. tA(j - 1) = tN2 
115. tN2 = tN3 
116. tN1 = tA(j) 
117. 
118. Console.WriteLine("tn1 = " & tN1) 
119. Console.WriteLine("tn2 = " & tN2) 
120. Console.WriteLine("tn3 = " & tN3) 
121. **Next**
122. tA(tA.GetUpperBound(0)) = tN2 
123. 
124. Console.WriteLine(tA.GetUpperBound(0) & " " & tA(tA.GetUpperBound(0))) 
125. **Next**
126. 
127. **For** i = 0 **To** tA.GetUpperBound(0) **Step** 1 
128. Console.WriteLine(" i = " \+ **CStr**(i) + " " & tA(i)) 
129. **Next**
130. **Return** tA(tA.GetUpperBound(0)) 
131. 
132. 
133. **End****Function**
134. 
135. 
136. **Public****Function** Min(**ByVal****ParamArray** Num() **As****Integer**) **As****Integer**
137. **Dim** tN **As****Integer**, i **As****Integer**
138. **If** Num.Length = 0 **Then****Return****Nothing**
139. tN = Num(0) 
140. 
141. 
142. **For** i = 1 **To** Num.GetUpperBound(0) 
143. **If** Num(i) < tN **Then** tN = Num(i) 
144. **Next**
145. 
146. 
147. **Return** tN 
148. **End****Function**
149. 
150. 
151. **End****Class**
152. 
153. **End****Module**
154.

2、Java

**\[java\]** [view plain][] [copy][view plain] [![在CODE上查看代码片][CODE]][CODE_CODE] [![派生到我的代码片][ico_fork.svg]][ico_fork.svg 1]

1. **public****static****int** clsDistance(String str1, String str2) \{ 
2. 
3. **int** j; 
4. **int** i; 
5. 
6. **int** mCharALen, mCharBLen; 
7. 
8. mCharALen = str1.length(); 
9. mCharBLen = str2.length(); 
10. 
11. **int** tp1 = -1; 
12. **int** tp2 = -1; 
13. 
14. j = Math.min(mCharALen , mCharBLen) - 1; 
15. 
16. **for** (i = 0; i <= j; i++) \{ 
17. **if** (str1.charAt(i) != str2.charAt(i)) \{ 
18. tp1 = i; 
19. **break**; 
20. \} 
21. 
22. \} 
23. 
24. **if** (tp1 == -1) \{ 
25. **return** Math.abs(mCharBLen - mCharALen); 
26. \} 
27. 
28. **for** (i = 0; i <= j - tp1; i++) \{ 
29. 
30. **if** (str1.charAt(mCharALen - i - 1) != str2.charAt(mCharBLen - i 
31. \- 1)) \{ 
32. tp2 = i; 
33. **break**; 
34. \} 
35. \} 
36. 
37. **if** (tp2 == -1) \{ 
38. **return** Math.abs(mCharALen - mCharBLen); 
39. \} 
40. **int** taBound = mCharALen - tp1 - tp2; 
41. 
42. **int** tA\[\] = **new****int**\[taBound + 1\]; 
43. 
44. **for** (i = 0; i < tA.length; i++) \{ 
45. tA\[i\] = i ; 
46. 
47. \} 
48. System.out.println(Arrays.toString(tA)); 
49. **int** tN1, tN2, tN3; 
50. 
51. **for** (i = 0; i < mCharBLen - tp1 - tp2 ; i++) \{ 
52. tN1 = tA\[0\]; 
53. tN2 = tN1 + 1; 
54. 
55. System.out.println("\\n" \+ i + " " \+ str2.charAt(mCharBLen 
56. \- tp2 - i - 1)); 
57. 
58. **for** (j = 1; j < tA.length ; j++) \{ 
59. 
60. System.out.print(str1.charAt(mCharALen - tp2 - j ) +" "); 
61. 
62. **if** (str1.charAt(mCharALen - tp2 - j ) == str2.charAt(mCharBLen 
63. \- tp2 - i - 1)) \{ 
64. 
65. tN3 = tN1; 
66. \} **else** \{ 
67. tN3 = Math.min(tA\[j\], Math.min(tN1, tN2)) + 1; 
68. 
69. \} 
70. 
71. tA\[j - 1\] = tN2; 
72. tN2 = tN3; 
73. tN1 = tA\[j\]; 
74. 
75. System.out.println("\\ntN1 = " \+ tN1); 
76. System.out.println("tN2 = " \+ tN2); 
77. System.out.println("tN3 = " \+ tN3); 
78. \} 
79. 
80. tA\[tA.length - 1\] = tN2; 
81. System.out.println("\\n"\+tA\[tA.length - 1\] ); 
82. \} 
83. 
84. System.out.println("\\n" \+Arrays.toString(tA)); 
85. **return** tA\[tA.length - 1\]; 
86. 
87. \}

3、Lotus Script

**\[plain\]** [view plain][] [copy][view plain] [![在CODE上查看代码片][CODE]][CODE_CODE] [![派生到我的代码片][ico_fork.svg]][ico_fork.svg 1]

1. %REM 
2. Function clsDistance 
3. Description: Comments for Function 
4. %END REM 
5. Function clsDistance(str1 As String ,str2 As String) As Double 
6. Dim mCharALen As Integer 
7. Dim mCharBLen As Integer 
8. Dim i As Integer 
9. Dim simularity As Double 
10. Dim maxlen As Integer 
11. 
12. mCharALen = Len(str1) 
13. mCharBLen = Len(str2) 
14. 
15. If mCharALen > mCharBLen Then 
16. maxlen = mCharALen 
17. Else 
18. maxlen = mCharBLen 
19. End If 
20. 
21. If str1= "" Or str2 = "" Then 
22. clsDistance = 0 
23. Exit function 
24. End If 
25. 
26. Dim j As Integer 
27. 
28. If mCharALen > mCharBLen Then 
29. j = mCharBLen - 1 
30. Else 
31. j = mCharALen - 1 
32. End If 
33. 
34. Dim tP1 , tP2 As Integer 
35. tP1 = -1 
36. tP2 = -1 
37. 
38. For i = 0 To j Step 1 
39. 
40. If Right$(Left$(str1,i+1),1) <> Right$(Left$(str2,i+1),1) Then 
41. tP1 = i 
42. Exit For 
43. End If 
44. 
45. Next 
46. 
47. 
48. If tP1 = -1 Then 
49. clsDistance = 1 - Abs(mCharALen - mCharBLen) / maxlen 
50. Exit Function 
51. End If 
52. 
53. 
54. For i = 0 To j - tP1 
55. If Right$(Left$(str1,mCharALen - i),1) <> Right$(Left$(str2,mCharBLen - i),1) Then 
56. tP2 = i 
57. Exit For 
58. End If 
59. Next 
60. 
61. 
62. If tP2 = -1 Then 
63. clsDistance = 1 - Abs(mCharALen - mCharBLen) / maxlen 
64. Exit Function 
65. End If 
66. 
67. Dim tA(15000) As Integer 
68. Dim tABound As Integer 
69. tABound = mCharALen - tP1 - tP2 + 1 
70. 
71. For i = 0 To tABound Step 1 
72. tA(i) = i 
73. Next 
74. 
75. Dim tN1 As Integer, tN2 As Integer, tN3 As Integer 
76. 
77. 
78. For i = 0 To mCharBLen - tP1 - tP2 
79. tN1 = tA(0) 
80. tN2 = tN1 + 1 
81. 
82. For j = 1 To tABound 
83. 
84. If Right$(Left$(str1,mCharALen - tP2 - j + 1),1) = Right$(Left$(str2,mCharBLen - tP2 - i),1) Then 
85. tN3 = tN1 
86. Else 
87. tN3 = Min(tA(j), tN1, tN2) + 1 
88. End If 
89. 
90. tA(j - 1) = tN2 
91. tN2 = tN3 
92. tN1 = tA(j) 
93. Next 
94. 
95. 
96. tA(tABound) = tN2 
97. Next 
98. 
99. simularity = 1 - tA(tABound) / maxlen 
100. 
101. clsDistance = simularity 
102. End Function

[view plain]: http://blog.csdn.net/kangkanglou/article/details/39234907#
[CODE]: https://code.csdn.net/assets/CODE_ico.png
[CODE_CODE]: https://code.csdn.net/snippets/467980
[ico_fork.svg]: https://code.csdn.net/assets/ico_fork.svg
[ico_fork.svg 1]: https://code.csdn.net/snippets/467980/fork