Je travaille sur un vérificateur orthographique en C ++ et je suis bloqué à une certaine étape de la mise en œuvre.
Disons que nous avons un fichier texte avec des mots correctement orthographiés et une chaîne entrée que nous souhaitons vérifier les fautes d'orthographe. Si cette chaîne est un mot mal orthographié, je peux facilement trouver sa forme correcte en cochant tous les mots dans le fichier texte et en choisissant celui qui diffère de celui-ci avec un minimum de lettres. Pour ce type d'entrée, j'ai implémenté une fonction qui calcule la distance d'édition Levenshtein entre 2 chaînes. Jusqu'à présent, si bon.
Maintenant, la partie difficile: Et si la chaîne entrée est une combinaison de mots mal orthographiés? Par exemple, "Iloevcokies". Compte tenu de ce que "i", "amour" et "cookies" sont des mots qui peuvent être trouvés dans le fichier texte, comment puis-je utiliser la fonction LEVENSHTEINE déjà implémentée pour déterminer quels mots du fichier conviennent à une correction? En outre, comment allez-y insérer des blancs dans les bonnes positions?
Une idée est la bienvenue :)
3 Réponses :
La correction d'orthographe des phrases peut être effectuée de quelques égards. Une solution nécessite d'avoir un index de mot bimagrams et des tri-grammes. Celles-ci pourraient bien sûr être immense. Une autre option serait d'essayer des permutations du mot avec des espaces insérés, puis effectuez une recherche sur chaque mot dans la phrase résultante. Jetez un coup d'œil à une simple implémentation d'un vérificateur orthographique par Peter Norvig de Google. De toute façon, envisagez d'utiliser un indice N-GRAM pour de meilleures performances, il existe des bibliothèques disponibles en C ++ pour référence.
Google et d'autres moteurs de recherche sont en mesure de procéder à une correction d'orthographe sur des expressions car elles ont un grand indice de requêtes et des ensembles de résultats associés, ce qui leur permet de calculer une hypothèse statistiquement bonne. Dans l'ensemble, le problème de correction d'orthographe peut devenir très complexe avec des méthodes telles que la correction contextuelle et la correction phonétique. Étant donné que l'utilisation des permutations de sous-termes possibles peut devenir coûteuse, vous pouvez utiliser certains types d'heuristiques, mais cela peut être hors de portée rapide.
Vous pouvez également envisager d'utiliser et une bibliothèque d'orthographe existante, telle que aspell .
Un point de départ pour une idée: l'un des meilleurs hits de votre distance L pour "iloevcokies" devrait être "cookies". Si vous pouvez modifier votre fonction de distance en L, suivez et renvoyez également un indice MIN-Index et MAX (c.-à-d. Ce match à partir duquel le caractère 5 et le caractère 10), vous pouvez supprimer cette sous-chaîne et re-vérifier l -Distance pour la chaîne avant elle et après elle, ensuite concaténate ceux d'une suggestion ...
Juste une pensée, bonne chance ....
Malheureusement, ce n'est pas si probable, vous pouvez également trébucher sur un mot totalement indépendant (c'est-à-dire que la distance d'édition ici serait quelque chose comme 6, c'est énorme).
Bien sûr, mais très peu de mots du tout seront proches de la distance d'édition. Les cookies pourraient toujours apparaître comme un coup de haut. Encore loin d'une solution complète cependant!
Je suppose que vous avez un index existant sur lequel vous exécutez votre distance de Levenshtein (par exemple, une trie, mais tout index trié fonctionne généralement bien).
Vous pouvez envisager l'ajout d'espaces blancs comme une opération d'édition régulière, c'est juste qu'il y a une torsion: vous avez besoin (alors) pour revenir à la racine de votre index pour le mot suivant.
De cette façon, vous obtenez le même indice, presque le même itinéraire, approximativement le même traversé, et il ne faut même pas avoir une incidence sur votre temps de fonctionnement.