内容简介：本文由作者祝娜授权网易云社区发布。编辑距离（Edit Distance），又称Levenshtein距离，是指两个字串之间，由一个转成另一个所需的最少编辑操作次数。许可的编辑操作包括将一个字符替换成另一个字符，插入一个字符，删除一个字符。算法实现步骤:
本文由作者祝娜授权网易云社区发布。
本文对两种文本相似度算法进行比较。余弦值相似度算法 VS 最小编辑距离法
1、L氏编辑距离（基于词条空间）
编辑距离（Edit Distance），又称Levenshtein距离，是指两个字串之间，由一个转成另一个所需的最少编辑操作次数。许可的编辑操作包括将一个字符替换成另一个字符，插入一个字符，删除一个字符。
算法实现步骤:
| 1 |
设置n为字符串s的长度。("我是个小仙女") 设置m为字符串t的长度。("我不是个小仙女") 如果n等于0，返回m并退出。 如果m等于0，返回n并退出。 构造两个向量v0[m+1] 和v1[m+1]，串联0..m之间所有的元素。 |
| 2 | 初始化 v0 to 0..m。 |
| 3 | 检查 s (i from 1 to n) 中的每个字符。 |
| 4 | 检查 t (j from 1 to m) 中的每个字符 |
| 5 |
如果 s[i] 等于 t[j]，则编辑代价cost为 0； 如果 s[i] 不等于 t[j]，则编辑代价cost为1。 |
| 6 |
设置单元v1[j]为下面的最小值之一： a、紧邻该单元上方+1：v1[j-1] + 1 b、紧邻该单元左侧+1：v0[j] + 1 c、该单元对角线上方和左侧+cost：v0[j-1] + cost |
| 7 | 在完成迭代 (3, 4, 5, 6) 之后，v1[m]便是编辑距离的值。 |
我们得到最小编辑距离为1那么它们的相似度为 (1-ld/(double)Math.max(str1.length(), str2.length()));
1 - 1/8=7/8.
其算法实现（java）：
public static float levenshtein(String str1,String str2) {
//计算两个字符串的长度。
int len1 = str1.length();
int len2 = str2.length();
//建立上面说的数组，比字符长度大一个空间
int[][] dif = new int[len1 + 1][len2 + 1];
//赋初值，步骤B。
for (int a = 0; a <= len1; a++) {
dif[a][0] = a;
}
for (int a = 0; a <= len2; a++) {
dif[0][a] = a;
}
//计算两个字符是否一样，计算左上的值
int temp;
for (int i = 1; i <= len1; i++) {
for (int j = 1; j <= len2; j++) {
if (str1.charAt(i - 1) == str2.charAt(j - 1)) {
temp = 0;
} else {
temp = 1;
}
//取三个值中最小的
dif[i][j] = min(dif[i - 1][j - 1] + temp, dif[i][j - 1] + 1,
dif[i - 1][j] + 1);
}
}
float similarity =1 - (float) dif[len1][len2] / Math.max(str1.length(), str2.length());
return similarity;
}
2、余弦值（基于权值空间）
关于余弦相似度可以参照 百度词条 余弦相似度
通过测量两个向量之间的角的余弦值来度量它们之间的相似性。0度角的余弦值是1，而其他任何角度的余弦值都不大于1;并且其最小值是-1。从而两个向量之间的角度的余弦值确定两个向量是否大致指向相同的方向。所以，它通常用于文件比较。
算法步骤
预处理→文本特征项选择→加权→生成向量空间模型后计算余弦。
具体步骤见附件： 余弦相似度算法步骤解释.docx
其算法实现（java）:
public static double getSimilarity(String doc1, String doc2) { if (doc1 != null && doc1.trim().length() > 0 && doc2 != null && doc2.trim().length() > 0) {
MapAlgorithmMap = new HashMap(); // 将两个字符串中的中文字符以及出现的总数封装到，AlgorithmMap中
for (int i = 0; i < doc1.length(); i++) { char d1 = doc1.charAt(i); if (isHanZi(d1)) { int charIndex = getGB2312Id(d1); if (charIndex != -1) { int[] fq = AlgorithmMap.get(charIndex); if (fq != null && fq.length == 2) {
fq[0]++;
} else {
fq = new int[2];
fq[0] = 1;
fq[1] = 0;
AlgorithmMap.put(charIndex, fq);
}
}
}
} for (int i = 0; i < doc2.length(); i++) { char d2 = doc2.charAt(i); if (isHanZi(d2)) { int charIndex = getGB2312Id(d2); if (charIndex != -1) { int[] fq = AlgorithmMap.get(charIndex); if (fq != null && fq.length == 2) {
fq[1]++;
} else {
fq = new int[2];
fq[0] = 0;
fq[1] = 1;
AlgorithmMap.put(charIndex, fq);
}
}
}
}
Iteratoriterator = AlgorithmMap.keySet().iterator(); double sqdoc1 = 0; double sqdoc2 = 0; double denominator = 0; while (iterator.hasNext()) { int[] c = AlgorithmMap.get(iterator.next());
denominator += c[0] * c[1];
sqdoc1 += c[0] * c[0];
sqdoc2 += c[1] * c[1];
} double origin = denominator / Math.sqrt(sqdoc1 * sqdoc2); if (String.valueOf(origin).equals("NaN")) { return Double.valueOf("0");
}
BigDecimal bg = new BigDecimal(origin); double f1 = bg.setScale(2, BigDecimal.ROUND_HALF_UP).doubleValue(); return f1;
} else { throw new NullPointerException(" the Document is null or have not cahrs!!");
}
} public static boolean isHanZi(char ch) { // 判断是否汉字
return (ch >= 0x4E00 && ch <= 0x9FA5);
} /**
* 根据输入的Unicode字符，获取它的GB2312编码或者ascii编码，
*
* @param ch
* 输入的GB2312中文字符或者ASCII字符(128个)
* @return ch在GB2312中的位置，-1表示该字符不认识
*/
public static short getGB2312Id(char ch) { try { byte[] buffer = Character.toString(ch).getBytes("GB2312"); if (buffer.length != 2) { // 正常情况下buffer应该是两个字节，否则说明ch不属于GB2312编码，故返回'?'，此时说明不认识该字符
return -1;
} int b0 = (buffer[0] & 0x0FF) - 161; // 编码从A1开始，因此减去0xA1=161
int b1 = (buffer[1] & 0x0FF) - 161; // 第一个字符和最后一个字符没有汉字，因此每个区只收16*6-2=94个汉字
return (short) (b0 * 94 + b1);
} catch (UnsupportedEncodingException e) {
e.printStackTrace();
} return -1;
}
现在对两种计算相似度的算法进行比较：
编辑距离相似度运行结果：
'第六章 字符编码' 与 '第一章 设计模式' 的相似度为:0.07159507274627686
'第六章 字符编码' 与 '第二章 python 学习' 的相似度为:0.06676656007766724
'第六章 字符编码' 与 '第三章 python简介' 的相似度为:0.08275055885314941
'第六章 字符编码' 与 '第四章 输入输出' 的相似度为:0.1878122091293335
'第六章 字符编码' 与 '第五章 数据类型和变量' 的相似度为:0.20358151197433472
'第六章 字符编码' 与 '第六章 字符编码' 的相似度为:1.0
'第六章 字符编码' 与 '第七章 list' 的相似度为:0.20995670557022095
runtime:989毫秒
L编辑距离的时间 算法采用矩阵的方式，计算两个字符串之间的变化步骤，会遍历两个文本中的每一个字符两两比较，可以推断出时间复杂度至少为 document1.length × document2.length
cos相似度运行结果:
'第六章 字符编码' 与 '第一章 设计模式' 的相似度为:0.5
'第六章 字符编码' 与 '第二章 python学习' 的相似度为:0.59
'第六章 字符编码' 与 '第三章 python简介' 的相似度为:0.68
'第六章 字符编码' 与 '第四章 输入输出' 的相似度为:0.62
'第六章 字符编码' 与 '第五章 数据类型和变量' 的相似度为:0.72
'第六章 字符编码' 与 '第六章 字符编码' 的相似度为:1.0
'第六章 字符编码' 与 '第七章 list' 的相似度为:0.59
runtime:400毫秒
使用余弦定理计算文本效率相对比较高：其算法复杂度大致为：document1.length + document2.length。
但是同时也可以看出 余弦相似度得到的结果相对比较高一些。使用分词或者过滤掉一些常用词会对结果的准确性更有利。
使用分词的方法在本文中没有展开。但是如果去掉文章里的“的、了、吧，呢、啊”等可以提高结果的准确率。当然同时也可以提高判断的阀值。
运行结果：
'第六章 字符编码' 与 '第一章 设计模式' 的相似度为:0.37
'第六章 字符编码' 与 '第二章 python学习' 的相似度为:0.48
'第六章 字符编码' 与 '第三章 python简介' 的相似度为:0.57
'第六章 字符编码' 与 '第四章 输入输出' 的相似度为:0.56
'第六章 字符编码' 与 '第五章 数据类型和变量' 的相似度为:0.67
'第六章 字符编码' 与 '第六章 字符编码' 的相似度为:1.0
'第六章 字符编码' 与 '第七章 list' 的相似度为:0.48
runtime:519毫秒
看以看出准确度有了一定的提高。
番外：
L编辑距离动态计算法，调用python脚本实现，脚本文件
__author__ = 'victor'
#-*- coding:utf-8 -*-
import sys
import Levenshtein
if __name__ == "__main__":
if(len(sys.argv) < 3):
print('Usage: python myratiodetect.py str1 str2')
exit(-1)
str1 = sys.argv[1]
str2 = sys.argv[2]
r = Levenshtein.ratio(str1, str2)
print(r)
exit(0)
本地运行的前提为：已经适应pip安装了：python_Levenshtein，所以其对服务器的依赖比较大，如果工程环境迁移了的话，会比较受影响。
程序的运行结果：
'第六章 字符编码' 与 '第一章 设计模式' 的相似度为:0.157063851181
'第六章 字符编码' 与 '第二章 python学习' 的相似度为:0.165801038753
'第六章 字符编码' 与 '第三章 python简介' 的相似度为:0.194563908481
'第六章 字符编码' 与 '第四章 输入输出' 的相似度为:0.268671351528
'第六章 字符编码' 与 '第五章 数据类型和变量' 的相似度为:0.300997688969
'第六章 字符编码' 与 '第六章 字符编码' 的相似度为:1.0
'第六章 字符编码' 与 '第七章 list' 的相似度为:0.296406739228
runtime:2247毫秒
运行速度.....比较慢..2333
参考：
https://www.2cto.com/kf/201407/314271.html
http://wdhdmx.iteye.com/blog/1343856
http://blog.sina.com.cn/s/blog_4a6b27a30102vbr0.html
http://blog.sina.com.cn/s/blog_15be922b70102xc2s.html
更多网易技术、产品、运营经验分享请访问网易云社区。
相关文章：
【推荐】 数据仓库的直白概述
【推荐】 基于 cookie 的 node 中间层灰度流程的一些思考
【推荐】 一招搞定短信验证码服务不稳定
以上所述就是小编给大家介绍的《文本相似度 余弦值相似度算法 VS L氏编辑距离（动态规划）》，希望对大家有所帮助，如果大家有任何疑问请给我留言，小编会及时回复大家的。在此也非常感谢大家对 码农网 的支持！
猜你喜欢:
- 从勾股定理到余弦相似度：程序员的数学基础
- ICML新研究提出泛化能力评估新指标：直接上向量余弦距离就OK，还开源了相关代码
- 通俗易懂--决策树算法、随机森林算法讲解(算法+案例)
- 限流算法之漏桶算法、令牌桶算法
- 什么是Paxos算法？Paxos算法是区块链核心算法之一
- 一文读懂对称加密算法、非对称加密算法和Hash算法
本站部分资源来源于网络，本站转载出于传递更多信息之目的，版权归原作者或者来源机构所有，如转载稿涉及版权问题，请联系我们。
创业的艺术2.0
〔美〕盖伊·川崎 / 刘悦、段歆玥 / 译言·东西文库／电子工业出版社 / 2016-9 / 68
“创业者导师”——盖伊•川崎的《创业的艺术2.0》被阿丽亚娜•赫芬顿评为“终极的创业手册”。无论您是企业家、小企业主、企业开拓者还是非盈利组织的领导人，都可以让你的产品、服务或理念获得成功。 盖伊选取了不用角度，探索前十年商界的巨大变化，并寻求解决之道。曾经所向披靡的市场巨头深陷水深火热之中，社交媒体也取代了人际关系和广告，成为营销推广的主要渠道。众筹也成为广大投资者的可行之举。“云”更是每......一起来看看 《创业的艺术2.0》 这本书的介绍吧!
