Calculer la distance minimale de Hamming entre une corde et un ensemble de chaînes
-
21-12-2019 - |
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.
La solution
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 **