計算字符串相似度算法 - Levenshtein

jopen 14年前發布 | 2K 次閱讀 Jafka Dropbox 表達式

0.這個算法實現起來很簡單

1.百度百科介紹：

Levenshtein 距離，又稱編輯距離，指的是兩個字符串之間，由一個轉換成另一個所需的最少編輯操作次數。

許可的編輯操作包括將一個字符替換成另一個字符，插入一個字符，刪除一個字符。

編輯距離的算法是首先由俄國科學家Levenshtein提出的，故又叫Levenshtein Distance。

2.用途

模糊查詢

3.實現過程

a.首先是有兩個字符串,這里寫一個簡單的 abc和abe

b.將字符串想象成下面的結構。

A處是一個標記，為了方便講解，不是這個表的內容。

</tr>

</tr> </tbody> </table>

c.來計算A處出得值

它的值取決于：左邊的1、上邊的1、左上角的0.

按照Levenshtein distance的意思：

上面的值和左面的值都要求加1，這樣得到1+1=2。

A處由于是兩個a相同，左上角的值加0.這樣得到0+0=0。

這是后有三個值，左邊的計算后為2，上邊的計算后為2，左上角的計算為0，所以A處取他們里面最小的0.

d.于是表成為下面的樣子

	abc	a	b	c
abe	0	1	2	3
a	1	A處
b	2
e	3

</tr>

</tr> </tbody> </table>

在B處會同樣得到三個值，左邊計算后為3，上邊計算后為1，在B處由于對應的字符為a、b，不相等，所以左上角應該在當前值的基礎上加1，這樣得到1+1=2，在（3,1,2）中選出最小的為B處的值。

e.于是表就更新了

	abc	a	b	c
abe	0	1	2	3
a	1	0
b	2	B處
e	3

</tr>

</tr> </tbody> </table>

C處計算后：上面的值為2，左邊的值為4，左上角的：a和e不相同，所以加1，即2+1，左上角的為3。

在（2,4,3）中取最小的為C處的值。

f.于是依次推得到

	abc	a	b	c
abe	0	1	2	3
a	1	0
b	2	1
e	3	C處

</tr>

</tr> </tbody> </table>

I處: 表示abc 和abe 有1個需要編輯的操作。這個是需要計算出來的。

同時，也獲得一些額外的信息。

A處: 表示a 和a 需要有0個操作。字符串一樣

B處: 表示ab 和a 需要有1個操作。

C處: 表示abe 和a 需要有2個操作。

D處: 表示a 和ab 需要有1個操作。

E處: 表示ab 和ab 需要有0個操作。字符串一樣

F處: 表示abe 和ab 需要有1個操作。

G處: 表示a 和abc 需要有2個操作。

H處: 表示ab 和abc 需要有1個操作。

I處: 表示abe 和abc 需要有1個操作。

g.計算相似度

先取兩個字符串長度的最大值maxLen，用1-（需要操作數除maxLen），得到相似度。

例如abc 和abe 一個操作，長度為3，所以相似度為1-1/3=0.666。

4.代碼實現

直接能運行，復制過去就行。

package code;
/**

@className:MyLevenshtein.java
@classDescription:Levenshtein Distance 算法實現
可以使用的地方：DNA分析 　　拼字檢查 　　語音辨識 　　抄襲偵測
@author:donghai.wan
@createTime:2012-1-12
*/
public class MyLevenshtein {
public static void main(String[] args) {

 //要比較的兩個字符串
 String str1 = "今天星期四";
 String str2 = "今天是星期五";
 levenshtein(str1,str2);

}
/**

　　DNA分析 　　拼字檢查 　　語音辨識 　　抄襲偵測

@createTime 2012-1-12
*/
public static void levenshtein(String str1,String str2) {
 //計算兩個字符串的長度。
 int len1 = str1.length();
 int len2 = str2.length();
 //建立上面說的數組，比字符長度大一個空間
 int[][] dif = new int[len1 + 1][len2 + 1];
 //賦初值，步驟B。
 for (int a = 0; a <= len1; a++) {

 dif[a][0] = a;

}
 for (int a = 0; a <= len2; a++) {

 dif[0][a] = a;

}
 //計算兩個字符是否一樣，計算左上的值
 int temp;
 for (int i = 1; i <= len1; i++) {

 for (int j = 1; j <= len2; j++) {
     if (str1.charAt(i - 1) == str2.charAt(j - 1)) {
         temp = 0;
     } else {
         temp = 1;
     }
     //取三個值中最小的
     dif[i][j] = min(dif[i - 1][j - 1] + temp, dif[i][j - 1] + 1,
             dif[i - 1][j] + 1);
 }

}
 System.out.println("字符串\""+str1+"\"與\""+str2+"\"的比較");
 //取數組右下角的值，同樣不同位置代表不同字符串的比較
 System.out.println("差異步驟："+dif[len1][len2]);
 //計算相似度
 float similarity =1 - (float) dif[len1][len2] / Math.max(str1.length(), str2.length());
 System.out.println("相似度："+similarity);
}
//得到最小值
private static int min(int... is) {
 int min = Integer.MAX_VALUE;
 for (int i : is) {

 if (min > i) {
     min = i;
 }

}
 return min;
}




}</pre>
5.猜測原理 

為什么這樣就能算出相似度了？

首先在連續相等的字符就可以考慮到

紅色是取值的順序。

1.今天周一    天周一

		a	b	c
	0	1	2	3
a	1	A處 0	D處 1	G處 2
b	2	B處 1	E處 0	H處 1
e	3	C處 2	F處 1	I處 1

</tr>

</tr> </tbody> </table>

實現是去掉“今”，一步完成。

2.聽說馬上就要放假了你聽說要放假了

		天	周	一
	0	1	2	3
今	1	1	2	3
天	2	1	2	3
周	3	2	1	3
一	4	3	3	1

</tr>

</tr> </tbody> </table>

這兩個字符串是：

去掉“你”，加上“馬上就”，總共四步操作。

3.還是沒弄懂

6.結束

算法優化空間很大。

最后也沒弄懂為什么這樣算能算出相似度。

轉自：http://wdhdmx.iteye.com/blog/1343856

本文由用戶 jopen 自行上傳分享，僅供網友學習交流。所有權歸原作者，若您的權利被侵害，請聯系管理員。

轉載本站原創文章，請注明出處，并保留原始鏈接、圖片水印。

本站是一個以用戶分享為主的開源技術平臺，歡迎各類分享！

本文地址：http://www.baiduhome.net/blog/5035947118523382072.html

Jafka Dropbox 表達式

寫博客

計算字符串相似度算法 - Levenshtein

0.這個算法實現起來很簡單

1.百度百科介紹：

2.用途