Calcul rapide de la distance Levenshtein

Étant donné une énorme base de données de mots autorisés (triés par ordre alphabétique) et un mot, recherchez le mot de la base de données le plus proche du mot donné en termes de distance de Levenshtein.

L'approche naïve consiste, bien entendu, à simplement calculer la distance de levenshtein entre le mot donné et tous les mots du dictionnaire (on peut faire une recherche binaire dans la base de données avant de calculer réellement les distances).

Je me demande s'il existe une solution plus efficace à ce problème. Peut-être une heuristique qui nous permet de réduire le nombre de mots à rechercher, ou des optimisations à l'algorithme de distance levenshtein.

Liens vers des articles sur le sujet bienvenus.

Ce que vous demandez, c'est le problème de la recherche de voisins proches sous la distance de modification. Vous n'avez pas mentionné si vous êtes intéressé par les résultats théoriques ou l'heuristique, je vais donc répondre à la première.

La distance de montage est quelque peu désagréable à gérer pour la construction de structures de recherche proches voisins. Le problème principal est qu'en tant que métrique, elle se comporte (en quelque sorte) comme d'autres mauvaises métriques bien connues comme aux fins de réduction et d'approximation de dimensionnalité. Il y a un travail assez vaste à lire sur ce sujet, et votre meilleure source est l'ensemble des articles d' Alex Andoni : en suivant les pointeurs vers l'arrière (par exemple à partir de son article FOCS 2010), vous obtiendrez un bon ensemble de sources.$\ell_1$

Automates Levenshtein: http://en.wikipedia.org/wiki/Levenshtein_automaton

Arbres BK: http://en.wikipedia.org/wiki/BK-tree

Si vous avez un petit nombre de modifications erronées que vous allez tolérer, vous pouvez essayer d'utiliser un arbre de suffixes en pointillés . Avertissement: j'ai écrit ce document, mais il résout ce que vous voulez: il a un coût d'espace disque élevé, mais les requêtes sont vraiment rapides.

En général, il vaut mieux le regarder dans l'autre sens: vous avez un index de tous les mots du dictionnaire. Maintenant, pour un mot d'entrée w, s'il se trouve dans le dictionnaire, arrêtez. Sinon, générez toutes les variations à la distance 1 et recherchez-les. S'ils ne sont pas là, cherchez des variations à la distance 2, etc.

Il y a plusieurs améliorations à cette idée de base.

$O(m^{k+1} \cdot \sigma^{k})$$m$$\sigma$$k$

J'ai écrit une réponse à une question très similaire sur cs.stackexchange.com ( /cs//a/2096/1490 ), puis j'ai trouvé cette question. La réponse est pour la recherche approximative du voisin proche dans la distance d'édition (c'est-à-dire que l'algorithme génère une chaîne qui est approximativement aussi proche de la chaîne de requête que le plus proche voisin de la chaîne de requête). Je poste ici car je ne trouve aucune des références que j'ai données dans les réponses données ici.

Je pense que ce que vous voulez, c'est l'algorithme Wagner-Fischer: https://en.wikipedia.org/wiki/Wagner%E2%80%93Fischer_algorithm L'idée clé est que, puisque le dictionnaire que vous parcourez est trié, deux mots consécutifs sont très susceptibles de partager un long préfixe, vous n'avez donc pas besoin de mettre à jour la matrice entière pour chaque calcul de distance.

Vous pouvez utiliser Vouliez-vous dire?

Et puis trouvez la distance Levenshtein entre la réponse renvoyée par "Vouliez-vous dire" "et la chaîne de saisie à l'aide de la programmation dynamique.

Une façon consiste à former un modèle d'apprentissage automatique pour mapper les mots aux vecteurs et mapper la distance levenshtein à la distance euclidienne. Ensuite, vous pouvez créer un KDTree à partir des vecteurs du dictionnaire que vous souhaitez utiliser. J'ai créé un cahier jupyter qui le fait ici: https://gist.github.com/MichaelSnowden/9b8b1e662c98c514d571f4d5c20c3a03

Selon les commentaires de DW:

1. procédure de formation = descente de gradient stochastique avec gradients adaptatifs
2. fonction de perte = erreur quadratique moyenne entre la vraie distance d'édition et la distance euclidienne
3. données d'apprentissage = chaînes aléatoires de 1 à 32 caractères (pourraient être améliorées avec des données correspondant à une distribution réelle de fautes de frappe courantes)
4. résultats quantitatifs: après une formation d'environ 150 époques avec une taille de lot de 2048 (durée du mur = environ une minute), en utilisant des incorporations de mots de 512 dimensions, avec une couche cachée, l'erreur absolue moyenne entre la vraie distance d'édition et la distance d'édition prévue se situe à environ 0,75, ce qui signifie que la distance d'édition prévue est d'environ un caractère

Résumé de la structure du modèle:

1. Créez une incorporation apprise pour chaque caractère, y compris le caractère nul (utilisé plus tard pour compléter le texte à droite sous la limite de caractères)
2. Remplissez le côté droit du texte avec le caractère nul jusqu'à ce qu'il soit à la limite de caractères (32)
3. Concaténer ces plongements
4. Exécutez les plongements à travers un réseau de neurones à action directe pour produire une intégration de mots de dimension inférieure (512 dimensions)
5. Faites cela pour les deux mots
6. Trouver la distance euclidienne entre les vecteurs
7. Définir la perte comme étant l'erreur quadratique moyenne entre la vraie distance de Levenshtein et la distance euclidienne

Mes données d'entraînement ne sont que des chaînes aléatoires, mais je pense que les résultats pourraient vraiment s'améliorer si les données d'entraînement étaient des paires (faute de frappe / mot correct). J'ai fini par utiliser simplement /usr/share/dict/wordsparce qu'il est couramment disponible.