Python实现计算最小编辑距离
作者:hebedich 发布时间:2021-07-16 19:26:18
标签: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
投稿
猜你喜欢
- 通用用法但上图的字段名,类型需要根据不同接口填写,如某服务接口:因而对应的上传代码如下:# 输出参数:请求响应报文import reques
- 1、实现效果2、实现步骤模块导入import os,sys,timefrom PyQt5 import QtCore,QtWidgets,Q
- <%@ Page Language="C#" AutoEventWireup="true" C
- 本文实例讲述了Python爬取国外天气预报网站的方法。分享给大家供大家参考。具体如下:crawl_weather.py如下:#encodin
- 在这里我们将介绍的是MySQL内存使用上的线程独享,线程独享内存主要用于各客户端连接线程存储各种操作的独享数据,如线程栈信息,分组排序操作,
- Microsoft? SQL Server? 2000 提供了两种主要机制来强制业务规则和数据完整性:约束和触发器。触发器是一种特殊类型的存
- 在上一篇关于绘画Sankey桑葚图的文章里,已经介绍过大致的过程,本文主要解决如何自定义/修改 所想要的颜色, 如下所示一个桑葚图:想要修改
- Python可以使用 xml.etree.ElementTree 模块从简单的XML文档中提取数据。 为了演示,假设你想解析Planet P
- <?php// 使用Memache 作为进程锁 class lock_processlock{// key 的前缀protected
- 对于Python开发用户来讲,安装第三方库是家常便饭,下面提供两种安装方式pycharm软件安装1.打开file>setting2.点
- 项目介绍背景:DC竞赛比赛项目,运用回归模型进 * 价预测。数据介绍:数据主要包括2014年5月至2015年5月美国King County的房
- python实现情感分析(Word2Vec)** 前几天跟着老师做了几个项目,老师写的时候劈里啪啦一顿敲,写了个啥咱也布吉岛,线下自己就瞎琢
- 1. 前言但是对于很多人来说,首先编写一款 App 需要一定的移动端开发经验,其次还需要另外编写无障碍服务应用,如此显得有一定难度的本篇文章
- 为了方便使用分类,我定义了一个分类表category,里面字段是id(自动编号) cat_name(分类名) pare
- //方法1:$ip = $_SERVER["REMOTE_ADDR"];echo $ip;//方法2:$user_IP
- 如何利用Image Data Type从数据库中读取图片,并在主页中显示图形?然后,写如下代码:< % @&nbs
- PHP有一组进程控制函数(编译时需要–enable-pcntl与posix扩展),使得php能实现跟c
- 先按照下面的表结构创建mysql_order_by_test数据表,我们用实例一点一点告诉你,MySQL order by的用法。ORDER
- 天冷,人懒,事多,我就不全文翻译了。只列几个标题,很多内容完全按照我自己的理解写了一下。想读原汁原味的请移步:Icon design tre
- np.nonzero函数是numpy中用于得到数组array中非零元素的位置(数组索引)的函数。一般来说,通过help(np.nonzero