Calculer la distance minimale de Hamming entre une corde et un ensemble de chaînes

Question

ex: Si j'ai la chaîne "asdf" et l'ensemble des chaînes ("qwer", "asdv", "asdv"). La distance de halogerie entre l'ensemble et la chaîne serait de 1 comme "ASDV" et "ASDF" ont une hamming distance une distance.

Il est facile de brute la force avec quelque chose comme ça

def hamming_distance(string, set):
    min = len(string)
    for element in set:
        element_distance = sum(ch1 != ch2 for ch1, ch2 in zip(string, element))
        if min > element_distance:
            min = element_distance
        if min == 0:
            break
    return min

Je pense que cela a O (n * k) où n= len (string) et k= len (ensemble). Cependant, les échelles de taille de jeu maximale avec N ^ 2, ce qui signifie que nous traitons essentiellement de O (n ^ 3). Les ensembles plutôt statiques, donc si le prétraitement vous aiderait à être définitivement une option.

Enfin, je devrais mentionner que l'application ici consiste à déterminer quels ensemble sont les plus proches de la chaîne en question, mais j'ai réduit le problème car la longueur de la chaîne est un facteur limitant beaucoup plus que le nombre d'ensembles . S'il y a une autre façon d'aborder cela en regardant l'espace dans son ensemble au lieu des sous-ensembles individuels, je serais toutes les oreilles. Quand j'ai pris cette approche d'abord, il semblait que la complexité spatiale allait devenir complètement ridicule.

Answer 1

Tout d'abord, la distance de hammage entre chaînes est une métrique. Ainsi, vous essayez de trouver les k-voisins les plus proches dans un espace métrique (où K= 1).

Par conséquent, vous voudrez peut-être envisager un arbre similaire à la structure de données M-Tree: (voir http://en.wikipedia.org/wiki/m-tree et http : //www.vldb.org/conf/1997/p426.pdf ). Cet arborescence est conçu pour réduire les comparaisons de distance à effectuer pour trouver les «voisins les plus proches».

Personnellement, je ne pouvais pas trouver une implémentation d'un m-arbre en ligne que j'étais satisfait (voir mon fil fermé à la recherche d'une mise en œuvre mature m-arbre), donc j'ai roulé le mien.

Ma mise en œuvre est la suivante: https://github.com/jon1van/mtreemapAprepo

La seule autre implémentation que je pouvais trouver était celle-ci: https://github.com/erdavila/m -Tree Je n'ai pas aimé cette implémentation car elle n'avait pas de fonctionnalité supprimée (et plusieurs autres problèmes) (mais c'était libre alors ... c'est bien).

Vous voudrez peut-être envisager d'utiliser mon code (qui résout les recherches de Knn dans un espace métrique générique) avec une métrique de distance de Levensthtein ( http://fr.wikipedia.org/wiki/levenshtein_distance ). Trouver une métrique de distance de LevenShtein entièrement implémentée doit être assez facile

Ajout de la fonction de lavenstein ** http://code.google.com/p/google-refine/source/browse/trunk/src/main/java/edu/mit/simile/vicino/distances/levenstetindistance.java?r= 181