如何优化此编辑距离代码,即找到 2 个值之间更改的位数!例如word1 = '010000001000011111101000001001000110001' word2 = '010000001000011111101000001011111111111'
当我尝试在 Hadoop 上运行时需要很长时间才能完成?
如何减少for循环和比较?
#!/usr/bin/python
import os, re, string, sys
from numpy import zeros
def calculateDistance(word1, word2):
x = zeros( (len(word1)+1, len(word2)+1) )
for i in range(0,len(word1)+1):
x[i,0] = i
for i in range(0,len(word2)+1):
x[0,i] = i
for j in range(1,len(word2)+1):
for i in range(1,len(word1)+1):
if word1[i-1] == word2[j-1]:
x[i,j] = x[i-1,j-1]
else:
minimum = x[i-1, j] + 1
if minimum > x[i, j-1] + 1:
minimum = x[i, j-1] + 1
if minimum > x[i-1, j-1] + 1:
minimum = x[i-1, j-1] + 1
x[i,j] = minimum
return x[len(word1), len(word2)]
最佳答案
在网上找了一个位计数算法,找到了this page ,其中有几个很好的算法。我最喜欢的是一个声称适用于 Python 2.6/3.0 的单行函数:
return sum( b == '1' for b in bin(word1 ^ word2)[2:] )
我没有 Python,所以无法测试,但如果这个不起作用,请尝试其他之一。关键是计算两个字的按位异或中 1 的个数,因为每个差值都会有一个 1。
您正在计算Hamming distance ,对吧?
编辑:我试图了解您的算法,以及您处理输入的方式,看起来它们实际上是数组,而不仅仅是二进制数。所以我希望您的代码看起来更像:
return sum( a != b for a, b in zip(word1, word2) )
EDIT2:我已经弄明白你的代码做了什么,它根本不是汉明距离!它实际上是 Levenshtein distance ,它计算将一个字符串转换为另一个字符串所需的添加、删除或替换次数(汉明距离仅计算替换次数,因此仅适用于等长的数字串)。查看维基百科页面,您的算法或多或少是他们那里的伪代码的直接端口。正如他们指出的那样,比较长度为 m 和 n 的字符串的时间和空间复杂度是 O(mn),这非常好坏的。他们根据您的需要有一些优化建议,但我不知道您使用此功能做什么,所以我不能说什么最适合您。如果汉明距离对你来说足够好,上面的代码应该足够了(时间复杂度 O(n)),但它在某些字符串集上给出不同的结果,即使它们长度相等,像 '0101010101' 和 '1010101010',它们的汉明距离为 10(翻转所有位)和 Levenshtein 距离为 2(删除第一个 0 并将其添加到末尾)
关于python - 如何优化编辑距离代码?,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/7036277/