最大公共子串:
2009-11-27 10:421. Levenshtein Distance
该算法又称之为 "编辑距离",用于计算两个字符串的相似程度。原理很简单,就是返回将第一个字符串转换(删除、插入、替换)成第二个字符串的编辑次数。次数越少,意味着字符串相似度越高。
算法原理:Wikipedia - Levenshtein distance 本文摘自:http://www.rainsts.net/article.asp?id=767
Step1:
人 民 共 和 时 代
0, 0, 0, 0, 0, 0, 0
中 1, 0, 0, 0, 0, 0, 0
华 2, 0, 0, 0, 0, 0, 0
人 3, 0, 0, 0, 0, 0, 0
民 4, 0, 0, 0, 0, 0, 0
共 5, 0, 0, 0, 0, 0, 0
和 6, 0, 0, 0, 0, 0, 0
国 7, 0, 0, 0, 0, 0, 0
Step2:
人 民 共 和 时 代
0, 1, 2, 3, 4, 5, 6
中 1, 0, 0, 0, 0, 0, 0
华 2, 0, 0, 0, 0, 0, 0
人 3, 0, 0, 0, 0, 0, 0
民 4, 0, 0, 0, 0, 0, 0
共 5, 0, 0, 0, 0, 0, 0
和 6, 0, 0, 0, 0, 0, 0
国 7, 0, 0, 0, 0, 0, 0
Step3:
人 民 共 和 时 代
0, 1, 2, 3, 4, 5, 6
中 1, 1, 2, 3, 4, 5, 6
华 2, 2, 2, 3, 4, 5, 6
人 3, 2, 3, 3, 4, 5, 6
民 4, 3, 2, 3, 4, 5, 6
共 5, 4, 3, 2, 3, 4, 5
和 6, 5, 4, 3, 2, 3, 4
国 7, 6, 5, 4, 3, 3, 4
算法实现:
public static int LevenshteinDistance(string s1, string s2)
{
if (s1 == s2)
return 0;
else if (String.IsNullOrEmpty(s1))
return s2.Length;
else if (String.IsNullOrEmpty(s2))
return s1.Length;
var m = s1.Length + 1;
var n = s2.Length + 1;
var d = new int[m, n];
// Step1
for (var i = 0; i < m; i++) d[i, 0] = i;
// Step2
for (var j = 0; j < n; j++) d[0, j] = j;
// Step3
for (var i = 1; i < m; i++)
{
for (var j = 1; j < n; j++)
{
var cost = s1[i - 1] == s2[j - 1] ? 0 : 1;
var deletion = d[i - 1, j] + 1;
var insertion = d[i, j - 1] + 1;
var substitution = d[i - 1, j - 1] + cost;
d[i, j] = Math.Min(Math.Min(deletion, insertion), substitution);
}
}
return d[m - 1, n - 1];
}
2. LCS
LCS (Longest Common Subsequence) 算法用于找出两个字符串最长公共子串。
算法原理:
(1) 将两个字符串分别以行和列组成矩阵。
(2) 计算每个节点行列字符是否相同,如相同则为 1。
(3) 通过找出值为 1 的最长对角线即可得到最长公共子串。
人 民 共 和 时 代
中 0, 0, 0, 0, 0, 0
华 0, 0, 0, 0, 0, 0
人 1, 0, 0, 0, 0, 0
民 0, 1, 0, 0, 0, 0
共 0, 0, 1, 0, 0, 0
和 0, 0, 0, 1, 0, 0
国 0, 0, 0, 0, 0, 0
为进一步提升该算法,我们可以将字符相同节点(1)的值加上左上角(d[i-1, j-1])的值,这样即可获得最大公用子串的长度。如此一来只需以行号和最大值为条件即可截取最大子串。
人 民 共 和 时 代
中 0, 0, 0, 0, 0, 0
华 0, 0, 0, 0, 0, 0
人 1, 0, 0, 0, 0, 0
民 0, 2, 0, 0, 0, 0
共 0, 0, 3, 0, 0, 0
和 0, 0, 0, 4, 0, 0
国 0, 0, 0, 0, 0, 0
算法实现:
public static string LCS(string s1, string s2)
{
if (s1 == s2)
return s1;
else if (String.IsNullOrEmpty(s1) || String.IsNullOrEmpty(s2))
return null;
var d = new int[s1.Length, s2.Length];
var index = 0;
var length = 0;
for (int i = 0; i < s1.Length; i++)
{
for (int j = 0; j < s2.Length; j++)
{
// 左上角值
var n = i - 1 >= 0 && j - 1 >= 0 ? d[i - 1, j - 1] : 0;
// 当前节点值 = "1 + 左上角值" : "0"
d[i, j] = s1[i] == s2[j] ? 1 + n : 0;
// 如果是最大值,则记录该值和行号
if (d[i, j] > length)
{
length = d[i, j];
index = i;
}
}
}
return s1.Substring(index - length + 1, length);
}
分享到:
相关推荐
用本程序可得到字符串的相似度和字符串的公共子串以及编辑距离。
字符串相似度算法 字符串相似度算法 字符串相似度算法 字符串相似度算法 相似度 字符串
最大公共子串计算论文相似度:事件复杂度O(m*n),空间复杂度Omin(m,n)),可以用来计算两个字符串的最大公共子串长度、相似度;可以用于论文相似度量、地理信息等基于相似度量的查询等环境。由于空间复杂度低,因此可...
字符串相似度比较算法,可比较不同长度的任意两个字符串的相似度,以百分比显示。
输入2个中文字符串,计算2个字符串的相似度,用于相似度排序。
Levenshtein算法python也是用的这个对比字符串相似度的,还不错
比较两个字符串的相似度,利用Levenshein算法计算出两个字符串的最小编辑距离,根据最小编辑距离得出相似度,例如: 字符串1:1234 字符串2:51234,则他们的相似度为:4/5。
java 计算字符串相似度
就是一个简单的字符串相似度比较的方法,暂时还不知道有没有更好的方法,大家先看看,有更好的希望分享一下
Delphi计算或比较两组字符串的相似程度 对字符串进行挨个读取并进行比对,取得相似度
一个实现不同字符串相似度和距离度量的库。目前实现了十几种算法(包括 Levenshtein 编辑距离和兄弟、Jaro-Winkler、最长公共子序列、余弦相似度等)。查看下面的汇总表以获取完整列表... python字符串相似度 下载 ...
比较两个字符串的相似度,利用LCS算法计算出两个字符串的最长公序列,根据最长公序列得出相似度,例如: 字符串1:1234 字符串2:51234,则他们的相似度为:4*2/(4+5)。
关于字符串相似度检测的一个很好用的C代码
求N个字符串的最长公共子串,N,字符串长度不超过255。例如N=3,由键盘依次输入3个字符串为 Whatislocalbus? Namesomelocalbuses. loca1busisahighspeedI/Obusclosetotheprocessor. 则最长公共子串为“local...
用途:可用于论文抄袭检测、DNA等。...算法实现思路:通过对一个字符串插入、删除、替换转变成另一个字符串所需要的步骤称为距离,计算两个字符串之间的距离,从而可以得到两个字符串之间的相似度。
C#中文文本匹配,字符串匹配,中文词语匹配,计算2个句子相似度 中文匹配C#中文文本匹配,字符串匹配,中文词语匹配,计算2个句子相似度 C#中文文本匹配,字符串匹配,中文词语匹配,计算多个句子相似度 C#中文文本...
本文实例讲述了C语言求两个字符串的最长公共子串的方法。分享给大家供大家参考。具体实现方法如下: #include "stdio.h" #include "string.h" #include "stdlib.h" void getCommon(char str1[],char str2[],char * ...
两个字符串,计算出两个字符串的相似度,用于模糊匹配,很简单的小例子
通过编辑距离算法对两字符串相似度对比后顺序取出所有公共子串
Oracle字符相似度函数。在sql语句中直接用该函数来计算2个字符串相似度。