字串相似度-编辑距离

字符串编辑距离即 Levenshtein 距离

python库安装：

pip install python-Levenshtein

使用

1
2
3

import Levenshtein
str1="abc"
str2="bac"

edit distance(Levenshtein距离)

一个字串转化成另一个字串最少的操作次数(包括插入、删除、替换)

1	Levenshtein.distance(str1,str2)

要求str1和str2必须长度一致两个等长字串之间对应位置上不同字符的个数

1	Levenshtein.hamming(str1, str2)

计算公式 $$r = \frac{sum - ldist}{sum}$$, 表示两个字符串的相似度。

其中$\text{sum}$是指str1 和 str2 字串的长度总和，$\text{ldist}$是类编辑距离 .其中：删除、插入依然+1，但是替换+2 。

这样设计的目的：ratio(‘a’, ‘c’)，$sum=2$,如果按编辑距离计算$ldist$，则$ratio =\frac{2-1}2 = 0.5$,但是’a’,’c’没有重合，显然不合算，但是替换操作+2，就可以解决这个问题。

1	Levenshtein.ratio(str1, str2)

python-Levenshtein 还提供了Jaro distance 和 Jaro–Winkler distance 的文本距离的计算。用的时候再查。

参考资料