Efektywne wykorzystanie pythona do obliczenia odległości Hamminga

Question

Potrzebuję porównać wiele ciągów podobnych do 50358c591cef4d76. Mam funkcję odległości Hamminga (używając pHash), z której mogę korzystać. Jak mogę to zrobić wydajnie? Mój Pseudokod byłoby:

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

Chciałbym wyjściowe wyniki jako matrycy i być w stanie odzyskać wartości. Chciałbym również uruchomić go za pośrednictwem Hadoop Streaming!

Wszelkie wskazówki są przesyłane z wdzięcznością.

Oto co próbowałem ale jest powolny:

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

Pakiet w Pythonie distance udostępnia kalkulator odległości Hamminga:

import distance 

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

Istnieje również levenshtein pakiet, który zapewnia dystans Levenshteina obliczenia. Wreszcie difflib może zapewnić pewne proste porównania ciągów.

Jest więcej informacji i przykładowy kod dla wszystkich z nich na this old question.

Twój istniejący kod jest powolny, ponieważ przeliczyłeś skrót pliku w najbardziej wewnętrznej pętli, co oznacza, że ​​każdy plik jest wielokrotnie mieszany. Jeśli obliczyć pierwszy hash wtedy proces będzie bardziej efektywny:

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

Proces ten zasadniczo obejmuje O(N^2) porównań tak aby rozprowadzać to w sposób odpowiedni dla mapy zmniejszyć Problem polega na pobraniu komplet strun i podzielenie je do B bloków, gdzie B^2 = M (B = liczba bloków ciąg, M = liczba pracowników). Więc jeśli masz 16 ciągów i 4 pracowników, podzielisz listę łańcuchów na dwa bloki (a więc rozmiar bloku 8). Przykład podziału pracy:

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)