共计 1575 个字符，预计需要花费 4 分钟才能阅读完成。
莱文斯坦 (Levenshtein) 距离
莱文斯坦距离可以解决字符串相似度的问题。在莱文斯坦距离中，对每一个字符都有三种操作: 删除、添加、替换例如有 s1 和 s2 两个字符串，a 和 b 是与之对应的保存 s1 和 s2 全部字符的数组，i/ j 是数组下标。莱文斯坦距离的含义，是求将 a 变成 b(或者将 b 变成 a)，所需要做的最小次数的变换。
举个例子，字符串 ”kitten” 与“sitting”的莱文斯坦距离是 3，因为将 kitten 变为 sitting，最少需要三次变换：第一步 kitten -> sitten（字符 k 变成 s）
sitten -> sittin（字符 e 变成 i）
sittin -> sitting（在末尾插入字符 g）
python 实现
莱文斯坦距离的 python 模块在 https://github.com/ztane/pyth…，py2 和 py3 都支持。
安装 Levenshtein 模块
windows 安装
1，pip 安装 Levenshtein 模块
pip install python-Levenshtein
具体安装过程中，需要 C ++ 14.0 以上版本支持。C++ 下载路径:https://support.microsoft.com/en-us/help/2977003/the-latest-supported-visual-c-downloads
2，源码安装
首先下载 python_Levenshtein 的源码:https://www.lfd.uci.edu/~gohlke/pythonlibs/#python-levenshtein
下载的时候，注意源码包的 python 版本与本机安装 python 版本一致；同时需要注意的是，系统的位数。
拿 python_Levenshtein‑0.12.0‑cp36‑cp36m‑win_amd64.whl 为例，cp36 表示 python 版本是 python3.6，amd64 表示支持 64 位 windows 系统。
pip install python_Levenshtein‑0.12.0‑cp36‑cp36m‑win_amd64.whl
linux 安装
pip 安装 Levenshtein 模块
pip install python-Levenshtein
计算两个字符串的相似度
import Levenshtein
s3=’kitten’
s4=’sitting’
result=Levenshtein.ratio(s3,s4)
print(‘s3:%s,s4:%s:similar:%s’ % (s3,s4,str(result)))
#s3:kitten,s4:sitting:similar:0.6153846153846154
案例
计算两个字符串 list 的相似度
import Levenshtein
import jieba
autohome=’2009 款 1.6L 自动 G 特别版 ’
#current=’ 花冠 2009 款 1.6L 自动 G 特别版 ’
current=’2009 款 自动 G 特别版 1.6L’
autohome_jieba_gene=jieba.cut(autohome)
current_jieba_gene=jieba.cut(current)
l1 = list(autohome_jieba_gene)
l2 = list(current_jieba_gene)
listSimilar=Levenshtein.seqratio(l1,l2)
print(‘l1:%s,l2:%s,similar:%s’ %(repr(l1),repr(l2),str(listSimilar)))
#l1:[‘2009’, ‘ 款 ’, ‘ ‘, ‘1.6’, ‘L’, ‘ ‘, ‘ 自动 ’, ‘G’, ‘ 特别版 ’],l2:[‘2009’, ‘ 款 ’, ‘ ‘, ‘ 自动 ’, ‘G’, ‘ 特别版 ’, ‘ ‘, ‘1.6’, ‘L’],similar:0.6666666666666666
