高效地使用python來計算海明距離

我需要比較類似於50358c591cef4d76的大量字符串。我可以使用海明距離功能（使用pHash）。我如何有效地做到這一點？我的僞代碼將是：高效地使用python來計算海明距離

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 ...

來源

2014-07-04 schoon

如果你想比較每個字符串與每個字符串，你將有兩個嵌套循環。那是你想要做的嗎？ –

的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)

來源

2014-07-04 10:33:57

感謝您的幫助，但我已經有一個海明距離計算器。我把哈希移動到循環之外，因爲我做了太多次。 – schoon

我已經更新了我的答案。你說得對，循環中的哈希太慢了。 –

鏈接到http://stackoverflow.com/questions/682367/good-python-modules-for-fuzzy-string-comparison is broken – codebox

高效地使用python來計算海明距離

回答

相關問題