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读写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') >>&
-
python进阶教程之文本文件的读取和写入
Python具有基本的文本文件读写功能.Python的标准库提供有更丰富的读写功能. 文本文件的读写主要通过open()所构建的文件对象来实现. 创建文件对象 我们打开一个文件,并使用一个对象来表示该文件: 复制代码 代码如下: f = open(文件名,模式) 最常用的模式有: 复制代码 代码如下: "r" # 只读 "w" # 写入 比如 复制代码 代码如下: >>>f = open("test.txt",&
-
详解Python中的文本处理
字符串 -- 不可改变的序列 如同大多数高级编程语言一样,变长字符串是 Python 中的基本类型.Python 在"后台"分配内存以保存字符串(或其它值),程序员不必为此操心.Python 还有一些其它高级语言没有的字符串处理功能. 在 Python 中,字符串是"不可改变的序列".尽管不能"按位置"修改字符串(如字节组),但程序可以引用字符串的元素或子序列,就象使用任何序列一样.Python 使用灵活的"分片"操作来引用子
-
python将多个文本文件合并为一个文本的代码（便于搜索）
但是,当一本书学过之后,对一般的技术和函数都有了印象,突然想要查找某个函数的实例代码时,却感到很困难,因为一本书的源代码目录很长,往往有几十甚至上百个源代码文件,想要找到自己想要的函数实例谈何容易? 所以这里就是要将所有源代码按照目录和文件名作为标签,全部合并到一处,这样便于快速的搜索.查找,不是,那么查找下一个--于是很快便可以找到自己想要的实例,非常方便.当然,分开的源代码文件依然很有用,同样可以保留.合并之后的源代码文件并不大,n*100KB而已,打开和搜索都是很快速的.大家可以将同一种编
-
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文本相似性计算之编辑距离详解
编辑距离 编辑距离(Edit Distance),又称Levenshtein距离,是指两个字串之间,由一个转成另一个所需的最少编辑操作次数.编辑操作包括将一个字符替换成另一个字符,插入一个字符,删除一个字符.一般来说,编辑距离越小,两个串的相似度越大. 例如将kitten一字转成sitting:('kitten' 和 'sitting' 的编辑距离为3) sitten (k→s) sittin (e→i) sitting (→g) Python中的Levenshtein包可以方便的计算编辑距离
-
Python转换HTML到Text纯文本的方法
本文实例讲述了Python转换HTML到Text纯文本的方法.分享给大家供大家参考.具体分析如下: 今天项目需要将HTML转换为纯文本,去网上搜了一下,发现Python果然是神通广大,无所不能,方法是五花八门. 拿今天亲自试的两个方法举例,以方便后人: 方法一: 1. 安装nltk,可以去pipy装 (注:需要依赖以下包:numpy, PyYAML) 2.测试代码: 复制代码 代码如下: >>> import nltk >>> aa = r''''' <html
-
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基于动态规划算法计算单词距离.分享给大家供大家参考.具体如下: #!/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