比较两个字符串相似度 Levenshtein_Distance_Percent

比较两个字符串相似度 Levenshtein_Distance_Percent

1. //求两个字符串的相似度,返回差别字符数,Levenshtein Distance算法实现   
2. function Levenshtein_Distance(s,t){  
3.     var n=s.length;// length of s   
4.     var m=t.length;// length of t   
5.     var d=[];// matrix   
6.     var i;// iterates through s   
7.     var j;// iterates through t   
8.     var s_i;// ith character of s   
9.     var t_j;// jth character of t   
10.     var cost;// cost   
11.     // Step 1   
12.     if (n == 0) return m;  
13.     if (m == 0) return n;  
14.     // Step 2   
15.     for (i = 0; i <= n; i++) {  
16.         d[i]=[];  
17.         d[i][0] = i;  
18.     }  
19.     for (j = 0; j <= m; j++) {  
20.         d[0][j] = j;  
21.     }  
22.     // Step 3   
23.     for (i = 1; i <= n; i++) {  
24.         s_i = s.charAt (i - 1);       
25.         // Step 4          
26.         for (j = 1; j <= m; j++) {  
27.             t_j = t.charAt (j - 1);  
28.             // Step 5   
29.             if (s_i == t_j) {  
30.                 cost = 0;  
31.             }else{  
32.                 cost = 1;  
33.             }  
34.             // Step 6              
35.             d[i][j] = Minimum (d[i-1][j]+1, d[i][j-1]+1, d[i-1][j-1] + cost);  
36.         }  
37.     }  
38.     // Step 7   
39.     return d[n][m];  
40. }  
41.   
42. //求两个字符串的相似度,返回相似度百分比   
43. function Levenshtein_Distance_Percent(s,t){  
44.     var l=s.length>t.length?s.length:t.length;  
45.     var d=Levenshtein_Distance(s,t);  
46.     return (1-d/l).toFixed(4);  
47. }  
48.   
49. //求三个数字中的最小值   
50. function Minimum(a,b,c){  
51.     return a