Comment un correcteur orthographique devine-t-il le mot que vous vouliez écrire ? La distance entre deux mots

Pourquoi cette question : un modèle d'introduction

Le jury attend que vous expliquiez pourquoi vous avez choisi la question. Inspirez-vous de ce modèle, mais racontez votre propre parcours.

En spécialité LLCER, nous avons étudié l'orthographe anglaise, réputée l'une des plus irrégulières d'Europe, avec des règles comme « i before e, except after c » qui ont de nombreuses exceptions. J'utilise souvent un correcteur automatique et je me suis demandé comment il choisissait la bonne correction. J'ai découvert qu'il mesure une distance entre les mots, calculée par un algorithme récursif.

L'enjeu et les notions du programme

Définir une distance entre mots, la calculer par une relation de récurrence à deux indices et un tableau, et l'utiliser pour proposer une correction.

Le plan de l'exposé en 9,5 min

1. 1. Introduction

   1 min

   Quand on tape « recieve » ou « teh », le correcteur propose « receive » ou « the ». Problématique : comment mesurer la ressemblance entre deux mots pour choisir la meilleure correction ?

2. 2. Mathématiques : une distance calculée par récurrence

   4 min

   Opérations autorisées, chacune coûtant 1 : insérer une lettre, supprimer une lettre, remplacer une lettre. La distance de Levenshtein entre deux mots est le nombre minimal d'opérations pour passer de l'un à l'autre.

   Exemple : « kitten » → « sitting ». Remplacer k par s : « sitten » ; remplacer e par i : « sittin » ; insérer g : « sitting ». Trois opérations, et on ne peut pas faire moins : la distance vaut 3.

   Calcul général : on note $d(i,j)$d(i,j) la distance entre les $i$i premières lettres du premier mot et les $j$j premières du second. On a $d(i,0)=i$d(i,0)=i et $d(0,j)=j$d(0,j)=j. Puis $d(i,j)=\min (d(i-1,j)+1;d(i,j-1)+1;d(i-1,j-1)+c)$d(i,j)=minbigl(d(i-1,j)+1 ; d(i,j-1)+1 ; d(i-1,j-1)+cbigr), où $c=0$c=0 si les lettres $i$i et $j$j sont égales, 1 sinon. Les trois termes correspondent à une suppression, une insertion et une substitution.

   On remplit un tableau ligne par ligne, chaque case utilisant ses voisines déjà calculées : pour deux mots de 7 lettres, 49 cases suffisent, au lieu d'essayer toutes les suites d'opérations possibles. La case finale donne la distance.

   « recieve » et « receive » : la distance de Levenshtein vaut 2 (deux substitutions, i/e et e/i). Avec une quatrième opération, l'inversion de deux lettres voisines (distance de Damerau-Levenshtein), elle vaut 1. De même, « teh » est à distance 2 de « the », mais à 1 avec l'inversion. Comme les fautes de frappe sont souvent des inversions, les correcteurs l'utilisent.

   Le correcteur cherche les mots du dictionnaire à distance 1 ou 2, puis choisit le plus fréquent : c'est un compromis entre ressemblance et probabilité.

3. 3. In English: why is English spelling so strange?

   3 min

   English spelling is famous for its irregularities: "though", "through", "tough" and "cough" all end in "ough" but are pronounced differently. One reason is history: spelling was fixed by the first printers in the fifteenth century, while pronunciation kept changing, especially during the "Great Vowel Shift". Another reason is the many words borrowed from French, Latin and Greek, which kept their original spelling.

   Many people have tried to reform it. In the United States, Noah Webster's dictionary of 1828 simplified some spellings, which is why Americans write "color" and "center" while the British write "colour" and "centre". The writer George Bernard Shaw supported a completely new alphabet. None of these reforms changed English completely. Today, spell checkers have made spelling mistakes less visible, but some teachers worry that students no longer learn spelling rules. Others answer that the tools free writers to focus on what they want to say.

4. 4. Conclusion

   1,5 min

   La distance de Levenshtein, calculée par une récurrence à deux indices, vaut 3 entre « kitten » et « sitting », et un correcteur propose le mot du dictionnaire le plus proche et le plus fréquent. Un algorithme simple aide à vivre avec une orthographe irrégulière. J'ouvre sur l'usage de cette distance en génétique, pour comparer des séquences d'ADN.

Ce que j'écris au tableau

Pas de calculatrice ni de support numérique : un calcul clé écrit au tableau rend l'exposé concret et montre la solidité des connaissances.

Conclusion : la réponse à la question

Les questions probables du jury

Pendant les 10 minutesd'échange, le jury vous fait préciser et approfondir, sur tout le programme de vos spécialités en lien avec la question.

Les pièges qui coûtent des points

• Oublier l'initialisation d(i, 0) = i et d(0, j) = j.
• Confondre distance de Levenshtein et nombre de lettres différentes.
• Croire que la distance seule suffit à choisir la correction.

Revoir les notions

• Algorithmique et Python (Première spé maths) →
• Algorithmique et Python (Terminale spé maths) →

Autres questions : la langue comme donnée

• Pourquoi « the » représente-t-il 7 % des mots anglais ? La loi de Zipf
• Comment des statisticiens ont-ils découvert l'auteur de textes anonymes ? Les Federalist Papers
• Shakespeare avait-il un vocabulaire exceptionnel ? Compter les mots différents d'une œuvre
• Peut-on mesurer la difficulté d'un texte avec une formule ? L'indice de lisibilité de Flesch

Toutes les questions maths-llcer anglais →