À l'aide de python efficace pour calculer les distances de hamming

J'ai besoin de comparer un grand nombre de chaînes similaires à 50358c591cef4d76. J'ai une fonction de distance de Hamming (à l'aide de pHash) je peux utiliser. Comment puis-je le faire efficacement? Mon pseudo serait:

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

J'aimerais en sortie les résultats comme une matrice et d'être en mesure de récupérer les valeurs. Je tiens également à l'exécuter via Hadoop en Streaming!

Tous les pointeurs sont reçues avec reconnaissance.

Voici ce que j'ai essayé, mais il est lent:

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 ...
Si vous voulez comparer chaque chaîne avec chaque chaîne, vous aurez deux boucles imbriquées. Est-ce que vous voulez faire?

OriginalL'auteur schoon | 2014-07-04

  1. 6

    La distance paquet python fournit un calculateur de distance de hamming:

    import distance

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

    Il y a aussi un levenshtein package qui fournit des calculs de la distance de levenshtein. Enfin difflib peut donner quelques simples comparaisons de chaînes.

    Il n'y a plus d'informations et un exemple de code pour l'ensemble de ces sur cette vieille question.

    Votre code existant est lent parce que vous recalculer le hachage de fichier dans la plus à l'intérieur de la boucle, ce qui signifie que chaque fichier est haché beaucoup de temps. Si vous calculez la valeur de hachage d'abord, puis le processus sera beaucoup plus efficace:

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

    Ce processus implique fondamentalement O(N^2) des comparaisons afin de distribuer de façon appropriée pour une carte de réduire le problème consiste à prendre le jeu complet de cordes et de les diviser en B blocs où B^2 = M (B = nombre de chaîne de blocs, M = nombre de travailleurs). Donc, si vous aviez 16 cordes et 4 travailleurs, vous permettrait de diviser la liste des chaînes en deux blocs (donc une taille de bloc de 8). Un exemple de la division du travail suit:

    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)
    Merci pour votre aide, mais j'ai déjà un calculateur de Distance de Hamming. J'ai déplacer mon hachage à l'extérieur de la boucle, comme je le faisais beaucoup trop de temps.
    J'ai mis à jour ma réponse. Vous avez raison que le hachage de l'intérieur de la boucle est trop lent.
    Lien vers stackoverflow.com/questions/682367/... est cassé
    Pas de doute, amusant de police ont eu leur mot à dire. Dommage. Le seul lien qui a été mentionné que le manque d'exemples est levenshtein. Vous pouvez lire des exemples pour que ici: coli.uni-saarland.de/courses/LT1/2011/slides/...

    OriginalL'auteur Matthew Franglen