Quel algorithme choisir ?

Question

A demandé lors d'une récente interview :

Quelle structure de données utiliseriez-vous pour implémenter la correction orthographique dans un document. Le but est de savoir si un mot donné tapé par l'utilisateur est dans le dictionnaire ou non (pas besoin de le corriger). Quelle est la complexité ?

Answer 1

J'utiliserais un arbre "Radix", ou "Patricia", pour indexer le dictionnaire. Voir ici, y compris un exemple de son utilisation pour indexer les mots du dictionnaire : https://secure.wikimedia.org/wikipedia/en/wiki/Radix_tree . Ce lien contient une discussion utile sur sa complexité.

Answer 2

Si je comprends bien la question, on vous donne un dictionnaire (ou une liste de mots "corrects"), et on vous demande de préciser si un mot entré figure dans le dictionnaire. Vous recherchez donc des structures de données avec des temps de recherche très rapides. J'opterais pour un table de hachage

Answer 3

J'utiliserais un DAWG (Directed Acyclic Word Graph) qui est en fait un fichier compressé Trie .

Ils sont couramment utilisés dans les algorithmes du Scrabble et d'autres jeux de mots, comme le Boggle.

J'ai déjà fait ça avant. Le dictionnaire de Scrabble TWL06, avec ses 170 000 mots, tient dans une structure de 700 Ko, à la fois sur disque et en RAM.

Answer 4

En distance de Levenshtein vous indique combien de lettres vous devez changer pour passer d'une chaîne à l'autre ... en trouvant celle qui comporte le moins de substitutions, vous êtes en mesure de fournir des mots corrects (voir aussi Distance Damerau Levenshtein )

Pour améliorer les performances, vous ne devez pas calculer la distance par rapport à l'ensemble de votre dictionnaire et la limiter par une heuristique, par exemple les mots qui commencent par la même lettre.

Answer 5

Filtre Bloom. Les faux positifs sont possibles, mais pas les faux négatifs. Comme vous connaissez le dictionnaire à l'avance, vous pouvez éliminer les faux négatifs en utilisant un hachage parfait pour votre entrée (dictionnaire). Vous pouvez également l'utiliser comme structure de données auxiliaire derrière votre structure de données de dictionnaire réelle.

edit : Bien sûr la complexité est O(1) pour le filtre bloom.