编辑距离LCS算法详解:Levenshtein Distance 算法计算两个字符串的相似度

时间:13-06-07 栏目:C#开发, SEO优化 作者:kyle 评论:1 点击: 9,644 次

最近算法研究比较多。看了LCS,不大明白它的具体实现。应用倒是比较简单,可以通过LCS得到2个字符串的相似度。下面载一个博客园朋友的贴子。

Levenshtein Distance,编辑距离算法,是指从字符串A变成字符串B,所需的最少编辑(增,删,插入)次数。应用也相当广泛,这里我们用来求解两个字符串的相似度。

算法原理我就不再说明(注,对于算法原理,请参照 http://en.wikipedia.org/wiki/Levenshtein_distance ),这里只图解实现的过程。

【例子】假设现在有源串“jary”与目标串“jerry”,求源串到目标串的编辑距离

图解过程如下:

step 1:初始化如下矩阵

step 2:从源串的第一个字符(“j”)开始,从上至下与目标串进行对比

如果两个字符相等,则在从此位置的左,上,左上三个位置中取出最小的值;若不等,则在从此位置的左,上,左上三个位置中取出最小的值再加上1;

第一次,源串第一个字符“j” 与目标串的“j”对比,左,上,左上三个位置中取出最小的值0,因为两字符相等,所以加上0;接着,依次对比“j”→“e”,“j”→“r”,“j”→“r”,,“j”→“y” 到扫描完目标串。

step 3:遍历整个源串与目标串对比:

step 4:扫描完最后一列,则最后一个为最短编辑距离

求出编辑距离,那么两个字符串的相似度 Similarity = (Max(x,y) - Levenshtein)/Max(x,y),其中 x,y 为源串和目标串的长度。

C#实现代码如下:

public static int LevenshteinDistance(string source, string target)
 {
     int cell = source.Length;
     int row = target.Length;
     if (cell == 0) {
         return row;
     }
     if (row == 0) {
         return cell;
     }
     int[, ] matrix = new int[row + 1, cell + 1];
     for (var i = 0; i <= cell; i++) {
         matrix[0, i] = i;
     }
     for (var j = 1; j <= row; j++) {
         matrix[j, 0] = j;
     }
     var tmp = 0;
     for (var k = 0; k < row; k++) {
         for (var l = 0; l < cell; l++) {
             if (source[l].Equals(target[k])) tmp = 0;
             else tmp = 1;
             matrix[k + 1, l + 1] = Math.Min(Math.Min(matrix[k, l] + tmp, matrix[k + 1, l]), matrix[k, l + 1] + 1);
         }
     }
     return matrix[row, cell];
 }

 

public static float StringSimilarity(string source, string target)
 {
     var ld = LevenshteinDistance(source, target);
     var maxLength = Math.Max(source.Length, target.Length);
     return (float)(maxLength - ld) / maxLength;
 }

希望对一些朋友有用。

使用的时候,可以自己测试一下

float result=StringSimilarity(我的电脑,你的电脑);

console.WriteLine("相似度为:"+result.ToString());

其实算法和结果知道了。我还是没搞明白为什么这样做可以计算得到相似度 。有更厉害的朋友欢迎指正。感谢博客园的兄弟。里面的大牛就是多,转自http://www.cnblogs.com/three-zone/archive/2013/06/06/LevenshteinDistance.html

成都SEO小五嚎2句: 本文是(成都SEO小五)辛苦弄出来的,转载成都SEO小五原创的请保留链接: 编辑距离LCS算法详解:Levenshtein Distance 算法计算两个字符串的相似度,3Q

编辑距离LCS算法详解:Levenshtein Distance 算法计算两个字符串的相似度:目前有1 条留言,牛逼吧!

  1. 沙发
    lion:

    完全不知道在讲什么。。。 😮

    2013-06-10 12:17 pm [回复]

来给哥评论评论


------====== 小五公告 ======------
成都SEO小五,专注成都搜索引擎优化。
小五善长站内外优化,C#、PHP开发,中英文SEO,Google中英文和百度优化技术。欢迎群内交流。伸手党请绕路,求资源的请绕开,求问题解答的请进群内交流。开放了一个QQ交流群:160750032。加入验证时请标注任何SEO相交字眼。友情链接直接Q我,收录正常,内容大部份原创、SEO或者程序开发、网络营销、线上推广等相关行业即可。

常用工具

赞助广告

来看过哥的人