> elias | gamma | universell <
// Elias Gamma – universell kode for positive heltall uten parametere
Universell kode
Fungerer for alle positive heltall uten ekstra parametere.
Prefiksfri
Ingen kode er prefiks for en annen, noe som gir entydig dekoding.
Asymptotisk optimal
Nærmer seg optimal kompresjon for enkelte fordelinger.
>> teknisk informasjon
Hvordan Elias Gamma fungerer:
Elias Gamma koder et positivt heltall n slik: 1) Finn N = ⌊log₂(n)⌋, 2) Skriv N nuller som en unær kode, 3) Legg til den binære representasjonen av n (med N+1 biter). Resultatet er en kode på (2N+1) biter.
Kodingseksempler:
n=1: log₂(1)=0 Kode: 1 (ingen nuller + "1") n=2: log₂(2)=1 Kode: 010 (én null + "10") n=5: log₂(5)=2 Kode: 00101 (to nuller + "101") n=10: log₂(10)=3 Kode: 0001010 (tre nuller + "1010") Lengdeformel: 2⌊log₂(n)⌋ + 1
Hvorfor bruke Elias Gamma:
- >Ingen parametere kreves
- >Enkel implementasjon
- >Bra for små heltall
- >Universelt kodeskjema
- >Viktig i informasjon‑ og kompresjonsteori
>> ofte stilte spørsmål
Hva er Elias Gamma‑koding?
Elias Gamma er en universell kode for positive heltall, utviklet av Peter Elias. Hvert tall kodes ved at bitlengden representeres i unær form, etterfulgt av selve binærrepresentasjonen. Den kalles «universell» fordi den fungerer uten kunnskap om datadistribusjonen.
Når er Elias Gamma effektiv?
Elias Gamma er mest effektiv for heltall som følger en potenslovfordeling (P(n) ∝ n^-2). Den bruker omtrent 2log₂(n)+1 biter, noe som er gunstig for små verdier, men mindre effektivt for store tall.
Gamma vs Delta vs Omega?
Elias Gamma bruker 2log₂(n)+1 biter. Delta forbedrer dette til log₂(n)+2log₂(log₂(n)+1)+1 biter, mens Omega gir bedre kompresjon for svært store tall. Gamma er enklest, Delta er bedre for mellomstore verdier, og Omega er egnet for store n.
Hvor brukes Elias‑koder?
Elias‑koder brukes i informasjonsteori, forskning på datakompresjon og enkelte spesialiserte kompresjonsalgoritmer. De er teoretisk viktige som universelle koder, men mindre vanlige i praksis enn for eksempel Huffman‑ eller aritmetisk koding.