J'essaie d'écrire un correcteur orthographique qui devrait fonctionner avec un dictionnaire assez volumineux. Je souhaite vraiment un moyen efficace d'indexer les données de mon dictionnaire en utilisant une distance de Damerau-Levenshtein pour déterminer les mots les plus proches du mot mal orthographié.
Je recherche une structure de données qui me permettrait de trouver le meilleur compromis entre complexité d'espace et complexité d'exécution.
D'après ce que j'ai trouvé sur Internet, j'ai quelques pistes concernant le type de structure de données à utiliser:
Trie
Ceci est ma première pensée et semble assez facile à mettre en œuvre et devrait permettre une recherche / insertion rapide. La recherche approximative utilisant Damerau-Levenshtein devrait également être simple à mettre en œuvre ici. Mais cela ne semble pas très efficace en termes de complexité d'espace, car vous avez probablement beaucoup de temps système avec le stockage de pointeurs.
Patricia Trie
Cela semble prendre moins de place qu'un Trie classique, car vous évitez en gros le coût de stockage des pointeurs, mais je crains un peu la fragmentation des données dans le cas de dictionnaires très volumineux comme celui que j'ai.
Arbre à suffixe
Je ne suis pas sûr de celui-ci, il semble que certaines personnes trouvent cela utile dans l'exploration de texte, mais je ne suis pas vraiment sûr de ce que cela donnerait en termes de performances pour un correcteur orthographique.
Arbre de recherche ternaire
Celles-ci sont plutôt jolies et, en termes de complexité, devraient être proches (meilleures?) De Patricia Tries, mais je ne suis pas certain en ce qui concerne la fragmentation si ce serait mieux ou pire que Patricia Tries.
Arbre d'éclatement
Cela semble un peu hybride et je ne suis pas sûr de l’avantage qu’il aurait sur Tries, mais j’ai lu à plusieurs reprises que c’est très efficace pour l’exploration de texte.
J'aimerais avoir quelques informations sur la meilleure structure de données à utiliser dans ce contexte et sur ce qui la rend meilleure que les autres. S'il me manque des structures de données qui seraient encore plus appropriées pour un correcteur orthographique, je suis également très intéressé.
la source
Réponses:
J'ai rencontré le même problème, mais j'ai adopté une approche différente. Vous pouvez construire une sorte de fonction "hash", qui donnera pour un mot similaire le même nombre ou un nombre proche.
Le problème, c’est que cette fonction, qui donnera un "bon" résultat pour les mots avec insertion / suppression, donnera un "mauvais" passage, et inversement Exemple: associez des lettres à des chiffres, des lettres similaires à des nombres adjacents et additionnez-les pour chaque lettre d'un mot. Créez ensuite des tables de hachage avec des ensembles pour chaque clé et recherchez une intersection pour un mot.
Peut-être que des résultats peuvent être obtenus si nous examinons un "espace" de mots. X pour changer de lettre, Y pour ajouter / supprimer, Z pour une transition ou quelque chose comme ça.
Cependant, ce ne sont que des idées abstraites, je n'ai pas assez de temps pour les mettre en œuvre.
la source
Ne stockez pas les chaînes dans l'arborescence métrique. Il suffit de stocker un index et de stocker les chaînes dans un arbre Patricia.
Je ne sais pas quel arbre utiliser. Cela dépendra de vos données et de vos besoins (avez-vous besoin d'une insertion rapide?). Mettez à jour votre question si vous trouvez qu'un arbre est plus efficace que les autres.
Vous pouvez également consulter des outils spécialisés, tels que lucene.
la source