Distance d’édition · programmation dynamique

Trouver une séquence d’édition minimale et suivre sa table de distances de préfixes cellule par cellule.

À propos de cet outil

Transformer un texte en un autre

Saisissez une source et une cible, chacune contenant 0…20 points de code Unicode bien formés. Les textes vides sont valides. Calculer affiche d’abord la distance minimale et une séquence d’édition optimale. Ouvrez Distances de préfixes pour consulter la matrice complète ; Étape l’ouvre automatiquement. Les codes Unicode sous les textes intermédiaires sont repliables. Étape démarre une nouvelle table si besoin et révèle exactement une cellule, ligne par ligne. Révéler la dernière cellule achève le résultat immédiatement. Effacer le résultat conserve les textes d’entrée ; éditer un texte ou changer l’exemple efface l’ancien résultat. Les entrées et les détails ouverts sont enregistrés localement, même les brouillons incomplets ou invalides. Recharger les restaure sans calcul ; la navigation interne conserve le résultat ou le pas courant.

Fonctionnement de la table

La ligne i signifie les i premiers points de code de la source ; la colonne j signifie les j premiers points de code de la cible. Les indices d’en-tête montrent la longueur du préfixe, suivie du dernier point de code de ce préfixe. ∅ est le préfixe vide. D[0,j] = j insertions et D[i,0] = i suppressions. Une cellule intérieure choisit le minimum de la valeur diagonale plus 0 pour une correspondance ou 1 pour un remplacement, de la valeur au-dessus plus 1 pour une suppression, et de la valeur à gauche plus 1 pour une insertion.

La cellule courante liste les candidats et marque son prédécesseur choisi. Les égalités préfèrent la diagonale, puis la suppression, puis l’insertion. Le chemin final en surbrillance relie (0,0) à la cellule bas-droite. Il sélectionne une séquence optimale déterministe ; d’autres séquences optimales peuvent exister. Échanger deux caractères voisins n’est pas une opération séparée : ab → ba a ici une distance 2.

Lire la séquence d’édition

Chaque changement listé coûte 1. Les correspondances coûtent 0 et apparaissent dans Alignement complet. Les positions commencent à 0 dans le texte immédiatement avant cette opération, mesurées en points de code. Le texte ensuite montre tout le texte courant, pas seulement son caractère changé. Pour kitten → sitting la distance minimale est 3 : remplacer k par s à la position 0 pour obtenir sitten, remplacer e par i à la position 4 pour obtenir sittin, puis insérer g à la position 6 pour obtenir sitting.

Les trous d’alignement sont étiquetés Trou. Un tiret littéral reste un caractère, montré avec U+002D, et n’est jamais utilisé pour représenter un trou. Les numéros de pas dans Alignement complet comptent aussi les correspondances.

Unicode et texte exact

Le calcul utilise des points de code, pas des unités de code UTF-16 ni des grappes de graphèmes visuels. 😀 → vide a une distance 1, tandis que 👩‍💻 contient trois points de code. é composé et e suivi de U+0301 sont des entrées distinctes. Il n’y a ni normalisation, ni trim, ni conversion de casse, ni troncature silencieuse. Les substituts UTF-16 non appariés sont rejetés.

Chaque caractère non alphanumérique a une étiquette de code U+… dans la matrice ou l’alignement. □ représente un caractère d’espace ou invisible ; son code identifie lequel. Un cercle pointillé soutient une marque combinante et ne fait pas partie du texte source. Les textes intermédiaires conservent leur espace réel ; leurs notes de code utilisent des positions à base zéro. L’isolation bidirectionnelle empêche les caractères droite-à-gauche et les contrôles de direction de réarranger les étiquettes voisines.

Sources