// Codage Levenshtein - code universel récursif avec optimalité asymptotique
Encode récursivement la longueur de la longueur jusqu'à atteindre 0.
Se rapproche du minimum théorique pour de grands entiers.
Fonctionne pour tout entier naturel sans paramètre supplémentaire.
Le codage Levenshtein (aussi appelé code Levenstein ou L*) encode récursivement la longueur binaire d'un nombre. Pour un entier n de longueur binaire N : on encode récursivement C(N-1), on ajoute '1', puis on ajoute n sans son premier bit à 1. La récursion s'arrête à 0. Cela produit des codes asymptotiquement optimaux.
0 → 0 1 → 10 (C(0) + 1 + '') 2 → 110 (C(1) + 1 + '0') 3 → 111 (C(1) + 1 + '1') 4 → 11000 (C(2) + 1 + '00') 5 → 11001 (C(2) + 1 + '01') Structure récursive : C(0) = '0' C(1) = C(0) + 1 = '01' → '1' C(2) = C(1) + 1 + '0' = '110' C(3) = C(1) + 1 + '1' = '111'
Le codage Levenshtein (à ne pas confondre avec la distance de Levenshtein) est un code universel qui encode récursivement la longueur des entiers. Développé par Vladimir Levenshtein, il est asymptotiquement optimal pour les grands entiers.
Le code encode récursivement la longueur en bits moins un. Pour encoder n avec N bits, on encode d'abord (N-1), puis on ajoute '1' et enfin les (N-1) bits de poids faible de n. La récursion se termine à 0, qui est encodé en '0'.
Le codage Levenshtein est asymptotiquement optimal comme Elias Omega, mais utilise une structure récursive différente. Il est plus complexe que Elias Gamma/Delta, mais offre une meilleure compression pour des entiers très grands.
Le codage Levenshtein est principalement d'intérêt théorique en théorie de l'information et en complexité de Kolmogorov. Il est rarement utilisé en pratique, mais illustre des principes importants de codage universel optimal.