Correcteur orthographique — Distance de Levenshtein
Une entreprise développe un correcteur orthographique intelligent pour une suite bureautique. Le système doit détecter les fautes de frappe, suggérer des corrections, analyser la similarité entre documents et construire un index de recherche approximative. Le cœur du système repose sur la distance d'édition (distance de Levenshtein), qui mesure le nombre minimal d'opérations élémentaires (insertion, suppression, substitution) pour transformer un mot en un autre.
Objectif
Implémenter progressivement un correcteur orthographique complet : de la distance de Levenshtein naïve jusqu'à un graphe de corrections, en passant par la programmation dynamique, les variantes de distance, et l'indexation par ABR.
dictionnaire = [
'algorithm', 'algebra', 'alteration', 'altering',
'banana', 'balance', 'bandana', 'barrier',
'chapter', 'character', 'charge', 'chart',
'distance', 'distinct', 'distort', 'distribute',
'element', 'elephant', 'elevation', 'eliminate',
'function', 'fundamental','furnace', 'further',
'grammar', 'graphic', 'grateful', 'gravity',
'language', 'lantern', 'laptop', 'lateral',
'matrix', 'matter', 'measure', 'mention',
'pattern', 'pause', 'pencil', 'person',
'random', 'range', 'rational', 'reason',
'science', 'screen', 'segment', 'sentence',
'triangle', 'trigger', 'triple', 'trivial',
]
# Coûts des opérations (utilisés dans les variantes pondérées)
COUTS = {
'insertion' : 1,
'suppression' : 1,
'substitution' : 2, # substitution coûte 2 car = suppr + insert
'transposition': 1, # échange de deux lettres adjacentes
}
# Mots mal orthographiés à corriger (requêtes utilisateur)
requetes = [
'algorythm', # -> algorithm
'bananaa', # -> banana
'distanse', # -> distance
'elefant', # -> elephant
'fuction', # -> function
'grammer', # -> grammar
'laanguage', # -> language
'matirx', # -> matrix
'patern', # -> pattern
'randon', # -> random
]
Avant d'aborder la distance d'édition, on se familiarise avec les structures de données Python en manipulant le dictionnaire de mots : indexation, regroupement, analyse morphologique et filtrage par longueur.
Écrire une fonction construire_index(dictionnaire) qui retourne un dictionnaire {lettre_initiale: [mots]} regroupant les mots par leur première lettre, chaque groupe trié alphabétiquement.
Exemple
construire_index(dictionnaire)['a']
['algebra', 'algorithm', 'alteration', 'altering']
On parcourt le dictionnaire et on regroupe par première lettre avec setdefault, puis on trie chaque liste.
def construire_index(dictionnaire):
index = {}
for mot in dictionnaire:
lettre = mot[0]
index.setdefault(lettre, []).append(mot)
for lettre in index:
index[lettre].sort()
return index
construire_index(dictionnaire)['a'] → ['algebra', 'algorithm', 'alteration', 'altering']
Complexité
- Temps : O(D log D) — D mots, tri par groupe.
- Espace : O(D) — copie du dictionnaire.
Écrire une fonction infos_mot(mot) qui retourne un tuple (mot, longueur, nb_voyelles, nb_consonnes, premiere_lettre, derniere_lettre).
Exemple
infos_mot('algorithm')
('algorithm', 9, 3, 6, 'a', 'm')
def infos_mot(mot):
VOYELLES = set('aeiouAEIOU')
nb_voyelles = sum(1 for c in mot if c in VOYELLES)
nb_consonnes = len(mot) - nb_voyelles
return (mot, len(mot), nb_voyelles, nb_consonnes, mot[0], mot[-1])
infos_mot('algorithm')
→ ('algorithm', 9, 3, 6, 'a', 'm')
Écrire une fonction mots_par_longueur(dictionnaire) qui retourne un dictionnaire {longueur: [mots]} regroupant les mots par leur nombre de caractères, chaque groupe trié alphabétiquement.
Exemple
mots_par_longueur(dictionnaire)[7]
['balance', 'barrier', 'chapter', 'furnace', 'lantern', 'mention', 'pattern', 'segment', 'trivial']
def mots_par_longueur(dictionnaire):
groupes = {}
for mot in dictionnaire:
l = len(mot)
groupes.setdefault(l, []).append(mot)
for l in groupes:
groupes[l].sort()
return groupes
mots_par_longueur(dictionnaire)[7] → ['balance', 'barrier', 'chapter', 'furnace', 'lantern', 'mention', 'pattern', 'segment', 'trivial']
Écrire une fonction prefixes_communs(mot1, mot2) qui retourne la longueur du plus long préfixe commun des deux mots et la chaîne correspondante.
Exemples
prefixes_communs('algorithm', 'algebra')
prefixes_communs('matrix', 'matter')
prefixes_communs('banana', 'pattern')
(3, 'alg') (3, 'mat') (0, '')
def prefixes_communs(mot1, mot2):
i = 0
while i < len(mot1) and i < len(mot2) and mot1[i] == mot2[i]:
i += 1
return (i, mot1[:i])
prefixes_communs('algorithm', 'algebra') → (3, 'alg')
prefixes_communs('matrix', 'matter') → (3, 'mat')
prefixes_communs('banana', 'pattern') → (0, '')
Écrire une fonction mots_similaires_longueur(dictionnaire, mot, delta) qui retourne la liste des mots du dictionnaire dont la longueur diffère d'au plus delta caractères de celle de mot, triée par différence de longueur croissante puis alphabétiquement.
Exemple
mots_similaires_longueur(dictionnaire, 'algorythm', 1) # 'algorythm' a 9 lettres → mots de 8, 9 ou 10 lettres
['algorithm', 'altering', 'bandana', 'character', ...]
def mots_similaires_longueur(dictionnaire, mot, delta):
cible = len(mot)
candidats = [
(abs(len(m) - cible), m)
for m in dictionnaire
if abs(len(m) - cible) <= delta
]
candidats.sort(key=lambda x: (x[0], x[1]))
return [m for _, m in candidats]
mots_similaires_longueur(dictionnaire, 'algorythm', 1) → ['altering', 'bandana', 'barrier', 'chapter', 'distance', ... 'algorithm', 'character', 'eliminate', 'elevation', ...] # triés par différence de longueur puis alphabétiquement
1.1 — Version de base
Rappeler la définition récursive de la distance de Levenshtein d(u,v) entre deux chaînes u et v. Écrire ensuite une fonction récursive naïve levenshtein_naif(u, v) sans mémoïsation.
Définition et exemples
d(u, '') = |u|
d('', v) = |v|
Si u[-1] == v[-1] : d(u[:-1], v[:-1])
Sinon : 1 + min(d(u[:-1], v),
d(u, v[:-1]),
d(u[:-1], v[:-1]))
levenshtein_naif('kitten', 'sitting')
levenshtein_naif('banana', 'bandana')
3 1
def levenshtein_naif(u, v):
# Cas de base
if len(v) == 0: return len(u)
if len(u) == 0: return len(v)
# Pas de coût si derniers caractères identiques
if u[-1] == v[-1]:
return levenshtein_naif(u[:-1], v[:-1])
# Sinon : minimum des 3 opérations
return 1 + min(
levenshtein_naif(u[:-1], v), # suppression
levenshtein_naif(u, v[:-1]), # insertion
levenshtein_naif(u[:-1], v[:-1]) # substitution
)
levenshtein_naif('kitten', 'sitting') → 3
levenshtein_naif('banana', 'bandana') → 1
Analyser la complexité temporelle de levenshtein_naif. Expliquer pourquoi cette approche est impraticable pour des mots de longueur supérieure à 15 caractères. Donner une borne sur le nombre d'appels récursifs en fonction de |u| et |v|.
Borne sur les appels récursifs
Chaque appel génère au plus 3 sous-appels, et la profondeur maximale est |u| + |v|. Le nombre d'appels est donc borné par O(3|u|+|v|).
Pourquoi impraticable ?
Pour deux mots de longueur 15, on obtient jusqu'à 330 ≈ 2 × 1014 appels. À raison de 109 opérations/seconde, cela représente plus de 2 jours de calcul. De plus, les mêmes sous-problèmes (u[:i], v[:j]) sont recalculés exponentiellement de nombreuses fois.
Nombre de sous-problèmes distincts
Il n'existe que (|u|+1) × (|v|+1) sous-problèmes distincts. La mémoïsation ou la programmation dynamique ramène la complexité à O(|u| × |v|).
Écrire une fonction levenshtein_dp(u, v) qui calcule la distance de Levenshtein par programmation dynamique (tableau 2D). Retourner la distance et le tableau dp complet.
Exemple
dist, dp = levenshtein_dp('algorithm', 'algorythm')
dist → 2
On remplit un tableau dp[i][j] = distance entre u[:i] et v[:j], ligne par ligne.
def levenshtein_dp(u, v):
n, m = len(u), len(v)
# Initialisation : tableau (n+1) x (m+1)
dp = [[0] * (m + 1) for _ in range(n + 1)]
for i in range(n + 1): dp[i][0] = i # supprimer i chars de u
for j in range(m + 1): dp[0][j] = j # insérer j chars de v
# Remplissage
for i in range(1, n + 1):
for j in range(1, m + 1):
if u[i-1] == v[j-1]:
dp[i][j] = dp[i-1][j-1] # pas de coût
else:
dp[i][j] = 1 + min(
dp[i-1][j], # suppression
dp[i][j-1], # insertion
dp[i-1][j-1] # substitution
)
return dp[n][m], dp
dist, dp = levenshtein_dp('algorithm', 'algorythm')
dist → 2
Complexité
- Temps : O(n × m) — remplissage du tableau.
- Espace : O(n × m) — stockage du tableau complet.
Donner la complexité temporelle et spatiale de levenshtein_dp. Proposer une version espace optimisé utilisant seulement deux lignes au lieu du tableau complet, et justifier pourquoi cela fonctionne.
Justification
Pour calculer dp[i][j], on n'utilise que la ligne précédente dp[i-1][*] et la case courante dp[i][j-1]. Il suffit donc de conserver deux lignes : la ligne précédente et la ligne en cours de calcul. Cela réduit l'espace de O(n×m) à O(m).
| Version | Temps | Espace |
|---|---|---|
| levenshtein_dp (tableau complet) | O(n×m) | O(n×m) |
| levenshtein_optimise (deux lignes) | O(n×m) | O(m) |
Limite
Avec seulement deux lignes, on ne peut plus reconstruire le chemin d'opérations (nécessaire pour Q11). Si la reconstruction est requise, le tableau complet est indispensable.
Écrire la fonction levenshtein_optimise(u, v) qui implémente la version espace optimisé (deux lignes uniquement). Retourner uniquement la distance finale.
Exemples
levenshtein_optimise('algorithm', 'algorythm')
levenshtein_optimise('elephant', 'elefant')
2 2
def levenshtein_optimise(u, v):
n, m = len(u), len(v)
prev = list(range(m + 1)) # ligne i-1 initialisée à [0,1,...,m]
for i in range(1, n + 1):
curr = [i] + [0] * m # curr[0] = i (supprimer i chars de u)
for j in range(1, m + 1):
if u[i-1] == v[j-1]:
curr[j] = prev[j-1]
else:
curr[j] = 1 + min(prev[j], curr[j-1], prev[j-1])
prev = curr
return prev[m]
levenshtein_optimise('algorithm', 'algorythm') → 2
levenshtein_optimise('elephant', 'elefant') → 2
1.2 — Reconstruction des opérations
Écrire une fonction reconstruire_operations(dp, u, v) qui remonte le tableau dp depuis la case dp[n][m] et retourne la liste ordonnée des opérations pour transformer u en v. Chaque opération est un tuple (type, position, caractere).
Exemple
dist, dp = levenshtein_dp('algorythm', 'algorithm')
reconstruire_operations(dp, 'algorythm', 'algorithm')
[('substitution', 5, 'y->i'),
('insertion', 8, 'h')]
On remonte le tableau en partant de (n, m) et on suit la case qui a fourni la valeur minimale. Les opérations sont collectées en sens inverse puis retournées.
def reconstruire_operations(dp, u, v):
ops = []
i, j = len(u), len(v)
while i > 0 or j > 0:
if i > 0 and j > 0 and u[i-1] == v[j-1]:
i -= 1; j -= 1 # correspondance exacte
elif i > 0 and j > 0 and dp[i][j] == dp[i-1][j-1] + 1:
ops.append(('substitution', i-1, f'{u[i-1]}->{v[j-1]}'))
i -= 1; j -= 1
elif j > 0 and dp[i][j] == dp[i][j-1] + 1:
ops.append(('insertion', i, v[j-1]))
j -= 1
else:
ops.append(('suppression', i-1, u[i-1]))
i -= 1
ops.reverse()
return ops
reconstruire_operations(dp, 'algorythm', 'algorithm')
→ [('substitution', 5, 'y->i'), ('insertion', 8, 'h')]
Écrire une fonction appliquer_operations(mot, operations) qui applique séquentiellement une liste d'opérations à un mot et retourne le mot transformé. Vérifier que le résultat est cohérent avec la distance calculée.
Exemple
appliquer_operations('algorythm',
[('substitution', 5, 'i'), ('insertion', 8, 'h')])
'algorithm'
On travaille sur une liste de caractères pour faciliter les insertions/suppressions. Un décalage offset compense le glissement des indices après chaque opération.
def appliquer_operations(mot, operations):
chars = list(mot)
offset = 0
for op, pos, car in operations:
p = pos + offset
if op == 'substitution':
chars[p] = car
elif op == 'insertion':
chars.insert(p, car)
offset += 1
elif op == 'suppression':
chars.pop(p)
offset -= 1
return ''.join(chars)
appliquer_operations('algorythm',
[('substitution', 5, 'i'), ('insertion', 8, 'h')])
→ 'algorithm'
Écrire une fonction afficher_alignement(u, v, dp) qui retourne une chaîne montrant l'alignement des deux mots, en insérant des tirets - aux positions d'insertions ou suppressions.
Exemple
afficher_alignement('algorythm', 'algorithm', dp)
algorythm- algori-thm
def afficher_alignement(u, v, dp):
align_u, align_v = [], []
i, j = len(u), len(v)
while i > 0 or j > 0:
if i > 0 and j > 0 and u[i-1] == v[j-1]:
align_u.append(u[i-1]); align_v.append(v[j-1])
i -= 1; j -= 1
elif i > 0 and j > 0 and dp[i][j] == dp[i-1][j-1] + 1:
align_u.append(u[i-1]); align_v.append(v[j-1])
i -= 1; j -= 1
elif j > 0 and dp[i][j] == dp[i][j-1] + 1:
align_u.append('-'); align_v.append(v[j-1])
j -= 1
else:
align_u.append(u[i-1]); align_v.append('-')
i -= 1
align_u.reverse(); align_v.reverse()
return ''.join(align_u) + '\n' + ''.join(align_v)
algorythm- algori-thm
2.1 — Distance de Damerau-Levenshtein
La distance de Damerau-Levenshtein ajoute une quatrième opération : la transposition de deux caractères adjacents (ab → ba coûte 1 au lieu de 2). Cette variante est plus pertinente pour les fautes de frappe (inversion de deux lettres).
Écrire une fonction damerau_levenshtein(u, v) qui calcule cette distance étendue par programmation dynamique, en ajoutant le cas de transposition : si u[i] == v[j-1] et u[i-1] == v[j], alors dp[i][j] = min(dp[i][j], dp[i-2][j-2] + 1).
Exemples
damerau_levenshtein('matirx', 'matrix')
damerau_levenshtein('algorythm', 'algorithm')
1 # transposition i↔r 2
def damerau_levenshtein(u, v):
n, m = len(u), len(v)
dp = [[0] * (m + 1) for _ in range(n + 1)]
for i in range(n + 1): dp[i][0] = i
for j in range(m + 1): dp[0][j] = j
for i in range(1, n + 1):
for j in range(1, m + 1):
cout = 0 if u[i-1] == v[j-1] else 1
dp[i][j] = min(
dp[i-1][j] + 1, # suppression
dp[i][j-1] + 1, # insertion
dp[i-1][j-1] + cout # substitution ou match
)
# Transposition de deux caractères adjacents
if i > 1 and j > 1 and u[i-1] == v[j-2] and u[i-2] == v[j-1]:
dp[i][j] = min(dp[i][j], dp[i-2][j-2] + 1)
return dp[n][m]
damerau_levenshtein('matirx', 'matrix') → 1
damerau_levenshtein('algorythm','algorithm') → 2
Écrire une fonction comparer_distances(u, v) qui retourne un dictionnaire comparant les trois distances : Levenshtein basique, Levenshtein pondéré (substitution coûte 2) et Damerau-Levenshtein.
Exemple
comparer_distances('matirx', 'matrix')
{
'levenshtein' : 2,
'levenshtein_pondere': 3,
'damerau_levenshtein': 1,
}
def comparer_distances(u, v):
return {
'levenshtein' : levenshtein_optimise(u, v),
'levenshtein_pondere': levenshtein_pondere(u, v, COUTS),
'damerau_levenshtein': damerau_levenshtein(u, v),
}
2.2 — Distance avec coûts pondérés
Écrire une fonction levenshtein_pondere(u, v, couts) qui calcule la distance de Levenshtein avec des coûts variables pour chaque type d'opération (dictionnaire COUTS).
Exemple
levenshtein_pondere('algorythm', 'algorithm', COUTS)
3 # substitution 'y'→'i' coûte 2, insertion 'h' coûte 1
def levenshtein_pondere(u, v, couts):
n, m = len(u), len(v)
c_ins = couts['insertion']
c_sup = couts['suppression']
c_sub = couts['substitution']
dp = [[0] * (m + 1) for _ in range(n + 1)]
for i in range(n + 1): dp[i][0] = i * c_sup
for j in range(m + 1): dp[0][j] = j * c_ins
for i in range(1, n + 1):
for j in range(1, m + 1):
if u[i-1] == v[j-1]:
dp[i][j] = dp[i-1][j-1]
else:
dp[i][j] = min(
dp[i-1][j] + c_sup,
dp[i][j-1] + c_ins,
dp[i-1][j-1] + c_sub
)
return dp[n][m]
levenshtein_pondere('algorythm', 'algorithm', COUTS) → 3
3.1 — Recherche par distance
Écrire une fonction corriger(mot, dictionnaire, k) qui retourne les k meilleures corrections du mot (les k mots du dictionnaire les plus proches en distance de Levenshtein), sous forme de liste de tuples (mot_correct, distance) triés par distance croissante puis alphabétiquement.
Exemple
corriger('algorythm', dictionnaire, 3)
[('algorithm', 2), ('altering', 5), ('algebra', 6)]
def corriger(mot, dictionnaire, k):
distances = [
(levenshtein_optimise(mot, m), m)
for m in dictionnaire
]
distances.sort(key=lambda x: (x[0], x[1]))
return [(m, d) for d, m in distances[:k]]
corriger('algorythm', dictionnaire, 3)
→ [('algorithm', 2), ('altering', 5), ('algebra', 6)]
Complexité
- Temps : O(D × L²) — D mots de longueur max L.
- Espace : O(D + L) — liste de résultats + tableau DP.
La fonction corriger appelle levenshtein_dp pour chaque mot du dictionnaire. Donner la complexité totale en fonction de D (taille du dictionnaire) et L (longueur maximale des mots). Proposer deux stratégies de filtrage préalable pour réduire le nombre de calculs de distance sans dégrader la qualité des suggestions.
Complexité totale
Chaque calcul levenshtein_dp(mot, m) coûte O(|mot| × |m|) ≤ O(L²). Pour D mots : O(D × L²). Avec D = 52 mots et L = 11 c'est acceptable, mais pour un vrai dictionnaire (D = 100 000, L = 20), on obtient 4 × 1010 opérations — trop lent.
Stratégie 1 — Filtrage par longueur
Ne conserver que les mots dont la longueur diffère d'au plus Δ de |mot|. Justification : si ||u| − |v|| > d, alors levenshtein(u, v) ≥ ||u| − |v||, donc ces mots ne peuvent pas être parmi les k meilleurs si on connaît déjà une borne supérieure.
Stratégie 2 — Filtrage par préfixe commun
Ne conserver que les mots partageant au moins ⌊|mot|/3⌋ caractères en commun au début. Les fautes de frappe usuelles ne modifient pas le début du mot. Un index par lettre initiale (Q1) ou par bigrammes de début permet ce filtrage en O(1).
Écrire une fonction corriger_rapide(mot, dictionnaire, k) qui implémente la stratégie de filtrage en deux étapes : (1) ne conserver que les mots dont la longueur diffère d'au plus 2 de |mot|, (2) parmi eux, ne conserver que ceux partageant le même préfixe de longueur ⌊|mot|/3⌋, puis calculer levenshtein_optimise uniquement sur les candidats restants.
Exemple
corriger_rapide('algorythm', dictionnaire, 3)
[('algorithm', 2), ...] # même résultat, calculs réduits
def corriger_rapide(mot, dictionnaire, k):
n = len(mot)
taille_prefixe = n // 3
prefixe = mot[:taille_prefixe]
# Étape 1 : filtrage par longueur (±2)
candidats = [m for m in dictionnaire if abs(len(m) - n) <= 2]
# Étape 2 : filtrage par préfixe commun
if taille_prefixe > 0:
candidats = [m for m in candidats if m[:taille_prefixe] == prefixe]
# Calcul de distance sur les candidats restants
distances = [(levenshtein_optimise(mot, m), m) for m in candidats]
distances.sort(key=lambda x: (x[0], x[1]))
return [(m, d) for d, m in distances[:k]]
3.2 — Correction gloutonne
Écrire une fonction corriger_glouton(phrase, dictionnaire) qui corrige mot par mot une phrase entière : pour chaque mot, si sa distance minimale au dictionnaire est > 0, le remplacer par la meilleure correction. Retourner la phrase corrigée et la liste des corrections effectuées.
Exemple
corriger_glouton('the algorythm and the grammer', dictionnaire)
('the algorithm and the grammar',
[('algorythm', 'algorithm', 2), ('grammer', 'grammar', 1)])
def corriger_glouton(phrase, dictionnaire):
mots = phrase.split()
mots_corriges = []
corrections = []
for mot in mots:
# Chercher la meilleure correction
meilleur = min(dictionnaire, key=lambda m: levenshtein_optimise(mot, m))
d = levenshtein_optimise(mot, meilleur)
if d > 0:
mots_corriges.append(meilleur)
corrections.append((mot, meilleur, d))
else:
mots_corriges.append(mot)
return ' '.join(mots_corriges), corrections
corriger_glouton('the algorythm and the grammer', dictionnaire)
→ ('the algorithm and the grammar',
[('algorythm', 'algorithm', 2), ('grammer', 'grammar', 1)])
La correction gloutonne mot par mot peut produire des résultats sous-optimaux. Donner un exemple concret où le contexte améliorerait la correction. Quelle approche algorithmique permettrait de corriger une phrase entière globalement ?
Exemple de sous-optimalité
Le mot "range" est correct dans le dictionnaire, mais dans la phrase "the random range", si l'utilisateur voulait écrire "the random ranger", le glouton ne corrige pas "range" (distance = 0) alors qu'un modèle contextuel pourrait détecter l'incohérence.
Autre exemple : "I study langage" — "langage" est proche de "language" (d=1) et de "damage" (d=3). Sans contexte, la correction est bonne. Mais pour "I use langage model", "language model" est le contexte attendu, et une correction contextuelle serait plus fiable.
Approche globale
Un modèle de langage n-grammes ou un décodeur par faisceau (beam search) sur le produit cartésien des corrections possibles de chaque mot maximiserait la probabilité de la phrase entière. La programmation dynamique sur la séquence de mots (algorithme de Viterbi) donne une solution exacte en O(W × D²) pour une phrase de W mots.
On organise les mots du dictionnaire dans un ABR (Arbre Binaire de Recherche) dont la clé est le mot lui-même (ordre lexicographique). Chaque nœud est représenté par une liste [mot, infos, gauche, droite], et l'arbre vide par None.
# Nœud : [mot, infos, gauche, droite] # Arbre vide : None
Écrire les fonctions inserer_mot(arbre, mot) et construire_abr_dico(dictionnaire) qui construisent l'ABR du dictionnaire.
def inserer_mot(arbre, mot):
if arbre is None:
return [mot, infos_mot(mot), None, None]
if mot < arbre[0]:
arbre[2] = inserer_mot(arbre[2], mot)
elif mot > arbre[0]:
arbre[3] = inserer_mot(arbre[3], mot)
# Si mot == arbre[0] : déjà présent, on ne réinsère pas
return arbre
def construire_abr_dico(dictionnaire):
abr = None
for mot in dictionnaire:
abr = inserer_mot(abr, mot)
return abr
abr = construire_abr_dico(dictionnaire) # Arbre construit dans l'ordre de la liste
Complexité
- Insertion : O(h) par mot, h = hauteur de l'arbre.
- Construction : O(D × h) au total.
- Dans le pire cas (liste déjà triée), h = D → O(D²). Un AVL ou un arbre rouge-noir garantirait h = O(log D).
Écrire une fonction recherche_exacte(arbre, mot) qui retourne True si le mot est dans l'ABR (accès en O(h)), et une fonction mots_intervalle(arbre, debut, fin) qui retourne tous les mots lexicographiquement compris entre debut et fin.
Exemples
recherche_exacte(abr, 'matrix') recherche_exacte(abr, 'matrixx') mots_intervalle(abr, 'la', 'mb')
True False ['language', 'lantern', 'laptop', 'lateral']
def recherche_exacte(arbre, mot):
if arbre is None:
return False
if mot == arbre[0]:
return True
if mot < arbre[0]:
return recherche_exacte(arbre[2], mot)
return recherche_exacte(arbre[3], mot)
def mots_intervalle(arbre, debut, fin):
if arbre is None:
return []
resultat = []
if arbre[0] > debut: # explorer le sous-arbre gauche
resultat += mots_intervalle(arbre[2], debut, fin)
if debut <= arbre[0] <= fin: # le nœud courant est dans l'intervalle
resultat.append(arbre[0])
if arbre[0] < fin: # explorer le sous-arbre droit
resultat += mots_intervalle(arbre[3], debut, fin)
return resultat
mots_intervalle(abr, 'la', 'mb') → ['language', 'lantern', 'laptop', 'lateral']
Écrire une fonction recherche_approx_arbre(arbre, mot, seuil) qui parcourt l'ABR en élaguant intelligemment les branches : si le préfixe commun entre le mot cherché et le nœud courant est nul et que la différence de longueur dépasse seuil + 1, on n'explore pas ce sous-arbre. Retourner la liste des mots à distance ≤ seuil.
Exemple
recherche_approx_arbre(abr, 'grammer', 2)
[('grammar', 1), ('graphic', 4)] # indicatif
def recherche_approx_arbre(arbre, mot, seuil):
if arbre is None:
return []
noeud = arbre[0]
# Élagage : si préfixe commun nul ET différence de longueur > seuil+1
long_prefixe, _ = prefixes_communs(mot, noeud)
if long_prefixe == 0 and abs(len(mot) - len(noeud)) > seuil + 1:
return []
# Calculer la distance pour ce nœud
resultat = []
d = levenshtein_optimise(mot, noeud)
if d <= seuil:
resultat.append((noeud, d))
# Explorer les deux sous-arbres
resultat += recherche_approx_arbre(arbre[2], mot, seuil)
resultat += recherche_approx_arbre(arbre[3], mot, seuil)
return sorted(resultat, key=lambda x: (x[1], x[0]))
On modélise les mots du dictionnaire comme les nœuds d'un graphe : deux mots sont reliés par une arête de poids d si leur distance de Levenshtein est ≤ 2. Ce graphe permet de naviguer entre corrections voisines et de découvrir des familles de mots proches.
Écrire une fonction construire_graphe_corrections(dictionnaire, seuil) qui construit et retourne le graphe sous forme de dictionnaire d'adjacence {mot: [(voisin, distance)]}, en ne retenant que les paires de distance ≤ seuil.
Exemple
construire_graphe_corrections(dictionnaire, 2)['grammar']
[('graphic', 2), ('grateful', 2)] # indicatif
def construire_graphe_corrections(dictionnaire, seuil):
graphe = {mot: [] for mot in dictionnaire}
n = len(dictionnaire)
for i in range(n):
for j in range(i + 1, n):
u, v = dictionnaire[i], dictionnaire[j]
d = levenshtein_optimise(u, v)
if d <= seuil:
graphe[u].append((v, d))
graphe[v].append((u, d))
# Trier les voisins par distance puis alphabétiquement
for mot in graphe:
graphe[mot].sort(key=lambda x: (x[1], x[0]))
return graphe
Complexité
- Temps : O(D² × L²) — toutes les paires de mots.
- Pour D = 52, L = 11 : environ 52² × 121 ≈ 327 000 opérations → rapide.
Écrire une fonction chemin_corrections(graphe, mot_source, mot_cible) qui retourne le chemin de distance minimale (au sens du nombre d'arêtes) entre deux mots dans le graphe, par BFS. Retourner (chemin, nb_etapes) ou ([], -1) si inaccessible.
Exemples
chemin_corrections(graphe, 'grammar', 'graphic') chemin_corrections(graphe, 'banana', 'algorithm')
(['grammar', 'graphic'], 1) ([], -1) # composantes différentes
from collections import deque
def chemin_corrections(graphe, mot_source, mot_cible):
if mot_source not in graphe or mot_cible not in graphe:
return [], -1
if mot_source == mot_cible:
return [mot_source], 0
# BFS : file de (mot_courant, chemin_parcouru)
file = deque([(mot_source, [mot_source])])
visites = {mot_source}
while file:
courant, chemin = file.popleft()
for voisin, _ in graphe[courant]:
if voisin == mot_cible:
chemin_final = chemin + [voisin]
return chemin_final, len(chemin_final) - 1
if voisin not in visites:
visites.add(voisin)
file.append((voisin, chemin + [voisin]))
return [], -1
chemin_corrections(graphe, 'grammar', 'graphic') → (['grammar', 'graphic'], 1) chemin_corrections(graphe, 'banana', 'algorithm') → ([], -1)
Écrire une fonction composantes_corrections(graphe) qui retourne la liste des composantes connexes du graphe, triées par taille décroissante. Chaque composante est une liste de mots.
def composantes_corrections(graphe):
visites = set()
composantes = []
def bfs(depart):
composante = []
file = deque([depart])
visites.add(depart)
while file:
mot = file.popleft()
composante.append(mot)
for voisin, _ in graphe[mot]:
if voisin not in visites:
visites.add(voisin)
file.append(voisin)
return sorted(composante)
for mot in graphe:
if mot not in visites:
composantes.append(bfs(mot))
composantes.sort(key=lambda c: -len(c))
return composantes
Écrire une fonction hub_lexical(graphe) qui retourne le tuple (mot, degre) du mot ayant le plus grand nombre de voisins dans le graphe des corrections.
Exemple
hub_lexical(graphe)
('pattern', 4) # indicatif
def hub_lexical(graphe):
return max(
((mot, len(voisins)) for mot, voisins in graphe.items()),
key=lambda x: x[1]
)
6.1 — Plus longue sous-séquence commune (LCS)
La Plus Longue Sous-Séquence Commune (LCS) de deux chaînes u et v est la plus longue suite de caractères apparaissant dans le même ordre dans u et v (pas nécessairement consécutifs). Écrire une fonction lcs(u, v) qui retourne la longueur de la LCS et la sous-séquence elle-même.
Récurrence et exemples
lcs[i][j] = 0 si i=0 ou j=0
lcs[i][j] = lcs[i-1][j-1] + 1 si u[i] == v[j]
lcs[i][j] = max(lcs[i-1][j],
lcs[i][j-1]) sinon
lcs('algorithm', 'alteration')
→ (5, 'alrit')
lcs('banana', 'bandana')
→ (6, 'banana')
def lcs(u, v):
n, m = len(u), len(v)
# Construction du tableau DP
dp = [[0] * (m + 1) for _ in range(n + 1)]
for i in range(1, n + 1):
for j in range(1, m + 1):
if u[i-1] == v[j-1]:
dp[i][j] = dp[i-1][j-1] + 1
else:
dp[i][j] = max(dp[i-1][j], dp[i][j-1])
# Reconstruction de la sous-séquence par remontée
seq = []
i, j = n, m
while i > 0 and j > 0:
if u[i-1] == v[j-1]:
seq.append(u[i-1])
i -= 1; j -= 1
elif dp[i-1][j] >= dp[i][j-1]:
i -= 1
else:
j -= 1
seq.reverse()
return dp[n][m], ''.join(seq)
lcs('algorithm', 'alteration') → (5, 'alrit')
lcs('banana', 'bandana') → (6, 'banana')
Complexité
- Temps : O(n × m)
- Espace : O(n × m) pour le tableau, O(min(n,m)) si optimisé.
Écrire une fonction distance_lcs(u, v) qui calcule la distance d'édition à partir de la LCS : dLCS(u, v) = |u| + |v| − 2 × lcs(u, v). Vérifier que cette formule donne une distance cohérente avec Levenshtein (elle compte insertions et suppressions, mais pas les substitutions directes).
Exemples
distance_lcs('algorythm', 'algorithm')
distance_lcs('banana', 'bandana')
3 1
def distance_lcs(u, v):
longueur_lcs, _ = lcs(u, v)
return len(u) + len(v) - 2 * longueur_lcs
# 'algorythm' (9) + 'algorithm' (9) - 2×lcs(6) = 18 - 12 = ?
# lcs('algorythm', 'algorithm') = 'algorthm' (longueur 7)
# → 9 + 9 - 14 = 4... recalculer selon résultat réel
6.2 — Alignement de séquences
L'alignement optimal de deux mots insère des tirets - dans chacun de manière à maximiser le nombre de positions où les deux mots ont le même caractère. Écrire une fonction alignement_optimal(u, v) qui retourne le tuple (u_aligne, v_aligne, score) où score est le nombre de correspondances exactes.
Exemple
alignement_optimal('algorithm', 'alteration')
('algorit--hm-', 'al-teration-', 4)
On réutilise le tableau LCS pour reconstruire l'alignement : les correspondances restent en place, les non-correspondances reçoivent un tiret dans l'une ou l'autre chaîne.
def alignement_optimal(u, v):
n, m = len(u), len(v)
# Construction du tableau LCS
dp = [[0] * (m + 1) for _ in range(n + 1)]
for i in range(1, n + 1):
for j in range(1, m + 1):
if u[i-1] == v[j-1]:
dp[i][j] = dp[i-1][j-1] + 1
else:
dp[i][j] = max(dp[i-1][j], dp[i][j-1])
# Reconstruction de l'alignement
au, av = [], []
score = 0
i, j = n, m
while i > 0 or j > 0:
if i > 0 and j > 0 and u[i-1] == v[j-1]:
au.append(u[i-1]); av.append(v[j-1])
score += 1; i -= 1; j -= 1
elif j > 0 and (i == 0 or dp[i][j-1] >= dp[i-1][j]):
au.append('-'); av.append(v[j-1]); j -= 1
else:
au.append(u[i-1]); av.append('-'); i -= 1
au.reverse(); av.reverse()
return (''.join(au), ''.join(av), score)
alignement_optimal('algorithm', 'alteration')
→ ('algorit--hm-', 'al-teration-', 4) # indicatif
On assemble toutes les fonctions développées pour produire un rapport complet d'analyse de requête et un bilan global du correcteur sur l'ensemble des mots mal orthographiés.
Écrire une fonction analyser_requete(mot, dictionnaire, graphe, abr, k) qui analyse complètement une requête utilisateur et retourne un rapport dictionnaire complet : présence dans le dictionnaire, infos morphologiques, corrections, chemin dans le graphe, LCS et alignement avec la meilleure correction.
Exemple de rapport
analyser_requete('algorythm', dictionnaire, graphe, abr, 3)
{
'mot_saisi' : 'algorythm',
'dans_dictionnaire' : False,
'infos' : ('algorythm', 9, 3, 6, 'a', 'm'),
'corrections_dp' : [('algorithm',2),('altering',5),('algebra',6)],
'correction_damerau': [('algorithm',2),...],
'chemin_graphe' : (['algorithm','algebra'], 1),
'lcs_avec_meilleur' : (7, 'algori m'),
'alignement' : ('algorythm', 'algorithm-', 7),
'suggestion_finale' : 'algorithm',
}
def analyser_requete(mot, dictionnaire, graphe, abr, k):
corrections = corriger(mot, dictionnaire, k)
meilleur = corrections[0][0] if corrections else mot
# Chemin dans le graphe (depuis la meilleure correction)
chemin = ([], -1)
if meilleur in graphe and len(graphe[meilleur]) > 0:
voisin = graphe[meilleur][0][0]
chemin = chemin_corrections(graphe, meilleur, voisin)
lcs_res = lcs(mot, meilleur)
au, av, sc = alignement_optimal(mot, meilleur)
return {
'mot_saisi' : mot,
'dans_dictionnaire' : recherche_exacte(abr, mot),
'infos' : infos_mot(mot),
'mots_meme_longueur': mots_similaires_longueur(dictionnaire, mot, 0),
'corrections_dp' : corrections,
'correction_damerau': [(m, damerau_levenshtein(mot, m))
for m, _ in corrections[:k]],
'chemin_graphe' : chemin,
'lcs_avec_meilleur' : lcs_res,
'alignement' : (au, av, sc),
'suggestion_finale' : meilleur,
}
Écrire une fonction rapport_correcteur(requetes, dictionnaire, graphe, abr) qui traite toutes les requêtes et produit le rapport global du correcteur : statistiques générales, mot le plus difficile à corriger, mot le plus simple, détail de toutes les corrections, composante principale et hub lexical.
Rapport global
rapport_correcteur(requetes, dictionnaire, graphe, abr)
{
'nb_requetes' : 10,
'taux_correction_reussie' : 1.0,
'distance_moyenne' : 2.1,
'mot_plus_difficile' : ('laanguage', 'language', 3),
'mot_plus_simple' : ('randon', 'random', 1),
'corrections': {
'algorythm' : ('algorithm', 2),
'bananaa' : ('banana', 1),
...
},
'hub_lexical' : ('pattern', 4),
'description' : "Correcteur analysé sur 10 requêtes..."
}
def rapport_correcteur(requetes, dictionnaire, graphe, abr):
corrections = {}
for mot in requetes:
res = corriger(mot, dictionnaire, 1)
if res:
corrections[mot] = res[0] # (meilleur_mot, distance)
# Statistiques
nb = len(requetes)
nb_corriges = sum(1 for _, (_, d) in corrections.items() if d > 0)
distances = [d for _, (_, d) in corrections.items()]
dist_moy = sum(distances) / len(distances) if distances else 0
plus_difficile = max(corrections.items(), key=lambda x: x[1][1])
plus_simple = min(corrections.items(), key=lambda x: x[1][1])
composantes = composantes_corrections(graphe)
hub = hub_lexical(graphe)
meilleur_corr = plus_simple[0]
desc = (f"Correcteur analysé sur {nb} requêtes. "
f"Distance moyenne : {dist_moy:.1f}. "
f"Meilleure correction : '{meilleur_corr}'"
f"->'{corrections[meilleur_corr][0]}' "
f"(d={corrections[meilleur_corr][1]}).")
return {
'nb_requetes' : nb,
'nb_mots_incorrects' : nb_corriges,
'taux_correction_reussie' : nb_corriges / nb if nb > 0 else 0,
'distance_moyenne' : round(dist_moy, 2),
'mot_plus_difficile' : (plus_difficile[0],
plus_difficile[1][0],
plus_difficile[1][1]),
'mot_plus_simple' : (plus_simple[0],
plus_simple[1][0],
plus_simple[1][1]),
'corrections' : corrections,
'composante_principale' : composantes[0] if composantes else [],
'hub_lexical' : hub,
'description' : desc,
}
rapport_correcteur(requetes, dictionnaire, graphe, abr)
→ {
'nb_requetes' : 10,
'taux_correction_reussie' : 1.0,
'distance_moyenne' : 1.6,
'mot_plus_difficile' : ('laanguage', 'language', 3),
'mot_plus_simple' : ('randon', 'random', 1),
'hub_lexical' : ('pattern', 4),
...
}
Bilan général du problème
| Partie | Thème | Complexité clé |
|---|---|---|
| 0 | Structures Python | O(D log D) |
| 1.1 | Levenshtein DP | O(n × m) |
| 1.2 | Reconstruction | O(n + m) |
| 2 | Damerau, pondéré | O(n × m) |
| 3 | Correction, filtrage | O(D × L²) |
| 4 | ABR indexation | O(D × h) |
| 5 | Graphe + BFS | O(D² × L²) |
| 6 | LCS, alignement | O(n × m) |
| 7 | Intégration | O(D × L²) |
Discussion (0)
Soyez le premier à laisser un commentaire !
Laisser un commentaire
Votre commentaire sera visible après modération.