高效地使用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

的distance包在Python提供了汉明距离计算器：

import distance 

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

还有一个levenshtein包，它提供了Levenshtein距离计算。最后difflib可以提供一些简单的字符串比较。

有关于this old question上所有这些信息和示例代码的更多信息和示例代码。

您现有的代码很慢，因为您在最内层循环中重新计算文件哈希，这意味着每个文件都会被哈希多次。如果计算散列第一则该过程将变得更加高效：

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)比较，所以在某种程度上分发本适合地图缩小的问题包括采用一套完整的字符串和分裂他们到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)