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

深圳大道

``````//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);
}``````

### 深圳大道

xh4n3
2015/08/18
0
0

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

SomaLihq
2018/06/27
0
0

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

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

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

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

52分钟前
11
0

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

7
0
java工作流引擎Jflow流程事件和流程节点事件设置

ccflow周朋

3
0