Dictionnaire

Lors de la reconnaissance de caractères, même avec un algorithme de reconnaissance de caractère fonctionnel, des erreurs peuvent se glisser dans les mots.

Ces erreurs viennent souvent du fait que certaines lettres sont illisibles, d’où la nécessité d’implémenter une correction orthographique.

Principe

Nous disposons de plusieurs dictionnaires servant de base à la correction (Dictionnaire anglais et français déjà présents dans Linux).

Les dictionnaires sont de simples fichier texte contenant tous les mots d’une langue. Voici un exemple d’un “kikou-dictionnaire” contenant seulement des acronymes stupides:

“lol mdr kikou ptdr tkt rofl”

Nous extrayons donc les mots du dictionnaire afin de créer une table de hachage, qui nous permettra de détecter si un mot est mal orthographié, et donc de le corriger avec le mot le plus proche selon la distance d’édition de Levenshtein (Voir ci dessous).

Pour effectuer cela, nous comparons le mot entré en paramétré avec les mots extraits, et on recherche le mot ayant la plus petit distance d’édition avec notre mot.

Algorithme de Levenshtein

Pour savoir si un mot est correct ou non, on parcours les mots extraits à la recherche du mot.

Si ce dernier est trouvé, alors notre mot est correct, sinon, nous appliquons l’algorithme de Levenshtein, dont le fonctionnement est décrit ci dessous:

Tout d’abord, la distance de Levenshtein consiste à calculer le nombre minimum d’opérations simples à effectuer pour passer de notre mot à corriger, à un mot du dictionnaire.

Les opérations simples sont l’ajout d’un caractère, la suppression, ou l’édition, ou la transposition de deux caractères.

Par exemple, si A=piscine, B=piscyne, la distance de Levenshtein est égale à 1.

Pseudo code de l’Algorithme

entier DistanceDeLevenshtein(caractere chaine1[1..longueurChaine1],

caractere chaine2[1..longueurChaine2])

// d est un tableau de longueurChaine1+1 rangées et longueurChaine2+1 colonnes declarer entier d[0..longueurChaine1, 0..longueurChaine2] // i et j itèrent sur chaine1 et chaine2 declarer entier i, j, coût

pour i de 0 à longueurChaine1

d[i, 0] := i

pour j de 0 à longueurChaine2

d[0, j] := j

pour i de 1 à longueurChaine1

pour j de 1 à longueurChaine2

si chaine1[i] = chaine2[j] alors coût := 0

sinon coût := 1

d[i, j] := minimum(

d[i-1, j ] + 1, // effacement d[i, j-1] + 1, // insertion d[i-1, j-1] + coût // substitution

)

retourner d[longueurChaine1, longueurChaine2]