优化后的Levensthein distance算法实现

forrestlin

发布于 2018-05-24 10:06:09

1.6K0

发布于 2018-05-24 10:06:09

文章被收录于专栏：蜉蝣禅修之道

在上一篇文章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]

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

本文参与腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。

原始发表：2014年08月20日，如有侵权请联系 cloudcommunity@tencent.com 删除

编程算法