Discussion :

[fourgeaud]

Bonjour,

je dois realises un spellchecker (un correcteur orthographique) en gerant que certain cas.

Actuellement j'ai un algorithme qui :

1. transforme mon mot faut en regexp (ex : jjoobbb -> ^[j]+[aeiouy]+[b]+$ )
2. compare avec le dictionnaire pour recuperer tous les mots matchants avec la regexp
3. et pour finir je passe un algorithme de levenshtein dessus pour recuperer le plus probable.

La regex est en O(n) peut importe la longueur de la regex (n étant le mot a tester, donc ici chaque mot du dico).
Passant l'algo sur chaque mot du dico, je pense etre en O(nm) (m étant le nombre de mot du dico)
Et ensuite je passe levenshtein étant un algo en O(nm) sur les mots sauvegarder.

Que pensez-vous de la complexité finale de cette algo ?

Pour moi c'est O((nm)*2) soit o(nm) ?

Ou le situeriez-vous par rapport a O(n) ?


Merci d'avance pour votre aide !

[souviron34]

pour chaque mot tu dois passer à travers tous les autres, donc O(N^2)