// Levenshtein-kodning – rekursiv universell kod med asymptotisk optimalitet
Kodar längden av längden rekursivt tills den når 0.
Närmar sig det teoretiska minimumet för stora tal.
Fungerar för alla icke-negativa heltal utan extra parametrar.
Levenshtein-kodning (även kallad Levenstein- eller L*-kod) kodar bitlängden för ett tal rekursivt. För ett heltal n med binär längd N: koda C(N-1) rekursivt, lägg till '1' och lägg sedan till n utan det ledande 1-bitet. Rekursionen slutar vid 0. Detta ger asymptotiskt optimala koder.
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') Rekursiv 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-kodning (inte att förväxla med Levenshtein-avstånd) är en universell kod som rekursivt kodar längden på heltal. Den utvecklades av Vladimir Levenshtein och är asymptotiskt optimal för stora heltal.
Koden kodar rekursivt bitlängden minus ett. För att koda n med N bitar kodar du först (N-1), lägger till '1' och lägger sedan till de sista (N-1) bitarna i n. Rekursionen slutar vid 0, som kodas som '0'.
Levenshtein-kodning är asymptotiskt optimal precis som Elias Omega, men använder en annan rekursiv struktur. Den är mer komplex än Elias Gamma/Delta men ger bättre komprimering för mycket stora tal.
Levenshtein-kodning är framför allt av teoretiskt intresse inom informationsteori och Kolmogorov-komplexitet. Den används sällan i praktiken men illustrerar viktiga principer för optimal universell kodning.