Mit Python effizient Hamming-Distanzen berechnen

Question

Ich muss eine große Anzahl von Zeichenfolgen ähnlich wie 50358c591cef4d76 vergleichen. Ich habe eine Hamming-Distanz-Funktion (mit pHash), die ich benutzen kann. Wie mache ich das effizient? Mein Pseudocode wäre:

For each string 
    currentstring= string 
    For each string other than currentstring 
     Calculate Hamming distance 

Ich möchte die Ergebnisse als Matrix ausgeben und in der Lage sein, Werte abzurufen. Ich möchte es auch über Hadoop Streaming laufen lassen!

Alle Zeiger sind dankbar erhalten. Hier

ist, was ich versucht, aber es ist langsam:

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

Das distance Paket in Python bietet eine Hamming-Distanz Rechner:

import distance 

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

Es gibt auch ein levenshtein Paket, das levenshtein Abstand liefert Berechnungen. Schließlich kann difflib einige einfache Zeichenfolgenvergleiche bereitstellen.

Es gibt weitere Informationen und Beispielcode für alle diese auf this old question.

Ihr vorhandener Code ist langsam, weil Sie den Hash der Datei in der innersten Schleife neu berechnen, was bedeutet, dass jede Datei mehrmals gehackt wird. Wenn Sie die Hash-Berechnung zuerst, dann wird der Prozess wesentlich effizienter sein:

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

Dieser Prozess beinhaltet grundsätzlich O(N^2) Vergleiche so dass diese geeignet in einer Art und Weise zu verteilen, um eine Karte reduzieren Problem beinhaltet den kompletten Satz von Saiten nehmen und Dividieren sie in B Blöcke, wo B^2 = M (B = Anzahl der String-Blöcke, M = Anzahl der Arbeiter). Wenn Sie also 16 Strings und 4 Worker hätten, würden Sie die Liste der Strings in zwei Blöcke teilen (also eine Blockgröße von 8). Ein Beispiel für das Teilen der Arbeit folgt:

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)