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());
} |
本文转自william_xu 51CTO博客，原文链接：http://blog.51cto.com/williamx/747485，如需转载请自行联系原作者
