// Codifica Levenshtein - codice universale ricorsivo con optimalità asintotica
Codifica ricorsivamente la lunghezza della lunghezza fino ad arrivare a 0.
Si avvicina al minimo teorico per interi molto grandi.
Funziona per qualsiasi intero non negativo senza parametri aggiuntivi.
La codifica Levenshtein (chiamata anche codice Levenstein o L*) codifica in modo ricorsivo la lunghezza in bit di un numero. Per un intero n con lunghezza binaria N: si codifica ricorsivamente C(N-1), si aggiunge '1' e poi si aggiunge n senza il bit iniziale a 1. La ricorsione termina a 0. Questo produce codici asintoticamente ottimali.
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') Struttura ricorsiva: 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 codifica Levenshtein (da non confondere con la distanza di Levenshtein) è un codice universale che codifica ricorsivamente la lunghezza degli interi. Sviluppato da Vladimir Levenshtein, è asintoticamente ottimale per interi molto grandi.
Il codice codifica ricorsivamente la lunghezza in bit meno uno. Per codificare n con N bit, si codifica prima (N-1), poi si aggiunge '1' e infine gli ultimi (N-1) bit di n. La ricorsione termina a 0, che viene codificato come '0'.
La codifica Levenshtein è asintoticamente ottimale come Elias Omega, ma utilizza una struttura ricorsiva diversa. È più complessa di Elias Gamma/Delta, ma offre una compressione migliore per interi molto grandi.
La codifica Levenshtein è principalmente di interesse teorico nella teoria dell'informazione e nella complessità di Kolmogorov. È raramente usata nella pratica, ma mostra i principi della codifica universale ottimale.