Algorithme de MS Word pour la correction

pour moi enfin ce que je pense c'est qu'il a un dico et à chaque fois que tu tapes une lettre il se déplace dans ce dico à la recherche du mot que tu es en train de taper et si il le trouve pas il te mets des mots existants.

Merci arth pour ta réponse ;)

Oui c'est ce que je croyais au début également, mais je pense bien que cette recherche de mots par "arbre" est en fait inéfficace, O(log n) pour le nombre d'opérations si n est le nombre de mots dans le dico, alors qu'un algorithme type HashMap permetterait d'arriver a faire la meme chose mais en un temps +/- = O(1) ...enfin c'est ce que j'ai lu qqpart donc je pose la question pour voir ce que vous en pensez :)

Merci :)

Des algos comme la distance de Hamming appliquée aux caractères, ou le soundex, je suppose.

http://fr.wikipedia.org/wiki/Distance_de_Hamming
http://en.wikipedia.org/wiki/Soundex

Il doit y avoir bien d'autres algos...

En me relisant, je me suis rendu compte que j'ai écrit une bêtise : HashMap n'est pas un algo mais une structure de données basée sur une fonction de hashage permettant l'indexation et donc une recherche rapide...une demi heure de flagelation s'impose :D

L'idée de la distance de Hamming est en fait une sorte de reflet de mon idée de base qui consiste a utiliser un hashage : si je fais un hashage sur les mots d'un dico et ensuite je compare chaque mot de mon texte a un de ces mot du "dico" a partir de leurs signatures respectives (signature = résultat de hashage) je pense pouvoir deja detecter les mots incorrects. L'étape suivante serait de proposer des mots du dico qui pourraient remplacer les mots incorrects, c'est la que une distance de hamming tunnée aux signatures serait la bienvenue :)
Qu'en pensez vous?

Merci encore pour vos réponses :)

Le problème du hashage, c'est qu'il sert à comparer des choses parfaitement identiques.

Il faudrait donc préparer à l'avance toutes les fautes de frappe possibles sur tous les mots, et les hasher. ça me semble long.

Il vaut mieux calculer la distance de Hamming entre le mot entré et les mots du dictionnaire, puis afficher ceux dont la distance est la plus faible.

(Je ne me souviens plus bien comment on calcul la distance de hamming, mais je crois me souvenir que 2 lettre interverties vaut +1 pour le score, une lettre remplacée par une autre vaut +1 également, une lettre omise vaut +1, etc.)

Ceci dit, je pense que ça serait plus efficace combiné au soundex
(pour retrouver les mots orthographiés très différemment (et donc ayant une distance de Hamming importante), mais ayant une sonorité très proche.)

D'ailleurs, pourquoi pas appliquer la distance de Hamming au code soundex des mots...

En effet, tu as raison, chaque hashé va etre unique si j'implémente a ma maniere précédamment décrite...neanmoins soundex me parait une bonne solution...mais avant, je vais tout de même essayer une petite tentation : implementer une methode basée sur la distance de hamming, et determiner statistiquement un rayon du "cerle de hamming" et tous les mots qui sont proches seront contenus dans ce cercle :) Facile a implémenter d'ici ce soir

Merci pour vos réponses je tiendrais au courant des résultats

Bien sûr si jamais ça marche pas, alors je le fais avec le code soundex ce week end car j'ai rien prévu et ma femme est partie en vacances sans moi (mysère) :D

slt à tt le monde j'ai un exercice si pouvez le faire