[Base64.sh]

no v
en fr de es pt it nl ru ja ko zh tw ar hi pl tr sv da no

kode | dekode | komprimer

> levenshtein | rekursiv | optimal <

// Levenshtein-koding – rekursiv universell kode med asymptotisk optimalitet

0 tegn
0 tegn

>> funksjoner

[RECURSIVE]

Rekursiv struktur

Koder lengden av lengden rekursivt til den nĂĽr 0.

[OPTIMAL]

Asymptotisk optimal

NĂŚrmer seg det teoretiske minimumet for store tall.

[UNIVERSAL]

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.