编辑距离

发表于   |  

编辑距离

1. 定义

编辑距离，又称Levenshtein距离，是指两个字串之间，由一个转成另一个所需的最少编辑操作次数。

许可的编辑操作包括：将一个字符替换成另一个字符，插入一个字符，删除一个字符。

python里有专门的包实现python-Levenshtein

1
sudo pip install python-Levenshtein

2. python实现

2.1 python-Levenshtein

python里有专门的包实现python-Levenshtein

1
sudo pip install python-Levenshtein

  • Levenshtein.hamming(str1,str2)

    计算两个长度一致的字符串的hamming距离,返回值是对应位置上不同字符的个数

    ​

  • Levenshtein.distance(str1,str2)

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

    ​

  • Levenshtein.ratio(str1,str2)

    计算公式 r = (sum - ldist) / sum, 其中sum是指str1 和 str2 字串的长度总和，ldist是类编辑距离

    注意：这里的类编辑距离不是编辑距离，在此处，删除、插入依然+1，但是替换+2

    这样设计的目的：ratio(‘a’, ‘c’)，sum=2,按2中计算为（2-1）/2 = 0.5,’a’,’c’没有重合，显然不合算，但是替换操作+2，就可以解决这个问题。

2.2 如何用python实现编辑距离

(引自http://biansutao.iteye.com/blog/326008)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
# -*- coding: utf-8 -*-  
  
class arithmetic():  
      
    def __init__(self):  
        pass  
    ''''' 【编辑距离算法】 【levenshtein distance】 【字符串相似度算法】 '''  
    def levenshtein(self,first,second):  
        if len(first) > len(second):  
            first,second = second,first  
        if len(first) == 0:  
            return len(second)  
        if len(second) == 0:  
            return len(first)  
        first_length = len(first) + 1  
        second_length = len(second) + 1  
        distance_matrix = [range(second_length) for x in range(first_length)]   
        #print distance_matrix  
        for i in range(1,first_length):  
            for j in range(1,second_length):  
                deletion = distance_matrix[i-1][j] + 1  
                insertion = distance_matrix[i][j-1] + 1  
                substitution = distance_matrix[i-1][j-1]  
                if first[i-1] != second[j-1]:  
                    substitution += 1  
                distance_matrix[i][j] = min(insertion,deletion,substitution)  
        print(distance_matrix) 
        return distance_matrix[first_length-1][second_length-1]

参考文献：

使用Python计算文本相似性之编辑距离

http://biansutao.iteye.com/blog/326008)

http://www.coli.uni-saarland.de/courses/LT1/2011/slides/Python-Levenshtein.html#Levenshtein-inverse