如何优化编辑距离代码

Question

如何优化这个编辑距离代码，即找到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)]

Answer 1

我在网上寻找位计数算法，我找到了这个页面，其中有几个很好的算法。我最喜欢的是一个声称可以在Python 2.6/3.0下工作的单行函数:

return sum( b == '1' for b in bin(word1 ^ word2)[2:] )

我没有Python，所以我不能测试，但如果这个不起作用，试试其他的一个。关键是要计算两个单词的按位异或中1的个数，因为每个差异都会有一个1。

你在计算汉明距离，对吧?

编辑:我试图理解你的算法，以及你操纵输入的方式，看起来它们实际上是数组，而不仅仅是二进制数。所以我希望你的代码看起来更像:

return sum( a != b for a, b in zip(word1, word2) )

我知道你的代码是干什么的了，根本不是汉明距离!它实际上是Levenshtein距离，它计算将一个字符串转换为另一个字符串所需的添加、删除或替换次数(Hamming距离只计算替换次数，因此只适用于长度相等的数字字符串)。看看维基百科页面，你的算法或多或少是他们那里的伪代码的直接移植。正如他们所指出的，长度为m和n的字符串的比较的时间和空间复杂性是O(mn)，这是非常糟糕的。他们根据您的需求提供了一些优化建议，但我不知道您使用这个函数的目的，所以我不能说什么最适合您。如果汉明距离对你来说足够好，上面的代码应该足够了(时间复杂度O(n))，但是它在一些字符串集合上给出了不同的结果，即使它们是相同的长度，比如'0101010101'和'10101010 '，它们的汉明距离为10(翻转所有比特)和Levenshtein距离为2(删除第一个0并在末尾添加)

Answer 2

由于您还没有指定要使用的编辑距离，所以我将冒险假设它是Levenshtein距离。在这种情况下，您可以在这里或那里省去一些操作:

def levenshtein(a,b):
    "Calculates the Levenshtein distance between a and b."
    n, m = len(a), len(b)
    if n > m:
        # Make sure n <= m, to use O(min(n,m)) space.
        # Not really important to the algorithm anyway.
        a,b = b,a
        n,m = m,n
    current = range(n+1)
    for i in range(1,m+1):
        previous, current = current, [i]+[0]*n
        for j in range(1,n+1):
            add, delete = previous[j]+1, current[j-1]+1
            change = previous[j-1]
            if a[j-1] != b[i-1]:
                change = change + 1
            current[j] = min(add, delete, change)
    return current[n]

edit:同样，你没有提到你的数据集。根据它的特点，实现可能会改变以从中受益。

Answer 3

你的算法似乎做了很多工作。它将每个位与相反位向量中的所有位进行比较，这意味着你得到的算法复杂度为0 (m*n)。如果你在计算汉明距离，这是不必要的，所以我假设你没有。

你的循环构建了一个x[i,j]矩阵，看起来像这样:

   0  1  0  0  0  0  0  0  1  0  0 ... (word1)
0  0  1  0  0  0  0  0  0  1
1  1  0  1  1  1  1  1  1  0
0  0  1  0  1  1  1  1  1  1
0  0  1  1  0  1  1  1  1  2
0  0  1  1  1  0  1  1  1  2
0  0  1  1  1  1  0  1  1  2
1
1
...
(example word2)

这对于检测某些类型的编辑可能很有用，但是在不知道你要实现的编辑距离算法的情况下，我真的无法告诉你如何优化它。