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("abc","abec")
  1
  >>> print word_distance("ababec","abc")
  3
  """
  len_1=lambda x:len(x)+1
  c=[[i] for i in range(0,len_1(m)) ]
  c[0]=[j for j in range(0,len_1(n))]
  for i in range(0,len(m)):
  #  print i,' ',
    for j in range(0,len(n)):
      c[i+1].append(
        min(
          c[i][j+1]+1,#插入n[j]
          c[i+1][j]+1,#删除m[j]
          c[i][j] + (0 if m[i]==n[j] else 1 )#改
        )
      )
  #    print c[i+1][j+1],m[i],n[j],' ',
  #  print ''
  return c[-1][-1]
import doctest
doctest.testmod()
raw_input("Success!")

希望本文所述对大家的Python程序设计有所帮助。

赞 (0)

相关推荐

  • Python实现计算最小编辑距离

    Python实现计算最小编辑距离

    最小编辑距离或莱文斯坦距离(Levenshtein),指由字符串A转化为字符串B的最小编辑次数.允许的编辑操作有:删除,插入,替换.具体内容可参见:维基百科-莱文斯坦距离.一般代码实现的方式都是通过动态规划算法,找出从A转化为B的每一步的最小步骤.从Google图片借来的图, Python代码实现, (其中要注意矩阵的下标从1开始,而字符串的下标从0开始): def normal_leven(str1, str2): len_str1 = len(str1) + 1 len_str2 = len

  • 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中的文本处理

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

  • 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') >>&

  • 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将多个文本文件合并为一个文本的代码（便于搜索）

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

  • 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

随机推荐