python计算汉明距离_有效地使用python计算汉明距离

python中的

distance软件包提供汉明距离计算器：

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)