国产一级a片免费看高清,亚洲熟女中文字幕在线视频,黄三级高清在线播放,免费黄色视频在线看

    兩字符串相似度計(jì)算方法有好多，現(xiàn)對(duì)基于編距的算法的相似度計(jì)算自己總結(jié)下。

    簡(jiǎn)單介紹下Levenshtein Distance(LD)：LD 可能衡量?jī)勺址南嗨菩?。它們的距離就是一個(gè)字符串轉(zhuǎn)換成那一個(gè)字符串過(guò)程中的添加、刪除、修改數(shù)值。

    舉例：

• 如果str1="test"，str2="test"，那么LD(str1,str2) = 0。沒(méi)有經(jīng)過(guò)轉(zhuǎn)換。
• 如果str1="test"，str2="tent"，那么LD(str1,str2) = 1。str1的"s"轉(zhuǎn)換"n"，轉(zhuǎn)換了一個(gè)字符，所以是1。

如果它們的距離越大，說(shuō)明它們?cè)绞遣煌?/p>

     Levenshtein distance最先是由俄國(guó)科學(xué)家Vladimir Levenshtein在1965年發(fā)明，用他的名字命名。不會(huì)拼讀，可以叫它edit distance（編輯距離）。

    Levenshtein distance可以用來(lái)：

• Spell checking(拼寫(xiě)檢查)
• Speech recognition(語(yǔ)句識(shí)別)
• DNA analysis(DNA分析)
• Plagiarism detection(抄襲檢測(cè))

LD用m*n的矩陣存儲(chǔ)距離值。算法大概過(guò)程：

1. str1或str2的長(zhǎng)度為0返回另一個(gè)字符串的長(zhǎng)度。
2. 初始化(n+1)*(m+1)的矩陣d，并讓第一行和列的值從0開(kāi)始增長(zhǎng)。
3. 掃描兩字符串（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三者的最小值。
4. 掃描完后，返回矩陣的最后一個(gè)值即d[n][m]

最后返回的是它們的距離。怎么根據(jù)這個(gè)距離求出相似度呢？因?yàn)樗鼈兊淖畲缶嚯x就是兩字符串長(zhǎng)度的最大值。對(duì)字符串不是很敏感。現(xiàn)我把相似度計(jì)算公式定為1-它們的距離/字符串長(zhǎng)度最大值。

    源碼：

Java代碼

1. package com.chenlb.algorithm;   
2.   
3. /**  
4.  * 編輯距離的兩字符串相似度  
5.  *   
6.  * @author chenlb 2008-6-24 下午06:41:55  
7.  */  
8. public class Similarity {   
9.   
10.     private int min(int one, int two, int three) {   
11.         int min = one;   
12.         if(two < min) {   
13.             min = two;   
14.         }   
15.         if(three < min) {   
16.             min = three;   
17.         }   
18.         return min;   
19.     }   
20.        
21.     public int ld(String str1, String str2) {   
22.         int d[][];  //矩陣   
23.         int n = str1.length();   
24.         int m = str2.length();   
25.         int i;  //遍歷str1的   
26.         int j;  //遍歷str2的   
27.         char ch1;   //str1的   
28.         char ch2;   //str2的   
29.         int temp;   //記錄相同字符,在某個(gè)矩陣位置值的增量,不是0就是1   
30.         if(n == 0) {   
31.             return m;   
32.         }   
33.         if(m == 0) {   
34.             return n;   
35.         }   
36.         d = new int[n+1][m+1];   
37.         for(i=0; i<=n; i++) {    //初始化第一列   
38.             d[i][0] = i;   
39.         }   
40.         for(j=0; j<=m; j++) {    //初始化第一行   
41.             d[0][j] = j;   
42.         }   
43.         for(i=1; i<=n; i++) {    //遍歷str1   
44.             ch1 = str1.charAt(i-1);   
45.             //去匹配str2   
46.             for(j=1; j<=m; j++) {   
47.                 ch2 = str2.charAt(j-1);   
48.                 if(ch1 == ch2) {   
49.                     temp = 0;   
50.                 } else {   
51.                     temp = 1;   
52.                 }   
53.                 //左邊+1,上邊+1, 左上角+temp取最小   
54.                 d[i][j] = min(d[i-1][j]+1, d[i][j-1]+1, d[i-1][j-1]+temp);   
55.             }   
56.         }   
57.         return d[n][m];   
58.     }   
59.        
60.     public double sim(String str1, String str2) {   
61.         int ld = ld(str1, str2);   
62.         return 1 - (double) ld / Math.max(str1.length(), str2.length());    
63.     }   
64.        
65.     public static void main(String[] args) {   
66.         Similarity s = new Similarity();   
67.         String str1 = "chenlb.blogjava.net";   
68.         String str2 = "chenlb.javaeye.com";   
69.         System.out.println("ld="+s.ld(str1, str2));   
70.         System.out.println("sim="+s.sim(str1, str2));   
71.     }   
72. }  

package com.chenlb.algorithm;/*** 編輯距離的兩字符串相似度** @author chenlb 2008-6-24 下午06:41:55*/public class Similarity {private int min(int one, int two, int three) {int min = one;if(two < min) {min = two;}if(three < min) {min = three;}return min;}public int ld(String str1, String str2) {int d[][];	//矩陣int n = str1.length();int m = str2.length();int i;	//遍歷str1的int j;	//遍歷str2的char ch1;	//str1的char ch2;	//str2的int temp;	//記錄相同字符,在某個(gè)矩陣位置值的增量,不是0就是1if(n == 0) {return m;}if(m == 0) {return n;}d = new int[n+1][m+1];for(i=0; i<=n; i++) {	//初始化第一列d[i][0] = i;}for(j=0; j<=m; j++) {	//初始化第一行d[0][j] = j;}for(i=1; i<=n; i++) {	//遍歷str1ch1 = str1.charAt(i-1);//去匹配str2for(j=1; j<=m; j++) {ch2 = str2.charAt(j-1);if(ch1 == ch2) {temp = 0;} else {temp = 1;}//左邊+1,上邊+1, 左上角+temp取最小d[i][j] = min(d[i-1][j]+1, d[i][j-1]+1, d[i-1][j-1]+temp);}}return d[n][m];}public double sim(String str1, String str2) {int ld = ld(str1, str2);return 1 - (double) ld / Math.max(str1.length(), str2.length());}public static void main(String[] args) {Similarity s = new Similarity();String str1 = "chenlb.blogjava.net";String str2 = "chenlb.javaeye.com";System.out.println("ld="+s.ld(str1, str2));System.out.println("sim="+s.sim(str1, str2));}}

不知sim方法中的公式是合理，個(gè)人認(rèn)為差強(qiáng)人意思，不知javaeyer們，有沒(méi)有高見(jiàn)，指點(diǎn)一二，^_^

參考: http://www.merriampark.com/ld.htm