有效地使用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中的距离包提供了一个汉明距离计算器:

import distance

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

还有一个levenshtein包,提供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)比较,因此以适合地图减少问题的方式分配这个过程涉及获取整套字符串并将它们分成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)