【3】数据分析--15--levenshtein--两字符串相似度比较

一、简介

二、函数介绍

1. Levenshtein.hamming(str1, str2)

计算汉明距离。要求str1和str2必须长度一致。是描述两个等长字串之间对应位置上不同字符的个数。如

2. Levenshtein.distance(str1, str2)

计算编辑距离(也成Levenshtein距离)。是描述由一个字串转化成另一个字串最少的操作次数,在其中的操作包括插入、删除、替换。如

3. Levenshtein.ratio(str1, str2)

计算莱文斯坦比。计算公式 r = (sum - ldist) / sum, 其中sum是指str1 和 str2 字串的长度总和,ldist是类编辑距离 注意:这里的类编辑距离不是2中所说的编辑距离,2中三种操作中每个操作+1,而在此处,删除、插入依然+1,但是替换+2 这样设计的目的:ratio(‘a’, ‘c’),sum=2,按2中计算为(2-1)/2 = 0.5,’a’,‘c’没有重合,显然不合算,但是替换操作+2,就可以解决这个问题。

import Levenshtein

print Levenshtein.ratio('aaaa','aaac')
print Levenshtein.ratio('aaaa','aaacd')
print Levenshtein.ratio('aaaa','aaaA')

0.75
0.666666666667   # 因为是 (9-(1+2))/9
0.75

4. Levenshtein.jaro(s1, s2)

计算jaro距离,

$$ \begin{equation} d_{j} = \left \{ \begin{array}{lr} 0, & if m = 0 \\ \frac{1}{3}(\frac{m}{s_{1}} + \frac{m}{s_{2}} + \frac{m-t}{m} ) , & otherwise \end{array} \right. \end{equation} $$

其中的m为s1, s2的匹配长度,当某位置的认为匹配 当该位置字符相同,或者在不超过

t是调换次数的一半

5. Levenshtein.jaro_winkler(s1, s2)

计算Jaro–Winkler距离

$$ d_{w} =d_{j} + (lp(1-d_{j}))$$

三、算法介绍

1. Levenshtein距离

参考资料

个人公众号,比较懒,很少更新,可以在上面提问题,如果回复不及时,可发邮件给我: tiehan@sina.cn

Sam avatar
About Sam
专注生物信息 专注转化医学