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无损音乐搜索引擎实现代码

Python无损音乐搜索引擎实现代码

  研究了一段时间酷狗音乐的接口,完美破解了其vip音乐下载方式,想着能更好的追求开源,故写下此篇文章,本文仅供学习参考。虽然没什么技术含量,但都是自己一点一点码出来,一点一点...

pandas 根据列的值选取所有行的示例

如下所示: # 选取等于某些值的行记录 用 == df.loc[df['column_name'] == some_value] # 选取某列是否是某一类型的数值 用 isin...

python 的 scapy库,实现网卡收发包的例子

问题: 测试时 收发流采用TestCenter、SmartBit等仪表来进行。如果仍采用其进行自动化冒烟,则会带来效率低、成本高的问题。 解决方案: 采用网卡来收发流,虽然有性能统计上的...

Django 自定义分页器的实现代码

Django 自定义分页器的实现代码

为什么要实现分页? 在大部分网站中分页的功能都是必要的,尤其是在后台管理中分页更是不可或缺 分页能带给用户更好的体验,也能减轻服务器的压力 对于分页来说,有许多方法都可以实现 例如把数据...

Python脚本判断 Linux 是否运行在虚拟机上

在 WebHostingTalk 论坛上有些国外奸商会把虚拟机当作独立服务器卖,去年7月份的时候就有一位中国同胞上当受骗,并在 WHT 上发帖声讨,证据确凿,甚至连服务商自己也承认,回帖...