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程序设计有所帮助。
相关推荐
-
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根据经纬度计算距离示例
复制代码 代码如下: /** * 计算两点之间距离 * @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读写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文本相似性计算之编辑距离详解
编辑距离 编辑距离(Edit Distance),又称Levenshtein距离,是指两个字串之间,由一个转成另一个所需的最少编辑操作次数.编辑操作包括将一个字符替换成另一个字符,插入一个字符,删除一个字符.一般来说,编辑距离越小,两个串的相似度越大. 例如将kitten一字转成sitting:('kitten' 和 'sitting' 的编辑距离为3) sitten (k→s) sittin (e→i) sitting (→g) Python中的Levenshtein包可以方便的计算编辑距离
-
python将多个文本文件合并为一个文本的代码(便于搜索)
但是,当一本书学过之后,对一般的技术和函数都有了印象,突然想要查找某个函数的实例代码时,却感到很困难,因为一本书的源代码目录很长,往往有几十甚至上百个源代码文件,想要找到自己想要的函数实例谈何容易? 所以这里就是要将所有源代码按照目录和文件名作为标签,全部合并到一处,这样便于快速的搜索.查找,不是,那么查找下一个--于是很快便可以找到自己想要的实例,非常方便.当然,分开的源代码文件依然很有用,同样可以保留.合并之后的源代码文件并不大,n*100KB而已,打开和搜索都是很快速的.大家可以将同一种编
-
Python实现计算最小编辑距离
最小编辑距离或莱文斯坦距离(Levenshtein),指由字符串A转化为字符串B的最小编辑次数.允许的编辑操作有:删除,插入,替换.具体内容可参见:维基百科-莱文斯坦距离.一般代码实现的方式都是通过动态规划算法,找出从A转化为B的每一步的最小步骤.从Google图片借来的图, Python代码实现, (其中要注意矩阵的下标从1开始,而字符串的下标从0开始): def normal_leven(str1, str2): len_str1 = len(str1) + 1 len_str2 = len
-
python进阶教程之文本文件的读取和写入
Python具有基本的文本文件读写功能.Python的标准库提供有更丰富的读写功能. 文本文件的读写主要通过open()所构建的文件对象来实现. 创建文件对象 我们打开一个文件,并使用一个对象来表示该文件: 复制代码 代码如下: f = open(文件名,模式) 最常用的模式有: 复制代码 代码如下: "r" # 只读 "w" # 写入 比如 复制代码 代码如下: >>>f = open("test.txt",&
-
详解Python中的文本处理
字符串 -- 不可改变的序列 如同大多数高级编程语言一样,变长字符串是 Python 中的基本类型.Python 在"后台"分配内存以保存字符串(或其它值),程序员不必为此操心.Python 还有一些其它高级语言没有的字符串处理功能. 在 Python 中,字符串是"不可改变的序列".尽管不能"按位置"修改字符串(如字节组),但程序可以引用字符串的元素或子序列,就象使用任何序列一样.Python 使用灵活的"分片"操作来引用子
-
Python转换HTML到Text纯文本的方法
本文实例讲述了Python转换HTML到Text纯文本的方法.分享给大家供大家参考.具体分析如下: 今天项目需要将HTML转换为纯文本,去网上搜了一下,发现Python果然是神通广大,无所不能,方法是五花八门. 拿今天亲自试的两个方法举例,以方便后人: 方法一: 1. 安装nltk,可以去pipy装 (注:需要依赖以下包:numpy, PyYAML) 2.测试代码: 复制代码 代码如下: >>> import nltk >>> aa = r''''' <html
随机推荐
- angularjs实现搜索的关键字在正文中高亮出来
- 从头开始学代理(新手必读)(转帖) (一梦浮生)
- iOS9 系统分享调用之UIActivityViewController
- 求1000阶乘的结果末尾有多少个0
- Springboot使用POI实现导出Excel文件示例
- JS是否可以跨文件同时控制多个iframe页面的应用技巧
- jQuery+php实现ajax文件即时上传的详解
- Python不规范的日期字符串处理类
- 利用C++简单实现顺序表和单链表的示例代码
- mysql 一个较特殊的问题:You can't specify target table 'wms_cabinet_form'
- 详解addEventListener的三个参数之useCapture
- python中的__init__ 、__new__、__call__小结
- jquery中EasyUI实现异步树
- php curl登陆qq后获取用户信息时证书错误
- PHP临时文件的安全性分析
- 总结IOS关闭键盘/退出键盘的五种方式
- 使用Python的package机制如何简化utils包设计详解
- 详解Python读取yaml文件多层菜单
- Python实现多线程的两种方式分析
- iOS实现模拟定位功能的示例代码