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

代码地址

赞 (0)

相关推荐

  • python将多个文本文件合并为一个文本的代码（便于搜索）

    但是,当一本书学过之后,对一般的技术和函数都有了印象,突然想要查找某个函数的实例代码时,却感到很困难,因为一本书的源代码目录很长,往往有几十甚至上百个源代码文件,想要找到自己想要的函数实例谈何容易? 所以这里就是要将所有源代码按照目录和文件名作为标签,全部合并到一处,这样便于快速的搜索.查找,不是,那么查找下一个--于是很快便可以找到自己想要的实例,非常方便.当然,分开的源代码文件依然很有用,同样可以保留.合并之后的源代码文件并不大,n*100KB而已,打开和搜索都是很快速的.大家可以将同一种编

  • 详解Python中的文本处理

    字符串 -- 不可改变的序列 如同大多数高级编程语言一样,变长字符串是 Python 中的基本类型.Python 在"后台"分配内存以保存字符串(或其它值),程序员不必为此操心.Python 还有一些其它高级语言没有的字符串处理功能. 在 Python 中,字符串是"不可改变的序列".尽管不能"按位置"修改字符串(如字节组),但程序可以引用字符串的元素或子序列,就象使用任何序列一样.Python 使用灵活的"分片"操作来引用子

  • Python基于动态规划算法计算单词距离

    本文实例讲述了Python基于动态规划算法计算单词距离.分享给大家供大家参考.具体如下: #!/usr/bin/env python #coding=utf-8 def word_distance(m,n): """compute the least steps number to convert m to n by insert , delete , replace . 动态规划算法,计算单词距离 >>> print word_distance("

  • python根据经纬度计算距离示例

    复制代码 代码如下: /** * 计算两点之间距离 * @param _lat1 - start纬度 * @param _lon1 - start经度 * @param _lat2 - end纬度 * @param _lon2 - end经度 * @return km(四舍五入) */public static double getDistance(double _lat1,double _lon1, double _lat2,double _lon2){ double lat1 = (Math

  • python写的一个文本编辑器

    复制代码 代码如下: #!/usr/bin/env python#-*- coding: utf-8 -*-#=============================================================================#     FileName:#         Desc:#       Author: ToughGuy#      Version: 0.0.1#   LastChange: 2013-02-20 14:52:11#      H

  • python根据距离和时长计算配速示例

    复制代码 代码如下: function cal_pace(d,h,m,s){ var distance = d; var hours = h; var minutes = m; var seconds = s; if(distance.length > 0 && hours.length > 0 && minutes.length > 0 && seconds.length > 0) {  var speed = parseFloat

  • python进阶教程之文本文件的读取和写入

    Python具有基本的文本文件读写功能.Python的标准库提供有更丰富的读写功能. 文本文件的读写主要通过open()所构建的文件对象来实现. 创建文件对象 我们打开一个文件,并使用一个对象来表示该文件: 复制代码 代码如下: f = open(文件名,模式) 最常用的模式有: 复制代码 代码如下: "r"     # 只读 "w"     # 写入 比如 复制代码 代码如下: >>>f = open("test.txt",&

  • Python转换HTML到Text纯文本的方法

    本文实例讲述了Python转换HTML到Text纯文本的方法.分享给大家供大家参考.具体分析如下: 今天项目需要将HTML转换为纯文本,去网上搜了一下,发现Python果然是神通广大,无所不能,方法是五花八门. 拿今天亲自试的两个方法举例,以方便后人: 方法一: 1. 安装nltk,可以去pipy装 (注:需要依赖以下包:numpy, PyYAML) 2.测试代码: 复制代码 代码如下: >>> import nltk  >>> aa = r''''' <html

  • Python文本相似性计算之编辑距离详解

    Python文本相似性计算之编辑距离详解

    编辑距离 编辑距离(Edit Distance),又称Levenshtein距离,是指两个字串之间,由一个转成另一个所需的最少编辑操作次数.编辑操作包括将一个字符替换成另一个字符,插入一个字符,删除一个字符.一般来说,编辑距离越小,两个串的相似度越大. 例如将kitten一字转成sitting:('kitten' 和 'sitting' 的编辑距离为3) sitten (k→s) sittin (e→i) sitting (→g) Python中的Levenshtein包可以方便的计算编辑距离

  • Python读写txt文本文件的操作方法全解析

    Python读写txt文本文件的操作方法全解析

    一.文件的打开和创建 >>> f = open('/tmp/test.txt') >>> f.read() 'hello python!\nhello world!\n' >>> f <open file '/tmp/test.txt', mode 'r' at 0x7fb2255efc00> 二.文件的读取 步骤:打开 -- 读取 -- 关闭 >>> f = open('/tmp/test.txt') >>&

随机推荐