欢迎访问响应式个人博客!
男生版
女生版
初遇时,她的微笑,她往日的深情、承诺和傻劲,两个人共度的美丽时刻,一一印在回忆里,今天的感情已经比不上从前,但是我爱着恋着往日的她,舍不得离开!
排行
详情
您当前的位置>首页 > 正文
常见算法是js实现汇总
2017-10-24 14:42:03   来源:总结   评论:0 点击:

 for i from 0 to lenStr1
  d[i, 0] := i
 for j from 0 to lenStr2
  d[0, j] := j

 for i from 1 to lenStr1
  for j from 1 to lenStr2
   if str1[i] = str2[j] then cost := 0
         else cost := 1
   d[i, j] := minimum(
         d[i-1, j ] + 1,  // deletion
         d[i , j-1] + 1,  // insertion
         d[i-1, j-1] + cost // substitution
        )

 return d[lenStr1, lenStr2];
 这个算法其实就是一个矩阵的计算:
   k i t t e n
  0 1 2 3 4 5 6
 s 1 1 2 3 4 5 6
 i 2 2 1 2 3 4 5
 t 3 3 2 1 2 3 4
 t 4 4 3 2 1 2 3 
 i 5 5 4 3 2 2 3
 n 6 6 5 4 3 3 2
 g 7 7 6 5 4 4 3
 首先给定第一行和第一列,然后,每个值d[i,j]这样计算:d[i,j] = min(d[i-1,j]+ 1,d[i,j-1] +1,d[i-1,j-1]+(str1[i] == str2[j]?0:1));
 最后一行,最后一列的那个值就是LD的结果。
 LD(str1,str2) <= max(str1.len,str2.len);

  有人提出了Levenshtein automaton(Levenshtein自动机)来计算和某个字符串距离小于某个值的集合。这样能够加快近似字符串的计算过程。见文献:Klaus U. Schulz, Stoyan Mihov, Fast String Correction with Levenshtein-Automata. International Journal of Document Analysis and Recognition, 5(1):67--85, 2002.

A Guided Tour to Approximate String Matching GONZALO NAVARRO
 这篇文章里面对这个方面(字符串相似)进行了很多描述。其中,包含了动态规划法计算Edit distance的方法。

-------------------------------------------华丽丽的分割线-------------------------------------------------------------------------

js实现:

<script>

//求两个字符串的相似度,返回差别字符数,Levenshtein Distance算法实现

function Levenshtein_Distance(s,t){

 var n=s.length;// length of s

 var m=t.length;// length of t

 var d=[];// matrix

 var i;// iterates through s

 var j;// iterates through t

 var s_i;// ith character of s

 var t_j;// jth character of t

 var cost;// cost

 // Step 1

 if (n == 0) return m;

 if (m == 0) return n;

 // Step 2

 for (i = 0; i <= n; i++) {

  d[i]=[];

  d[i][0] = i;

 }

 for (j = 0; j <= m; j++) {

  d[0][j] = j;

 }

 // Step 3

 for (i = 1; i <= n; i++) {

  s_i = s.charAt (i - 1);

  // Step 4

  for (j = 1; j <= m; j++) {

   t_j = t.charAt (j - 1);

   // Step 5

   if (s_i == t_j) {

    cost = 0;

   }else{

    cost = 1;

   }

   // Step 6

   d[i][j] = Minimum (d[i-1][j]+1, d[i][j-1]+1, d[i-1][j-1] + cost);

  }

 }

 // Step 7

 return d[n][m];

}

//求两个字符串的相似度,返回相似度百分比

function Levenshtein_Distance_Percent(s,t){

 var l=s.length>t.length?s.length:t.length;

 var d=Levenshtein_Distance(s,t);

 return (1-d/l).toFixed(4);

}

//求三个数字中的最小值

function Minimum(a,b,c){

 return a

}

var str1="ddsddf",str2="xdsfsx";

alert(Levenshtein_Distance_Percent(str1,str2));

</script>

相关热词搜索:算法 常见

上一篇:JS地址栏动态传参查询的方法
下一篇:JavaScript里的循环方法

收藏