Je me demande s'il existe une structure de données efficace pour effectuer "Récupérer toutes les chaînes avec une distance levenshtein inférieure à X".Façon d'implémenter "Obtenir toutes les chaînes avec une distance Levenshtein inférieure à X"
Peu de choses que je suis intéressé par:
c'est recherche neighborer le plus proche en fonction espace métrique avec la distance de levenshtein comme la métrique (ou distance)
un VP-tree est l'une des façons de résoudre ce problème
ce Python VP-tree implementation est une démo de travail qui montre comment un VP-tree fonctionne, disons une liste de mots il fournit un shell interactif où vous tapez un mot et il renvoie les mots de cette liste qui ne sont pas plus que X distance du mot que vous avez tapé
Semble comme un simple breadth-first search avec chaque génération étant juste un «edit» loin de la précédente - et avec des contrôles en place pour s'assurer qu'une chaîne apparaît dans un seul et unique niveau.
Ceci serait facilement implémenté en utilisant un couple de hashsets/hashtables dans une paire de boucles.
Cool. Je ne sais pas pourquoi il ne m'est jamais venu à l'esprit que les gens essaieraient de résoudre ce problème dans les espaces métriques généraux. Je regarderai. –