文档章节

Levenshtein Distance + LCS 算法计算两个字符串的相似度

深圳大道
 深圳大道
发布于 2016/12/29 15:39
字数 340
阅读 5
收藏 0
//LD最短编辑路径算法
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] + 1), matrix[k, l + 1] + 1);
        }
    }
    return matrix[row, cell];
}


//LCS最大公共序列算法
public static int LongestCommonSubsequence(string source, string target) 
{
    if (source.Length == 0 || target.Length == 0) 
        return 0;
    int len = Math.Max(target.Length, source.Length);
    int[, ] subsequence = new int[len + 1, len + 1];
    for (int i = 0; i < source.Length; i++) 
    {
        for (int j = 0; j < target.Length; j++) 
        {
            if (source[i].Equals(target[j])) 
                subsequence[i + 1, j + 1] = subsequence[i, j] + 1;
            else 
                subsequence[i + 1, j + 1] = 0;
        }
    }
    int maxSubquenceLenght = (from sq in subsequence.Cast < int > () select sq).Max < int > ();
    return maxSubquenceLenght;
}

//计算两个字符串相似度 数值越大越相似
public static float StringSimilarity(string source, string target) 
{
    var ld = LevenshteinDistance(source, target);
    var lcs = LongestCommonSubsequence(source, target);
    return ((float)lcs)/(ld+lcs);;
}
/// <summary>
/// 获取两个字符串的相似度(适合中文)
/// </summary>
/// <param name=”sourceString”>第一个字符串</param>
/// <param name=”str”>第二个字符串</param>
/// <returns></returns>
public static double SimilarityWith(string sourceString, string str)
{
	char[] ss = sourceString.ToCharArray();
	char[] st = str.ToCharArray();
	int t = 0; //命中
	int k = 0; //非命中
	foreach (var item in st)
	{
		if (ss.Contains(item))
		{
			t++;
		}
		else
		{
			k++;
		}
	}
	return (double)t / ((double)k + (double)t);
}


本文转载自:http://blog.csdn.net/smartsmile2012/article/details/52587855

深圳大道
粉丝 3
博文 877
码字总数 0
作品 0
深圳
架构师
私信 提问
【Python】 字符串相似性度量,用difflib还是Levenshtein

【作者笔记】 difflib(Python自带):不一定为字符串,数组也可以匹配,但数组匹配时只有单个元素完全匹配才计入相似。 Levenshtein(第三方插件):需要输入为字符串,匹配时是整体匹配,数...

qcyfred
03/19
0
0
使用 Levenshtein 寻找彼此相似的字符串对

我们爬来了一些数据,接下来以豆瓣畅销书为例。 爬虫爬来的数据有 而我们系统中原有的数据有 做前端的同志可能一眼就看出来了,两个数组中有三个元素是因为全半角的缘故,是不能全词匹配的,...

xh4n3
2015/08/18
0
0
计算字符串相似度算法——Levenshtein

1.百度百科介绍: Levenshtein 距离,又称编辑距离,指的是两个字符串之间,由一个转换成另一个所需的最少编辑操作次数。 许可的编辑操作包括将一个字符替换成另一个字符,插入一个字符,删除...

SomaLihq
2018/06/27
0
0
编辑距离 (Levenshtein Distance算法)

很久没有写算法了, 个人算法中等, 不好不坏. 觉的学习算法的好处很多, 还可以保持大脑活跃度, 因此最近会写些算法的博客. 这篇文章的算法是工作中用到的. 一个成熟的动态规划算法.介绍给大家...

Anderson大码渣
03/03
0
0
python-Levenshtein几个计算字串相似度的函数解析

linux环境下,没有首先安装python_Levenshtein,用法如下: 重点介绍几个该包中的几个计算字串相似度的几个函数实现。 1. Levenshtein.hamming(str1, str2) 计算汉明距离。要求str1和str2必须...

技术mix呢
2017/11/08
0
0

没有更多内容

加载失败,请刷新页面

加载更多

《生活的难题》的读后感3600字范文

《生活的难题》的读后感3600字范文: 假如我们对丑的事物也能够像对待美的事物那般抱持一种开放、接纳的心态,拥有相同的感受力,那么我们便会发现它们都是充满意义的,而这种认识会使生活变...

原创小博客
14分钟前
1
0
Linux learn(四)

7. Linux磁盘与文件系统管理 文件系统通常会将数据放在不同的区块,权限与属性放置到inode中,至于实际数据则放到datab lock区块中,另外,还有一个超级区块(superblock)会记录整个文件系统...

lazy~
22分钟前
1
0
微信公众号开发(四)

微信公众号开发时常需要一个用户授权绑定的过程。关于微信公众号的用户绑定,一般有如下两种实现方式: (1)通过发送短信验证码的方式; (2)使用用户登录时,向后端传递openid的方式。 使...

织梦之魂
今天
3
0
设计模式-工厂模式

工厂模式 工厂模式(Factory Pattern)是 Java 中最常用的设计模式之一。这种类型的设计模式属于创建型模式,它提供了一种创建对象的最佳方式。 在工厂模式中,我们在创建对象时不会对客户端...

HOT_POT
今天
8
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部