// Levenshtein-kodning - rekursiv universalkode med asymptotisk optimalitet
Koder længden af længden rekursivt, indtil 0 nås.
Nærmer sig det teoretiske minimum for store tal.
Virker for alle ikke-negative heltal uden ekstra parametre.
Levenshtein-kodning (også kaldet Levenstein- eller L*-kode) koder rekursivt bitlængden af et tal. For et heltal n med binær længde N: kod C(N-1) rekursivt, tilføj '1', og tilføj derefter n uden det første 1-bit. Rekursionen stopper ved 0. Dette giver asymptotisk optimale 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 (ikke at forveksle med Levenshtein-afstand) er en universel kode, der rekursivt koder længden af heltal. Den blev udviklet af Vladimir Levenshtein og er asymptotisk optimal for store heltal.
Koden koder rekursivt bitlængden minus én. For at kode n med N bits koder man først (N-1), tilføjer '1' og til sidst de sidste (N-1) bits af n. Rekursionen stopper ved 0, som kodes som '0'.
Levenshtein-kodning er asymptotisk optimal ligesom Elias Omega, men bruger en anden rekursiv struktur. Den er mere kompleks end Elias Gamma/Delta, men giver bedre kompression for meget store heltal.
Levenshtein-kodning er primært af teoretisk interesse inden for informationsteori og Kolmogorov-kompleksitet. Den bruges sjældent i praksis, men demonstrerer vigtige principper for optimal universel kodning.