// Levenshtein-codering - recursieve universele code met asymptotische optimaliteit
Codeert de lengte van de lengte recursief totdat 0 is bereikt.
Benadert het theoretische minimum voor grote getallen.
Werkt voor elk niet-negatief geheel getal zonder extra parameters.
Levenshtein-codering (ook wel Levenstein- of L*-code genoemd) codeert recursief de bitlengte van een getal. Voor een geheel getal n met binaire lengte N: codeer recursief C(N-1), voeg een '1' toe en voeg vervolgens n zonder zijn leidende 1-bit toe. De recursie eindigt bij 0. Dit levert asymptotisch optimale codes op.
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') Recursieve structuur: C(0) = '0' C(1) = C(0) + 1 = '01' → '1' C(2) = C(1) + 1 + '0' = '110' C(3) = C(1) + 1 + '1' = '111'
Levenshtein-codering (niet te verwarren met de Levenshtein-afstand) is een universele code die recursief de lengte van gehele getallen codeert. Ontwikkeld door Vladimir Levenshtein, en asymptotisch optimaal voor grote getallen.
De code codeert recursief de bitlengte minus één. Om n met N bits te coderen, codeer je eerst (N-1), voeg je '1' toe en daarna de laatste (N-1) bits van n. De recursie stopt bij 0, dat wordt gecodeerd als '0'.
Levenshtein-codering is net als Elias Omega asymptotisch optimaal, maar gebruikt een andere recursieve structuur. Ze is complexer dan Elias Gamma/Delta, maar biedt betere compressie voor zeer grote getallen.
Levenshtein-codering is voornamelijk van theoretisch belang in de informatietheorie en de Kolmogorov-complexiteit. In de praktijk wordt het zelden gebruikt, maar het illustreert belangrijke principes van optimale universele codering.