Algorithme Levenshtein: Comment puis-je répondre à ces exigences d'édition de texte?

Question

J'utilise l'algorithme Levenshtein pour répondre à ces exigences:

Lorsque vous recherchez un mot de N caractères, les mots à suggérer comme correction dans la base de données de mon dictionnaire sont les suivants:

Chaque mot du dictionnaire de N caractères qui a 1 caractère de différence avec le mot trouvé. Exemple: mot trouvé: bearn, mot du dictionnaire: bear

Chaque mot du dictionnaire de N + 1 caractères ayant N caractères égal au mot trouvé. Exemple: mot trouvé: ours, mot du dictionnaire: ours

Chaque mot du dictionnaire de N-1 caractères ayant N-1 caractères égaux au mot trouvé. Exemple: mot trouvé: ours, mot du dictionnaire: ours

J'utilise cette implémentation de l'algorithme Levenshtein en C ++ pour rechercher lorsqu'un mot a un nombre de Levenshtein égal à 1 (qui est le nombre de Levenshtein pour les trois cas), mais comment puis-je choisir le mot à suggérer? J'ai lu des articles sur Boyer-Moore-Horspool et Knuth-Morris-Pratt mais je ne suis pas sûr de savoir comment l'un ou l'autre peut être utile.

#include <string>
#include <vector>
#include <algorithm>

using namespace std;

int levenshtein(const string &s1, const string &s2)
{
   string::size_type N1 = s1.length();
   string::size_type N2 = s2.length();
   string::size_type i, j;
   vector<int> T(N2+1);

   for ( i = 0; i <= N2; i++ )
      T[i] = i;

   for ( i = 0; i < N1; i++ ) {
      T[0] = i+1;
      int corner = i;
      for ( j = 0; j < N2; j++ ) {
         int upper = T[j+1];
         if ( s1[i] == s2[j] )
            T[j+1] = corner;
         else
            T[j+1] = min(T[j], min(upper, corner)) + 1;
         corner = upper;
      }
   }
   return T[N2];
}

Answer 1

Vous pouvez également ajouter un l'excellent article de Norvig sur la correction orthographique à votre lecture.

Cela fait longtemps que je ne l'ai pas lu, mais je me souviens que cela ressemblait beaucoup à ce que vous écrivez.

Answer 2

Comme je l’ai dit ailleurs, Boyer-Moore n’est pas vraiment fait pour cela. Puisque vous souhaitez rechercher simultanément plusieurs morsures, l'algorithme de Wu et Manber devrait vous plaire davantage.

J'ai posté un code C ++ de validation de concept en réponse à une autre question . Respectez les mises en garde qui y sont mentionnées.

Answer 3

Pourquoi limiter la suggestion à un seul mot, pourquoi ne pas inclure un ensemble de mots? Si vous êtes limité à un seul mot, vous pouvez classer vos résultats selon une fréquence d'utilisation pré-calculée ou similaire. Cette fréquence peut être mise à jour en fonction des choix des utilisateurs dans la suggestion.

Par ailleurs, dans le cas où le mot d'origine ne contient pas d'erreur orthographique, vous pouvez définir un ordre de priorité pour les observations N + 1, ce qui correspondrait davantage à une saisie semi-automatique. Quoi qu'il en soit, je ne pense pas qu'il existe une façon correcte de le faire. Peut-être que si vos exigences sont plus précises, il serait plus facile de les préciser.

De plus, vous n'avez pas besoin de connaître Python pour comprendre les algorithmes décrits dans l'article de Norvig.

Answer 4

Si je vous ai bien compris, il n’ya pas de réponse correcte à votre question. Vous identifiez jusqu'à trois suggestions pour un mot donné à l'aide de Levenshtein. Il vous appartient de définir une règle permettant de choisir celle à utiliser et celles à filtrer. Ou peut-être devriez-vous les utiliser tous?

Il est intéressant de noter que l’extension Damerau de Levenshtein pourrait vous intéresser, où deux personnages échangés sont également considérés comme donnant un score de 1, au lieu de 2, ce qui revient à la vanille Levenshtein.