python - 如何优化编辑距离代码？

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

在网上找了一个位计数算法，找到了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 并将其添加到末尾)