// Levenshtein-Codierung – rekursiver universeller Code mit asymptotischer Optimalität
Kodiert die Länge der Länge rekursiv, bis 0 erreicht ist.
Nähert sich für große Ganzzahlen dem theoretischen Minimum.
Funktioniert für jede nichtnegative Ganzzahl ohne zusätzliche Parameter.
Levenshtein-Codierung (auch Levenstein- oder L*-Code genannt) kodiert rekursiv die Bitlänge einer Zahl. Für ein Integer n mit binärer Länge N: man kodiert rekursiv C(N-1), fügt eine '1' an und hängt dann n ohne das führende 1-Bit an. Die Rekursion endet bei 0. So entstehen asymptotisch optimale Codes.
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') Rekursive Struktur: 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-Codierung (nicht zu verwechseln mit der Levenshtein-Distanz) ist ein universeller Code, der rekursiv die Länge von Ganzzahlen kodiert. Er wurde von Vladimir Levenshtein entwickelt und erreicht für große Ganzzahlen asymptotische Optimalität.
Der Code kodiert rekursiv die Bitlänge minus eins. Um n mit N Bits zu kodieren, kodiert man zuerst (N-1), fügt eine '1' an und hängt dann die letzten (N-1) Bits von n an. Die Rekursion stoppt bei 0, das zu '0' kodiert wird.
Levenshtein-Codierung ist wie Elias Omega asymptotisch optimal, verwendet aber eine andere rekursive Struktur. Sie ist komplexer als Elias Gamma/Delta, erzielt aber eine bessere Kompression für sehr große Ganzzahlen.
Levenshtein-Codierung ist vor allem in der Informationstheorie und der Kolmogorov-Komplexität von theoretischem Interesse. Sie wird selten praktisch verwendet, zeigt aber wichtige Prinzipien optimaler universeller Codes.