在上一篇文章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]
由于内存分配减少了,所以算法的效率也能提高一点,即使时间复杂度没有改变。
分享到:
相关推荐
SQL SERVER实现编辑距离(Edit Distance)算法,可进行模糊匹配查询
NULL 博文链接:https://biansutao.iteye.com/blog/326008
资源名:免疫算法程序实现_物流选址_matlab 资源类型:matlab项目全套源码 源码说明: 全部项目源码都是经过测试校正后百分百成功运行的,如果您下载后不能运行可联系我进行指导或者更换。 适合人群:新手及有一定...
本文主要介绍字符匹配算法-JaroWinklerDistance,并附有例子
levenshtein - 这是一个Go实现计算Levenshtein距离算法
DV-distance是一种基于多跳机制的定位算法, 其相邻节点间的距离通过RSSI测距技术实际测量得到。为了减少RSSI测距误差对定位精度的影响, 首先对RSSI测距误差进行修正, 再对已有的信标节点间计算距离误差修正值的方法...
用python 实现的编辑距离算法,支持权重的定义,和词语之间的关联
距离矢量算法(Distance Vector Algorithm)的动态路由
simhash 算法的 java 实现。特点计算字符串的 simhash通过构建智能索引来计算所有字符串之间的相似性,因此可以处理大数据使用使用输入文件和输出文件运行 Maininputfile 的格式(参见 src / test_in):一个文件每...
C#,字符串相似度的莱文斯坦距离(Levenshtein Distance)算法与源代码 莱文斯坦距离(Levenshtein Distance)用于衡量两个字符串之间的相似度。 莱文斯坦距离以俄国科学家(Vladimir I. Levenshtein)命名,他于...
LD算法(Levenshtein Distance)又称编辑距离算法(Edit Distance)。以字符串A通过插入字符、删除字符、替换字符变成另一个字符串B,那么操作的过程的次数表示两个字符串的差异。本资源为此算法的python实现。...
实现迪杰斯特拉算法 Dijkstra void main() { //设置初值 int u=1; //设源点的序号为1 for(int i=0; i; i++) { Visited[i]=0; path[i]=u-1; Distance[i]=Graph[u-1][i]; } Visited[u-1]=1; //源点已...
我们可以根据公式一得出Jaro得分:如果使用Jaro–Winkler,并且取范围因子P=0.1,我们会得出:P=0.1L=3假使串 s1 DWAYNE 并且 s
动态规划 编辑距离 可以用来判别字符串的差异
Distance.m蚁群算法
Frechet distance算法 C++源码
需求: 1 设计一个名为 MyPoint的类,表示一个带 x坐标和 y坐标的点.该类包括: * 两个带 get方法的数据域 x和 y分别表示... * 随后,设计并实现 k-均值 (k-means)聚类算法,将这 n个对象进行聚类,并输出聚类的结果。
这段代码实现了一个简单的三边定位算法,包括以下步骤: 定义了一个 Point 结构体用于表示坐标点,包括 x 和 y 两个成员变量。...这个示例代码实现了一个简单的三边定位算法,可以根据实际需求进行扩展和优化。
LevenshteinDistance(编辑距离)算法详解[借鉴].pdf
两个字符串的相似度算法实现——编辑距离之Levenshtein距离