优化后的Levensthein distance算法实现

在上一篇文章Levenshtein distance算法实现中,笔者已经讲解了一般最小编辑距离的算法。该算法采用动态规划,时间复杂度是O(m*n),m,n分别为两个字符串的长度,而空间复杂度也是O(m*n),如果使用int作为矩阵元素的类型,则矩阵的占用空间大小为sizeof(int)*m*n,假如两个字符串的长度均为10000个字符,则矩阵大小为400MB,相当可观。参考一个快速、高效的Levenshtein算法实现,笔者重新实现了一遍Levenshtein distance算法,其主要思想就是利用两个列向量来代替矩阵,每次只保存当前状态和上一次运算状态,算法结束后并不能获得该两个字符串任意子序列之间的最小编辑距离。算法采用Python实现,代码如下:

#!/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, v1, v2 = m + 1, [], []
for i in range((n + 1)):
    v1.append(i)
    v2.append(i)
for i in range(m + 1)[1:m + 1]:
    for j in range(n + 1)[1:n + 1]:
        cost = 0
        if s1[i - 1] == s2[j - 1]:
            cost = 0
        else:
            cost = 1
        minValue = v1[j] + 1
        if minValue > v2[j - 1] + 1:
            minValue = v2[j - 1] + 1
        if minValue > v1[j - 1] + cost:
            minValue = v1[j - 1] + cost
        v2[j] = minValue
    for j in range(n + 1):
        v1[j] = v2[j]
print v2[n]

由于内存分配减少了,所以算法的效率也能提高一点,即使时间复杂度没有改变。

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

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏漫漫深度学习路

tensorflow学习笔记(四十):tensorflow语音识别 及 python音频处理库

tensorflow 语音识别 最近在做语音识别的项目,现在项目告一段落,就把最近碰到的东西做一个总结。 python中关于语音处理的库 scipy.io.wa...

1.2K9
来自专栏深度学习之tensorflow实战篇

tensorflow载入数据的三种方式 之 TF生成数据的方法

Tensorflow数据读取有三种方式: Preloaded data: 预加载数据 Feeding: Python产生数据,再把数据喂给后端。 Reading...

4264
来自专栏python读书笔记

《算法图解》note 9 动态规划1.动态规划定义2.与分治法及贪婪算法的区别3.动态规划的后续学习

2085
来自专栏数据科学与人工智能

Python语言做数据探索教程

本文总结Python语言做数据探索的知识。 类似R语言做数据探索,利用Python语言做数据探索。 1 数据导入 2 数据类型变换 3 数据集变换 4 数据排序...

3815
来自专栏老马说编程

(34) 随机 / 计算机程序的思维逻辑

随机 本节,我们来讨论随机,随机是计算机程序中一个非常常见的需求,比如说: 各种游戏中有大量的随机,比如扑克游戏洗牌 微信抢红包,抢的红包金额是随机的 北京购...

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

Day4晚笔记

数据结构 并查集:捆绑两个点的信息,判断对错 倍增:LCA, 字符串 hash,模拟, 最小表示法 给定一个环状字符串,切开,使得字符串的字典序最小 图和树 割...

2664
来自专栏计算机视觉与深度学习基础

HDU4832

由于水平和竖直相互独立,所以可以分开计数,最后再用组合数算一下,万年老坑long long #include<cstdio> #include<iostream...

20710
来自专栏null的专栏

数据结构和算法——用动态规划求解最短路径问题

一、动态规划求解问题的思路     在《算法导论》上,动态规划的求解过程主要分为如下的四步: 描述最优解的结构 递归定义最优解的值 按自底向上的方式计算最优解的...

4775
来自专栏蜉蝣禅修之道

网络流算法Dinic的Python实现

1554
来自专栏marsggbo

Udacity并行计算课程笔记- Fundamental GPU Algorithms (Reduce, Scan, Histogram)

如下图示,第一种情况只有一个工人挖洞,他需要8小时才能完成,所以工作总量(Work)是8小时。第二种情况是有4个工人,它们2个小时就能完成挖洞任务,此时工作总量...

1331

扫码关注云+社区

领取腾讯云代金券