// Codificación Levenshtein - código universal recursivo con optimalidad asintótica
Codifica recursivamente la longitud de la longitud hasta llegar a 0.
Se aproxima al mínimo teórico para enteros grandes.
Funciona para cualquier entero no negativo sin parámetros adicionales.
La codificación Levenshtein (también llamada código Levenstein o L*) codifica de forma recursiva la longitud en bits de un número. Para un entero n con longitud binaria N: se codifica recursivamente C(N-1), se añade '1' y luego se añaden los bits de n sin el 1 inicial. La recursión termina en 0. Esto produce códigos asintóticamente óptimos.
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') Estructura recursiva: C(0) = '0' C(1) = C(0) + 1 = '01' → '1' C(2) = C(1) + 1 + '0' = '110' C(3) = C(1) + 1 + '1' = '111'
La codificación Levenshtein (no confundir con la distancia de Levenshtein) es un código universal que codifica recursivamente la longitud de los enteros. Desarrollado por Vladimir Levenshtein, es asintóticamente óptimo para enteros grandes.
El código codifica recursivamente la longitud en bits menos uno. Para codificar n con N bits, primero se codifica (N-1), luego se añade '1' y después los últimos (N-1) bits de n. La recursión termina en 0, que se codifica como '0'.
La codificación Levenshtein es asintóticamente óptima como Elias Omega, pero usa una estructura recursiva diferente. Es más compleja que Elias Gamma/Delta, pero obtiene mejor compresión para enteros muy grandes.
La codificación Levenshtein es principalmente de interés teórico en teoría de la información y complejidad de Kolmogórov. Rara vez se usa en la práctica, pero ilustra principios de codificación universal óptima.