字符串相似度算法-莱文斯坦距离算法

莱文斯坦(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.whllinux安装 pip 安装Levenshtein模块 pip install python-Levenshtein计算两个字符串的相似度import Levenshteins3=‘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 Levenshteinimport jiebaautohome=‘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