LD 字符串比较算法

fengzl

浏览: 216313 次
性别:
来自: 宁波

最近访客更多访客>>

simon518

hongwen1993

tongfan

d8gmyself

博主相关

博客

微博

相册

留言

关于我

文章分类

社区版块

存档分类

算法 J#编程 C C++

编程算法
比较字符串（String）相似程度的算法。
LD(s1, s2)=把s1变成s2需要的{增加，删除，替换}操作之和。

汉字的特殊处理：http://www.cnitblog.com/ictfly/archive/2005/12/27/5828.aspx

<html>
<head>
<title>求两个字符串的相似度,Levenshtein Distance算法实现</title>
</head>
<body>
<h3>求两个字符串的相似度,Levenshtein Distance算法实现</h3>
字符串1:<input id="s" type="text" value="小谢天空"><br>
字符串2:<input id="t" type="text" value="小谢的天空"><br>
<input type="button" value="计算" onclick="test()"><br>
<div id="r"></div>
</body>
</html>
<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<b?(a<c?a:c):(b<c?b:c);
}

function test(){
var s=document.getElementById("s");
var t=document.getElementById("t");
var r=document.getElementById("r");
var l=Levenshtein_Distance_Percent(s.value,t.value);
r.innerHTML='字符串1:'+s.value+'<br>字符串2:'+t.value+'<br>'+'相似度:'+l+'<br>算法参考:<a href="http://www.merriampark.com/ld.htm" target="_blank">http://www.merriampark.com/ld.htm</a>';
}
</script>

分享到：