前一篇使用了LCS算法实现了文本相似度分析，使用过程中发现运行效率并不是太好，瓶颈主要体现在逐字比较的算法上，对于长一点的文本，其消耗的时间成倍增加。因此在不考虑使用基于语义分析（机器学习）算法的基础上，采用一种简化并且有效的方法。
Levenshtein Distance 该算法又称之为 "编辑距离"，用于计算两个字符串的相似程度。原理很简单，就是返回将第一个字符串转换(删除、插入、替换)成第二个字符串的编辑次数。次数越少，意味着字符串相似度越高。向上扩展至整篇文本，可以采用这种方法的变体实现，将原来的逐字转换为逐段。
算法过程：
1. 对两部分文本进行处理，将所有的非文本字符替换为分段标记“#”
2. 较长文本作为基准文本，遍历分段之后的短文本，发现长文本包含短文本子句后在长本文中移除。未发现匹配的字句累加长度。
3. 比较剩余文本长度与两段文本长度和。其值为不匹配比率。
代码如下：
| private final String content_regex = "(?i)[^a-zA-Z0-9\u4E00-\u9FA5]";
private float calculateContentSimilarityS(String content1, String content2){
if (content1 == null || content2 == null) {
return 0.00f;
}
if(content1.length() == 0 || content2.length() == 0){
return 0.00f;
}
String s1 = content1.replaceAll("content_regex", "").trim();
String s2 = content2.replaceAll("content_regex", "").trim();
if(s1.length() == 0 || s2.length() == 0){
return 0.00f;
} if (s1.equals(s2)) {
return 1.00f;
} else {
if (s1.length() > s2.length() ? (s1.indexOf(s2) > -1) : (s2
.indexOf(s1) > -1)) {
return s1.length() > s2.length() ? ((float) s2.length() / (float) s1
.length())
: ((float) s1.length() / (float) s2.length());
}
}
return calculateContentSimilarityDS(
content1.replaceAll(" ", "").replaceAll(content_regex, "#/"),
content2.replaceAll(" ", "").replaceAll(content_regex, "#/")); }
/**
* 判断两段正文相似度
*
* @param content1
* @param content2
* @return
*/
private float calculateContentSimilarityDS(String content1, String content2) { String s1;
StringBuffer s2; if(content1.length() > content2.length()){
s1 = content2;
s2 = new StringBuffer(content1);
} else{
s1 = content1;
s2 = new StringBuffer(content2);
}
String[] s1s = s1.split("#/");
int abandenCount = 0;
int totalLength = s1.length() + s2.length();
for (String s : s1s) {
int index = s2.indexOf("#" + s + "#");
if(index > 0){
s2 = s2.replace(index, index + s.length(), "");
} else{
abandenCount = s.length() + 1;
}
}
return 1.00f - ((float)(s2.length() + abandenCount) / (float)totalLength);
} |
附注：判断相似度阈值还需依据个人经验来进行设定，建议采用动态算法实现（对短文本要求较高的阈值，对长文本要求较低的阈值）。
本文转自william_xu 51CTO博客，原文链接：http://blog.51cto.com/williamx/752730，如需转载请自行联系原作者
