文档章节

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

深圳大道
 深圳大道
发布于 2016/12/29 15:35
字数 340
阅读 6
收藏 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
深圳
架构师
私信 提问
使用 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
文本相似度十大方法简要说明

1、余弦相似性 余弦(余弦函数),三角函数的一种。在Rt△ABC(直角三角形)中,∠C=90°,角A的余弦是它的邻边比三角形的斜边,即cosA=b/c,也可写为cosA=AC/AB。余弦函数:f(x)=cosx(x...

u012654154
2017/04/21
0
0

没有更多内容

加载失败,请刷新页面

加载更多

【C++】智能指针简述(四):shared_ptr

  在开始本文内容之前,我们再来总结一下,前文内容:   1.智能指针采用RAII机制,在构造对象时进行资源的初始化,析构对象时进行资源的清理及汕尾.   2.auto_ptr防止拷贝后析构释放同一块内...

shzwork
24分钟前
1
0
作为Java程序员这些技术都不会,拿什么去涨薪跳槽?

引言 当下,正面临着近几年来的最严重的互联网寒冬,听得最多的一句话便是:相见于江湖~,缩减HC、裁员不绝于耳,大家都是人心惶惶,年前如此,年后想必肯定又是一场更为惨烈的江湖厮杀。但博...

别打我会飞
47分钟前
2
0
springboot开发之定时器quartz 定时任务调度(压缩版,抽取quartz的单个任务表实现)

前言 老了, 记不住了, 好记性不如烂笔头; 没想到曾经过目不忘的我, 也有这么一天, 岁月蹉跎,学习一天不如一天 难受 Quartz可以用来做什么? Quartz是一个任务调度框架。比如你遇到这样的问题...

尾生
52分钟前
11
0
技术经理平时都干啥?

「技术主管」是开发团队中的某位程序员需要对一起创建系统的整个开发团队负责时所承担的角色。通常他既要对最终交付的软件系统负责,另外也会像一个程序员一样去开发实现系统。 一个技术主管...

春哥大魔王的博客
今天
7
0
java工作流引擎Jflow流程事件和流程节点事件设置

流程实例的引入和设置 关键词: 开源工作流引擎 Java工作流开发 .net开源工作流引擎 流程事件 工作流节点事件 应用场景: 在一些复杂的业务逻辑流程中需要在某个节点或者是流程结束后做一些业...

ccflow周朋
今天
3
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部