Levenshtein distance最小编辑距离算法实现

Levenshtein distance,中文名为最小编辑距离,其目的是找出两个字符串之间需要改动多少个字符后变成一致。该算法使用了动态规划的算法策略,该问题具备最优子结构,最小编辑距离包含子最小编辑距离,有下列的公式。

其中d[i-1,j]+1代表字符串s2插入一个字母,d[i,j-1]+1代表字符串s1删除一个字母,然后当xi=yj时,不需要代价,所以和上一步d[i-1,j-1]代价相同,否则+1,接着d[i,j]是以上三者中最小的一项。

算法实现(Python):

假设两个字符串分别为s1,s2,其长度分别为m,n,首先申请一个(m+1)*(n+1)大小的矩阵,然后将第一行和第一列初始化,d[i,0]=i,d[0,j]=j,接着就按照公式求出矩阵中其他元素,结束后,两个字符串之间的编辑距离就是d[n,m]的值,代码如下:

#!/usr/bin/env python
# -*- coding: utf-8 -*-
__author__ = 'xanxus'
s1, s2 = raw_input('String 1:'), raw_input('String 2:')
m, n = len(s1), len(s2)
colsize, matrix = m + 1, []
for i in range((m + 1) * (n + 1)):
    matrix.append(0)
for i in range(colsize):
    matrix[i] = i
for i in range(n + 1):
    matrix[i * colsize] = i
for i in range(n + 1)[1:n + 1]:
    for j in range(m + 1)[1:m + 1]:
        cost = 0
        if s1[j - 1] == s2[i - 1]:
            cost = 0
        else:
            cost = 1
        minValue = matrix[(i - 1) * colsize + j] + 1
        if minValue > matrix[i * colsize + j - 1] + 1:
            minValue = matrix[i * colsize + j - 1] + 1
        if minValue > matrix[(i - 1) * colsize + j - 1] + cost:
            minValue = matrix[(i - 1) * colsize + j - 1] + cost
        matrix[i * colsize + j] = minValue
print matrix[n * colsize + m]

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏数值分析与有限元编程

一维变带宽存储刚度矩阵

我们知道,集成之后的整体刚度矩阵是一个对称的稀疏带状矩阵,如图1所示。这样的矩阵包含大量的0元素,占用大量的存储空间。为了节约存储空间,可采取一些方法对刚度矩阵...

4076
来自专栏崔庆才的专栏

TensorFlow RNN Cell源码解析

本文介绍下 RNN 及几种变种的结构和对应的 TensorFlow 源码实现,另外通过简单的实例来实现 TensorFlow RNN 相关类的调用。 RNN R...

5165
来自专栏Python小屋

详解Python科学计算扩展库numpy中的矩阵运算(1)

首先解答上一篇文章中使用with关键字让你的Python代码更加Pythonic最后的习题,该题答案是False,原因在于内置函数sorted()的参数reve...

2914
来自专栏小樱的经验随笔

MATLAB命令大全+注释小结

一、常用对象操作:除了一般windows窗口的常用功能键外。 1、!dir 可以查看当前工作目录的文件。   !dir& 可以在dos状态下查看。 2、who ...

3424
来自专栏深度学习与计算机视觉

理解ResNet结构与TensorFlow代码分析

该博客主要以TensorFlow提供的ResNet代码为主,但是我并不想把它称之为代码解析,因为代码和方法,实践和理论总是缺一不可。 github地址,其中...

8037
来自专栏漫漫深度学习路

pytorch学习笔记(二):gradient

gradient 在BP的时候,pytorch是将Variable的梯度放在Variable对象中的,我们随时都可以使用Variable.grad得到对应Var...

3008
来自专栏数据结构与算法

1099 字串变换 2002年NOIP全国联赛提高组

1099 字串变换 2002年NOIP全国联赛提高组  时间限制: 1 s  空间限制: 128000 KB  题目等级 : 黄金 Gold 题解 题目描述 D...

2593
来自专栏拂晓风起

妙用Pixel bender执行复杂运算/普通数据运算 传递Vector数组

1052
来自专栏mathor

从暴力递归到动态规划

 动态规划没有那么难,但是很多老师在讲课的过程中讲的并不好,由此写下一篇文章记录学习过程

2201
来自专栏Java Web

最长公共子序列问题

问题描述: 求两个字符序列的公共最长子序列。 ---- 最长公共子串 在回到子序列问题之前,先来了解一下子串的问题。 例如,HISH和FISH两个字符序列的公...

3794

扫码关注云+社区

领取腾讯云代金券