Python实现计算最小编辑距离

yipeiwu_com5年前Python基础

最小编辑距离或莱文斯坦距离(Levenshtein),指由字符串A转化为字符串B的最小编辑次数。允许的编辑操作有:删除,插入,替换。具体内容可参见:维基百科—莱文斯坦距离。一般代码实现的方式都是通过动态规划算法,找出从A转化为B的每一步的最小步骤。从Google图片借来的图,

Python代码实现, (其中要注意矩阵的下标从1开始,而字符串的下标从0开始):

 def normal_leven(str1, str2):
   len_str1 = len(str1) + 1
   len_str2 = len(str2) + 1
   #create matrix
   matrix = [0 for n in range(len_str1 * len_str2)]
   #init x axis
   for i in range(len_str1):
     matrix[i] = i
   #init y axis
   for j in range(0, len(matrix), len_str1):
     if j % len_str1 == 0:
       matrix[j] = j // len_str1

   for i in range(1, len_str1):
     for j in range(1, len_str2):
       if str1[i-1] == str2[j-1]:
         cost = 0
       else:
         cost = 1
       matrix[j*len_str1+i] = min(matrix[(j-1)*len_str1+i]+1,
                     matrix[j*len_str1+(i-1)]+1,
                     matrix[(j-1)*len_str1+(i-1)] + cost)

   return matrix[-1]

最近看文章看到Python库提供了一个包difflib实现了从对象A转化对象B的步骤,那么计算最小编辑距离的代码也可以这样写了:

 def difflib_leven(str1, str2):
  leven_cost = 0
  s = difflib.SequenceMatcher(None, str1, str2)
  for tag, i1, i2, j1, j2 in s.get_opcodes():
    #print('{:7} a[{}: {}] --> b[{}: {}] {} --> {}'.format(tag, i1, i2, j1, j2, str1[i1: i2], str2[j1: j2]))

    if tag == 'replace':
      leven_cost += max(i2-i1, j2-j1)
    elif tag == 'insert':
      leven_cost += (j2-j1)
    elif tag == 'delete':
      leven_cost += (i2-i1)
  return leven_cost

代码地址

相关文章

python并发和异步编程实例

关于并发、并行、同步阻塞、异步非阻塞、线程、进程、协程等这些概念,单纯通过文字恐怕很难有比较深刻的理解,本文就通过代码一步步实现这些并发和异步编程,并进行比较。解释器方面本文选择pyth...

Python中字典和JSON互转操作实例

JSON是一种轻量级的数据交换格式,各种语言都有良好的支持。字典是Python的一种数据结构。可以看成关联数组。 有些时候我们需要设计到字典转换成JSON序列化到文件,或者从文件中读取J...

Python实现3行代码解简单的一元一次方程

本文所述实例为Python用3行代码实现解一元一次方程,代码简洁高效,具体用法如下: >>> solve("x - 2*x + 5*x - 46*(235-24)...

Python 求数组局部最大值的实例

求数组局部最大值 给定一个无重复元素的数组A[0…N-1],求找到一个该数组的局部最大值。规定:在数组边界外的值无穷小。即:A[0]>A[-1],A[N-1] >A[N]。 显然,遍历一...

更改Python的pip install 默认安装依赖路径方法详解

更改Python的pip install 默认安装依赖路径方法详解

前言 声明:python版本3.6,以下讨论的Python也都是适用于3.x版本 在实际使用安装python的pip安装 依赖库是非常的便捷的。 而且一般大家使用的都是安装Anacond...