Discussion :

[hakim13700]

Bonjour, je suis entrain de créer une interface graphique pour un correcteur orthographique. Pour le moment j'arrive à charger mes dictionnaire. De plus quand je tape un mot pour vérifier si ce mot se trouve dans un des dictionnaire chargé cela marche !

Mon problème est que je n'arrive pas quand le mot n'y est pas à proposer des mot proche d'après mon ennoncé "Pour proposer des mots pouvant corriger une erreur, DiCo utilise une regle simple pour trouver les mots

proches d'un mot incorrect : dans chaque dictionnaire charge, DiCo cherche tous les mots (corrects)

qui ne diferent que d'une seule lettre du mot incorrect. Un mot Y ne difere d'un mot X que d'une

seule lettre si on peut passer de X a Y :

{ en enlevant une lettre quelconque a X

{ en ajoutant une lettre quelconque a X

{ en remplacant une lettre d'X par une lettre quelconque

{ en permuttant deux lettres quelconques d'X consecutives

Par exemple, le mot blid n'est pas un mot anglais correct, et DiCo peut proposer les mots blind,

bid, lid, bled ou blip pour la substitution, mais pas les mots bide, blade, bride, elide, glide ou

slide."

En espérant une réponse de votre part !! Merci d'avance et voici mon interface graphique

[dinobogan]

Ton énoncé m'a fait penser à "la distance de Levenshtein". Jette aussi un oeil à "la distance de Hamming" utilisée sur les codes correcteurs. C'est plus éloigné de ce que tu cherches mais ça pourrait te donner des idées.

[hakim13700]

on m'avait proposé d'utiliser matcher.find() mais bon la je suis bloqué je sait vraiment pas quoi faire...

[hakim13700]

Personne n'a une autre solution à me proposer ?? il faudrai que je fasse ca...

Etant donné un mot incorrect, il suffit de générer tous les mots qui diffèrent de ce mot incorrect d'une seule lettre. Par exemple, pour le mot incorrect 'tble', on va essayer d'ajouter une lettre à chaque position, et on va essayer :

- {a,b,c,..,z}tble (donc 26 mots)
- t{a,b,c,...,z}ble (donc encore 26 mots) : dans ce paquet, on trouve 'table'
- tb{a,b,c,...,z}le (encore 26 mots)
- ....

chaque mot généré est bien sûr cherché dans le dictionnaire et on ne retient que ceux qui sont corrects. On fait la même chose avec la suppression d'une lettre, la permutation de deux lettres, etc.

La méthode semble un peu "lourde", mais c'est en fait très rapide, car on ne génrère à chaque fois que de l'ordre de 26 mots, donc ça fonctionne parfaitement.

[dinobogan]

La méthode semble un peu "lourde", mais c'est en fait très rapide, car on ne génrère à chaque fois que de l'ordre de 26 mots, donc ça fonctionne parfaitement.

Donc ton problème est résolu ?

[hakim13700]

A non pardon !!! j'ai remis ce que mon professeur m'a répondu !! excusez moi ^^ !! ne faite pas attention au 2 dernière ligne...

[dinobogan]

La distance de Levenshtein répond exactement à ta problématique et sera bien plus rapide à l'exécution que l'algo présenté par ton prof et aussi plus simple à mettre en place.
L'algo de ton prof est très lent sur un mot inconnu qui ne sera pas trouvé dans le dictionnaire.
Présentation du pire cas : imaginons un mot de 6 lettres absent du dictionnaire que nous appellerons MOT. Imaginons ensuite un dictionnaire avec 1000 entrées. Tu souhaites codée une seule règle : il manque une lettre dans le mot.
La lettre peut être à 7 positions différentes. A partir de MOT, tu vas construire 7 * 26 = 182 mots, chacun est à trouver dans le dictionnaire, soit 182.000 tests minimum.
Et il te reste toutes les autres règles à vérifier !

La distance de Levenshtein fonctionne par parcours d'une matrice entre MOT et un mot du dictionnaire. Cette distance te permettra d'appliquer toutes les règles demandées ci-dessus en une seule passe de tout ton dictionnaire.
Pour chaque calcul de distance, tu conserves toujours la distance la plus petite MIN correspondant à un mot du dictionnaire LE_MOT. Dans les calculs suivants, tu arrêtes le calcul de la distance lorsqu'elle devient plus grande que MIN.
A la fin du parcours du dictionnaire, si la distance MIN est supérieure à 2 alors MOT n'est pas dans le dictionnaire, sinon, tu remplaces MOT par LE_MOT.

Maintenant, si le prof t'oblige à utiliser son algo, tu n'as plus qu'à le mettre en place, tu as tout ce qu'il faut.