Distance minimale d'édition

Dans l'exercice vidéo, vous avez observé comment la distance d'édition minimale est utilisée pour déterminer le degré de similitude entre deux chaînes de caractères. Pour rappel, la distance d'édition minimale correspond au nombre minimal d'étapes nécessaires pour passer de chaîne A à la chaîne B, les opérations disponibles étant les suivantes :

• Insertion d'un nouveau caractère.
• Suppression d'un caractère existant.
• Remplacement d'un caractère existant.
• Transposition de deux caractères consécutifs existants.

                    Quelle est la distance d'édition minimale de «sign» à «sing», et quelle(s) opération(s) vous permet(tent) d'y parvenir ?