高效使用Python计算汉明距离

Question

高效使用Python计算汉明距离

8

我需要比较大量类似于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 ...

- schoon

如果您想将每个字符串与每个字符串进行比较，那么您需要两个嵌套循环。这是您想要做的吗？ - user1907906

你可以使用ceja库来利用PySpark的强大功能，并在数十亿行数据上应用汉明距离算法。 - Powers

1个回答

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Matthew Franglen · Accepted Answer

在Python中，distance包提供了汉明距离计算器:

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)次比较，因此为了分布在适合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)