Levenshtein距离及其python实现

本文主要是介绍Levenshtein距离及其python实现，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

概念

Levenshtein距离，又称L氏编辑距离，是指两个字串之间，由一个转成另一个所需的最少编辑操作次数。原子编辑操作包括增、删、改，即插入一个字符，删除一个字符，将一个字符替换成另一个字符。一般来说， Levenshtein 距离越小，两个串的相似度越大。 Levenshtein 距离已经在DNA分析、拼音纠错、命名实体抽取、实体共指、机器翻译等方面有广泛应用。

算法实现

具体计算公式参见维基百科，下面从自然语言表达和python实现两个方面介绍其计算逻辑。

2.1 自然语言表达

例如要计算“垃圾消息”和“A垃圾信息”的 Levenshtein距离，步骤如下：

第一步：依据两字符串长度构造字符串矩阵，并填入相应的位置数据，如下表：

		垃	圾	消	息
	0	1	2	3	4
A	1
垃	2
圾	3
信	4
息	5

第二步：从3,3格开始，开始计算。取以下三个值的最小值：

（1）如果最上方的字符等于最左方的字符，则为左上方的数字。否则为左上方的数字+1。（对于3,3来说为1）

（2）左方数字+1（对于3,3格来说为2）

（3）上方数字+1（对于3,3格来说为2）

因此格3,3的取值为1，如下表：

		垃	圾	消	息
	0	1	2	3	4
A	1	1
垃	2
圾	3
信	4
息	5

第三步：循环使用第二步操作，将其他格子填满。结果如下表：

		垃	圾	消	息
	0	1	2	3	4
A	1	1	2	3	4
垃	2	1	2	3	4
圾	3	2	1	2	3
信	4	3	2	2	3
息	5	4	3	3	2

第四步：取右下角数值2，即为L氏编辑距离。

2.2 python实现

 def  levenshtein_distance(first , second): 
     '''
      计算两个字符串之间的L氏编辑距离
      :输入参数 first: 第一个字符串
      :输入参数 second: 第二个字符串
      :返回值: L氏编辑距离
      '''
       if  len(first) ==  0  or  len(second) ==  0: 
         return  len(first) +  len(second) 
     first_length =  len(first) +  1
      second_length =  len(second) +  1
      distance_matrix = [ range(second_length)  for  i  in  range(first_length)]  # 初始化矩阵
      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) 
     return distance_matrix[first_length- 1][second_length- 1] 
 
 
 if __name__ ==  '__main__': 
     print levenshtein_distance( u"垃圾消息" ,  u"A垃圾信息")  # 运行结果为：2
      