// Codificação Levenshtein - código universal recursivo com optimalidade assintótica
Codifica recursivamente o comprimento do comprimento até chegar a 0.
Aproxima-se do mínimo teórico para inteiros grandes.
Funciona para qualquer inteiro não negativo sem parâmetros extras.
A codificação Levenshtein (também chamada de código Levenstein ou L*) codifica recursivamente o comprimento em bits de um número. Para um inteiro n com comprimento binário N: codifica-se recursivamente C(N-1), adiciona-se '1' e em seguida os bits de n sem o primeiro bit 1. A recursão termina em 0. Isso produz códigos assintoticamente ideais.
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') Estrutura 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'
A codificação Levenshtein (não confundir com a distância de Levenshtein) é um código universal que codifica recursivamente o comprimento dos inteiros. Desenvolvido por Vladimir Levenshtein, é assintoticamente ideal para inteiros grandes.
O código codifica recursivamente o comprimento em bits menos um. Para codificar n com N bits, primeiro codificamos (N-1), depois adicionamos '1' e, em seguida, os últimos (N-1) bits de n. A recursão termina em 0, que é codificado como '0'.
A codificação Levenshtein é assintoticamente ideal como Elias Omega, mas usa uma estrutura recursiva diferente. É mais complexa que Elias Gamma/Delta, mas alcança melhor compressão para inteiros muito grandes.
A codificação Levenshtein é principalmente de interesse teórico em teoria da informação e complexidade de Kolmogorov. Raramente é usada na prática, mas demonstra princípios importantes de codificação universal ótima.