Distance d'édition

Programmation dynamique • Cours-TP 2A

L'objectif de l'exercice est de calculer la distance d'édition (distance de Levenshtein) entre deux chaînes de caractères, c'est-à-dire le nombre minimal d'opérations (insertion, suppression, substitution) nécessaires pour transformer une chaîne en l'autre, en explorant trois approches de plus en plus optimisées.

Soit $a$ et $b$ deux chaînes de caractères. On note $| a |$ le cardinal de $a$ , c'est-à-dire le nombre de caractères de la chaîne. $a [- 1]$ désigne le dernier caractère de la chaîne $a$ . On dénote par $a [: - 1]$ la chaîne $a$ tronquée de son dernier caractère.

On suppose que :

supprimer un caractère,
insérer un caractère,
et substituer un caractère,

sont des opérations qui ont toute un coût unitaire (1). Si le caractère est identique, la substitution ne coûte rien (0).

La distance d'édition est définie par induction de la manière suivante :

d_{e} (a, b) = {\begin{matrix} \max (| a |, | b |) & si \min (| a |, | b |) = 0 \\ d_{e} (a [: - 1], b [: - 1]) & si a [- 1] = b [- 1] \\ 1 + \min {\begin{matrix} d_{e} (a [: - 1], b) \\ d_{e} (a, b [: - 1]) \\ d_{e} (a [: - 1], b [: - 1]) \end{matrix} & sinon \end{matrix}

Exemple :

1

Indice

Créer un tableau 2D de taille (len(a)+1)×(len(b)+1) et le remplir ligne par ligne en distinguant le cas caractères égaux (diagonale) du cas contraire (1 + min de trois directions adjacentes).

Programmation dynamique ascendante : Écrire une fonction impérative de(a, b) qui renvoie la distance d'édition entre les deux chaînes a et b en complétant un tableau 2D à la bonne dimension. Par exemple de("kitten", "sitting") renvoie 3.
2

Indice

Structurer la récursion sur les premiers caractères avec un cas de base sur les chaînes vides puis, sinon, renvoyer 1 + min de trois appels sur a[1:]/b, a[1:]/b[1:] et a/b[1:].

Récursion sans mémoïsation : Écrire une fonction récursive rec_de(a, b) qui renvoie la distance d'édition. Par exemple rec_de("kitten", "sitting") renvoie `3.
3

Indice

Vérifier d'abord la présence de la clé (a, b) dans le dictionnaire mem, puis comparer les derniers caractères en tronquant avec a[:-1] et b[:-1] avant d'enregistrer le résultat.

Récursion avec mémoïsation : Écrire une fonction récursive avec mémoïsation mem_de(a, b, mem) qui renvoie la distance d'édition, en utilisant le dictionnaire mem (clef : le tuple (a, b)) pour stocker et réutiliser les résultats déjà calculés. Par exemple mem_de("kitten", "sitting", {}) renvoie 3.