> levenshtein | rekursiv | optimal <
// Levenshtein-koding – rekursiv universell kode med asymptotisk optimalitet
Rekursiv struktur
Koder lengden av lengden rekursivt til den når 0.
Asymptotisk optimal
Nærmer seg det teoretiske minimumet for store tall.
Universell kode
Fungerer for alle ikke-negative heltall uten ekstra parametere.
>> teknisk informasjon
Hvordan Levenshtein-koding fungerer:
Levenshtein-koding (også kalt Levenstein- eller L*-kode) koder den binære lengden til et tall rekursivt. For et heltall n med binær lengde N: kod C(N-1) rekursivt, legg til '1', og legg deretter til n uten det ledende 1-bitet. Rekursjonen stopper ved 0. Dette gir asymptotisk optimale koder.
Kodingsprosess:
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'
Hvorfor bruke Levenshtein-koding:
- ▸Asymptotisk optimalitet
- ▸Ingen antakelser om fordelinger
- ▸Viktig i informasjonsteori
- ▸Universell kode for heltall
- ▸Svært god for veldig store tall
>> ofte stilte spørsmål
Hva er Levenshtein-koding?
Levenshtein-koding (ikke å forveksle med Levenshtein-avstand) er en universell kode som rekursivt koder lengden til heltall. Den ble utviklet av Vladimir Levenshtein og er asymptotisk optimal for store heltall.
Hvordan fungerer rekursjonen her?
Koden koder rekursivt bitlengden minus én. For å kode n med N biter koder du først (N-1), legger til '1' og legger deretter til de siste (N-1) bitene av n. Rekursjonen stopper ved 0, som kodes som '0'.
Levenshtein vs. Elias-koder?
Levenshtein-koding er asymptotisk optimal på samme måte som Elias Omega, men bruker en annen rekursiv struktur. Den er mer kompleks enn Elias Gamma/Delta, men gir bedre komprimering for svært store tall.
Hvor brukes den?
Levenshtein-koding er hovedsakelig av teoretisk interesse i informasjonsteori og Kolmogorov-kompleksitet. Den brukes sjelden i praksis, men demonstrerer viktige prinsipper for optimal universell koding.