如何优化编辑距离代码？

Question

如何优化这个编辑距离的代码，也就是计算两个值之间改变了多少位！比如说，word1 = '010000001000011111101000001001000110001' 和 word2 = '010000001000011111101000001011111111111'。

我在Hadoop上运行的时候，花了很长时间才完成。

怎么才能减少循环和比较的次数呢？

#!/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

你的算法似乎做了很多工作。它把每一位都和对面的位向量里的所有位进行比较，这样的算法复杂度是 O(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)

这个矩阵可能对检测某些类型的编辑有用，但我不知道你想实现的编辑距离算法是什么，所以我真的无法告诉你怎么优化它。

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]

补充：另外，你没有提到你的数据集。根据数据集的特点，具体的实现可能会有所不同，以便更好地利用它。

Answer 3

我在网上找了一个计数位数的算法，发现了这个页面，里面有几个不错的算法。我最喜欢的是一个一行的函数，声称可以在Python 2.6 / 3.0上使用：

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

我没有Python，所以不能测试，如果这个不行，可以试试其他的。关键是要计算你两个词的按位异或（XOR）结果中1的数量，因为每个不同的地方都会有一个1。

你是在计算汉明距离吧？

编辑：我在试着理解你的算法，看到你对输入的处理方式，感觉它们实际上是数组，而不仅仅是二进制数字。所以我觉得你的代码应该更像这样：

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

编辑2：我明白了你的代码在做什么，其实它根本不是汉明距离！它实际上是莱文斯坦距离，这个距离计算的是把一个字符串变成另一个字符串需要多少次添加、删除或替换（汉明距离只计算替换，所以只适合长度相等的数字字符串）。从维基百科的页面来看，你的算法基本上是直接移植了那里的伪代码。正如他们所指出的，比较长度为m和n的字符串的时间和空间复杂度是O(mn)，这其实是比较糟糕的。他们根据你的需求提供了一些优化建议，但我不知道你用这个函数是干嘛的，所以不能说什么对你最好。如果汉明距离对你来说足够好，上面的代码应该就可以了（时间复杂度是O(n)），但在某些字符串组合上，它给出的结果会不同，即使它们长度相等，比如'0101010101'和'1010101010'，它们的汉明距离是10（翻转所有位），而莱文斯坦距离是2（去掉第一个0并把它加到最后）。