首页 > 代码库 > 优化后的Levensthein distance算法实现
优化后的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 = http://www.mamicode.com/v1[j] + 1>由于内存分配减少了,所以算法的效率也能提高一点,即使时间复杂度没有改变。
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。