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
代码如下:
private final String content_regex = "(?i)[^a-zA-Z0-9\u4E00-\u9FA5]";
/**
* 判断两段正文相似度
* @param content1
* @param content2
* @return
*/
private float calculateContentSimilarity(String content1, String content2){
String s1 = content1.replaceAll("content_regex", "").trim();
String s2 = content2.replaceAll("content_regex", "").trim();
if(s1.equals(s2)){
return 1.00f;
}else {
if (s1.length() > s2.length() ? (s1.indexOf(s2) > -1)
: (s2.indexOf(s1) > 0)) {
return s1.length() > s2.length() ? ((float) s2
.length() / (float) s1.length()) : ((float) s1
.length() / (float) s2.length());
}
}
// return calculateSimilarityLCS(s1, s2);
return calculateContentSimilarityD(content1, content2);
}
/**
* 判断两段正文相似度
* @param content1
* @param content2
* @return
*/
private float calculateContentSimilarityD(String content1, String content2){
String[] s1 = content1.trim().split("。");
String[] s2 = content2.trim().split("。");
if(s1.length < s2.length){
String[] temp = s1;
s1 = s2;
s2 = temp;
}
float totalWeight = 0;
for (int i = 0; i < s2.length; i++) {
float unitWeight = 0;
for (int j = 0; j < s1.length; j++) {
if(content2.indexOf(s2[i]) > -1){
unitWeight = 1.00f;
break;
}
float weight = calculateSimilarityLCS(s2[i], s1[j]);
if (unitWeight < weight) {
unitWeight = weight;
}
}
totalWeight += unitWeight;
}
return (totalWeight/s2.length) * (s2.length/s1.length);
}
/**
* 判断两段文本相似度
* @param value1
* @param value2
* @return
*/
private float calculateSimilarityLCS(String s1, String s2) {
int[][] d = new int[s1.length()][s2.length()];
int index = 0;
int length = 0;
for (int i = 0; i < s1.length(); i++) {
for (int j = 0; j < s2.length(); j++) {
int n = i - 1 >= 0 && j - 1 >= 0 ? d[i - 1][j - 1] : 0;
d[i][j] = s1.charAt(i) == s2.charAt(j) ? 1 + n : 0;
if (d[i][j] > length) {
length = d[i][j];
index = i;
}
}
}
int begin = index - length + 1;
String simword = s1.substring(begin, begin + length) ;
return s1.length() > s2.length() ? ((float) simword
.length() / (float) s1.length()) : ((float) simword
.length() / (float) s2.length());
}
分享到:
相关推荐
一个简单的基于LCS的计算文本相似度的函数,新人所写,高手勿喷
根据LCS算法取出最长公用字符串,实现字符串比较
最长公共子序列,即LCS算法,用C#写的LCS算法实现过程
最长子序列LCS算法,用于处理最长公共字串问题。 两个序列的LCS问题包含两个序列的前缀的LCS,因此,LCS问题具有最优子结构性质。在设计递归算法时,不难看出递归算法具有子问题重叠的性质。 设C[i,j]C[i,j]...
比较两个字符串的相似度,利用LCS算法计算出两个字符串的最长公序列,根据最长公序列得出相似度,例如: 字符串1:1234 字符串2:51234,则他们的相似度为:4*2/(4+5)。
关于LCS(最长公共子序列)算法的实现~ 自己测试通过的
本程序是为了熟悉lcs算法,通过使用lcs算法来计算两篇文章的相似度
求2个序列的最大公共子序列,求出最优解,并打印出算法实现所需数组,C++实现。
LCS算法的精髓就是动态规划,序列其实不仅限于字符序列,因此我用模版类对该算法进行了封装,里面提供了尽量方便的函数来进行该算法的使用,该实现并不追求速度最快化,而是尽量让该算法类能支持重用,若发现算法有...
注:实在linux 平台下的,windows下未必能运行
#include "come.h" void main() { int N; N=4; char a[500]; char b[500];... LCS lcs1(a,b);... printf("\t最长公共子序列为: %s\n",lcs1.... printf("\t字符串%d阶N-gram相似度为: %f\n",ng1.N,ng1.ngram()); } }
最长公共子串匹配动态规划算法实现,源代码加注释,可运行啊,这描述限定真死板,还20 字符,吃多了啊
文本之间在相似度比较时主要考虑关键词的匹配特性,缺乏对关键词间组合关系的深入分析。针对关键词间组合特性,按序组合的关键词数目越大,对文本之间相似度贡献越大,并提出基于关键词组合数目的非线性语义关联性...
LCS算法的简单java实现,可以一起讨论学习
sim代码相似度算法大致实现,核心是用LCS最长公共子序列和DP动态规划。
借助LCS算法实现文本文档比对,可以自行扩展支持word等格式文件
LCS算法源码
实现了求最长公共子序列的算法,内容简单易懂,代码也很短
项目需要一个文本比较器 自己根据LCS longest Common Subsequence 编写的比较器。功能精简可以根据我的代码在扩展支持其他格式的比较。 VS2008的项目
lcs算法详解.pdf