La distance de Levenshtein
Évoquer la distance qui sépare deux nombres consiste souvent à calculer leur différence absolue : ce qui écarte ainsi 800 de 7 vaudrait 793. C’est vrai dans le contexte d’une arithmétique en base 10, mais on peut voir les choses autrement. La distance entre Wissant (sur la côte d’Opale, dans le Pas-de-Calais) et Sète (au bord de la Méditerranée, dans l’Hérault), par exemple, est de 847 km à vol d’oiseau et de 1 037 km par la route. Quant à la distance de Levenshtein (voir article « Codes correcteurs : garder les erreurs à distance ») entre ces deux communes, elle est beaucoup plus petite et ne vaut que 6. Voici en effet le plus court chemin qui mène de l’une à l’autre en choisissant à chaque étape parmi les opérations de remplacement, de suppression ou d’ajout d’un caractère : WISSANT, ISSANT, SSANT, SANT, SENT, SÈT, SÈTE.
Amusons-nous avec la distance de Levenshtein DL et les nombres écrits en toutes lettres. Déjà, DL(DISTANCE, LEVENSHTEIN) = 10 (assurez-vous-en !). Ensuite, DL(LEVENSHTEIN, DIX) = 10 également. Puis DL(DIX, DIX) = 0, mais DL(DIX, ZÉRO) = 4. Une bien étrange arithmétique…
En fait, l’itération du procédé boucle rapidement. Reprenons depuis le début en décidant que chaque nombre indique la distance de Levenshtein qui sépare les deux termes écrits avant lui. On trouve alors :
DISTANCE, LEVENSHTEIN, DIX, DIX, ZÉRO, QUATRE, CINQ, SIX, TROIS, QUATRE, SIX, SIX, ZÉRO, QUATRE. Puis ce dernier QUATRE ramène à CINQ car on a déjà rencontré les deux termes consécutifs ZÉRO, QUATRE, et le processus boucle.
Quand on commence l’itération par ZÉRO, UN, on boucle rapidement aussi : ZÉRO, UN, QUATRE, CINQ, SIX, TROIS, QUATRE, QUATRE, ZÉRO, CINQ, QUATRE, SIX, SIX, ZÉRO, QUATRE, CINQ, et ce dernier terme ramène au tout premier SIX.
Quelles propriétés mathématiques saurez-vous démontrer sur DL ?
Avec la distance de Jaccard, il faut du métier…
La distance de Jaccard DJ mesure la « proximité » de deux mots, sans tenir compte de l’ordre des lettres.
La formule pour le calcul de la distance de Jaccard entre deux mots est : DJ = 1 – (nombre de lettres communes / nombre total de lettres distinctes).
Une distance de Jaccard est donc toujours comprise entre 0 et 1. Plus la distance est « proche de 0 », plus les mots sont « proches de l’anagramme ».
Par exemple, on a :
DJ(DISTANCE, JACCARD) = 1 – (Card{D, A, C} / Card{I, S, T, N, E, J, C, A, R, D}) = 1 – 3/10 = 0,7.
On est en effet loin de l’anagramme !
Là encore, quelles propriétés pourrez-vous dégager pour cette distance ?
.jpg "© 123RF / studiom1")
Suites et autodescription
L’encyclopédie en ligne des suites d’entiers (OEIS) de Neil Sloane et Simon Plouffe contient, comme son nom l’indique, beaucoup de suites de nombres entiers. Nombre d’entre elles jouent avec la notion de distance. La suite S portant la référence A346810 est l’une des plus récentes d’entre elles. Voici comment elle commence :
S = 1, 2, 10, 20, 3, 4, 7, 8, 30, 40, 107, 5, 80, 9, 6, 15, 11, 206, 19, 12, 13, 21, 111, 50, 300, 120, 131, 90, 140, 14, 210, 16, 17, 18, 25, 26, 31, 41, 29, 23, 160, 170, 180, 22, 27, 502, 51, 260, 802, 33, 1290, 24, 32, 200, 410, 270, 34, 1070, 35, 28, 37, 42, 47, 330.
Cette suite s’autodécrit : on dénombre S(n) chiffres entre le terme S(n) et la « plus proche » copie de la chaîne de caractères S(n). Ainsi y a-t-il un seul chiffre entre le premier « 1 » et le « 1 » de 10. Ce chiffre, c’est 2, et il y a deux chiffres entre 2 et le « 2 » de 20. Ce sont 1 et 0, et il y a bien dix chiffres entre 10 et le « 10 » de 107. Ce sont 2, 0, 3, 4, 7, 8, 3, 0, 4 et 0, et on dénombre vingt chiffres entre 20 et le « 20 » de 206, etc. Les nombres écrits en italique sont bien ceux qui forment, précisément, le début de S.