高效计算汉明距离的Python使用方法

Question

我需要比较很多类似于50358c591cef4d76的字符串。我有一个可以用的汉明距离函数（使用pHash）。我该怎么高效地做到这一点呢？我的伪代码是：

For each string
    currentstring= string
    For each string other than currentstring
        Calculate Hamming distance

我想把结果输出成一个矩阵，并能够提取其中的值。我还希望通过Hadoop Streaming来运行这个程序！

如果有任何建议，我会非常感激。

这是我尝试过的，但速度很慢：

import glob
path = lotsdir + '*.*'
files = glob.glob(path)
files.sort()
setOfFiles = set(files)
print len(setOfFiles)
i=0
j=0
for fname in files:
    print 'fname',fname, 'setOfFiles', len(setOfFiles)
    oneLessSetOfFiles=setOfFiles
    oneLessSetOfFiles.remove(fname)
    i+=1

    for compareFile in oneLessSetOfFiles:
        j+=1
        hash1 = pHash.imagehash( fname )
        hash2 = pHash.imagehash( compareFile)
        print ...     

Answer 1

在Python中，有一个叫做 distance 的包，它可以用来计算汉明距离：

import distance

distance.levenshtein("lenvestein", "levenshtein")
distance.hamming("hamming", "hamning")

还有一个叫做 levenshtein 的包，可以用来计算莱文斯坦距离。最后，difflib 也可以用来进行一些简单的字符串比较。

关于这些包的更多信息和示例代码，可以在 这个旧问题 中找到。

你现有的代码运行得很慢，因为你在最内层的循环中重新计算文件的哈希值，这意味着每个文件都被哈希了很多次。如果你先计算哈希值，那么这个过程会高效得多：

files = ...
files_and_hashes = [(f, pHash.imagehash(f)) for f in files]
file_comparisons = [
    (hamming(first[0], second[0]), first, second)
    for second in files
    for first in files
    if first[1] != second[1]
]

这个过程本质上涉及到 O(N^2) 次比较，所以要把这个过程分配成适合map reduce的问题，就需要把所有字符串分成 B 个块，其中 B^2 = M（B = 字符串块的数量，M = 工作线程的数量）。所以如果你有16个字符串和4个工作线程，你就可以把字符串列表分成两个块（每块8个字符串）。下面是分配工作的一个例子：

all_strings = [...]
first_8 = all_strings[:8]
last_8 = all_strings[8:]
compare_all(machine_1, first_8, first_8)
compare_all(machine_2, first_8, last_8)
compare_all(machine_3, last_8, first_8)
compare_all(machine_4, last_8, last_8)