> elias | gamma | universal <
// Elias Gamma – universel kode for positive heltal uden parametre
Universel kode
Virker for alle positive heltal uden parametre.
Præfiksfri
Ingen kode er præfiks for en anden, så dekodning er entydig.
Asymptotisk optimal
Nærmer sig optimal komprimering for visse fordelinger.
>> teknisk info
Sådan fungerer Elias Gamma:
Elias Gamma koder et positivt heltal n ved: 1) Find N = ⌊log₂(n)⌋, 2) Skriv N nuller som en unær kode, 3) Tilføj den binære repræsentation af n (som har N+1 bit). Resultatet er en kode på (2N+1) bit.
Kodningseksempler:
n=1: log₂(1)=0 Kode: 1 (ingen nuller + "1") n=2: log₂(2)=1 Kode: 010 (én nul + "10") n=5: log₂(5)=2 Kode: 00101 (to nuller + "101") n=10: log₂(10)=3 Kode: 0001010 (tre nuller + "1010") Længdeformel: 2⌊log₂(n)⌋ + 1
Hvorfor bruge Elias Gamma:
- >Ingen parametre krævet
- >Simpel implementering
- >God til små heltal
- >Universel kodeskema
- >Vigtig i informations- og kompressionsteori
>> ofte stillede spørgsmål
Hvad er Elias Gamma‑kodning?
Elias Gamma er en universel kode for positive heltal udviklet af Peter Elias. Hvert tal kodes med længden af dets binære repræsentation i unær form, efterfulgt af selve binærtallet. Den kaldes "universel", fordi den virker uden at kende fordelingen af dataene.
Hvornår er Elias Gamma effektiv?
Elias Gamma er mest effektiv til heltal, der følger en potenslovsfordeling (P(n) ∝ n^-2). Den bruger cirka 2log₂(n)+1 bit, hvilket er godt til små værdier, men mindre effektivt for store tal.
Gamma vs. Delta vs. Omega?
Elias Gamma bruger 2log₂(n)+1 bit. Delta forbedrer dette til log₂(n)+2log₂(log₂(n)+1)+1 bit, og Omega giver yderligere forbedringer for meget store tal. Gamma er den simpleste, Delta er bedre til mellemstore værdier, og Omega egner sig til meget store tal.
Hvor bruges Elias‑koder?
Elias‑koder bruges i informationsteori, forskning i datakomprimering og nogle specialiserede komprimeringsalgoritmer. De er vigtige teoretisk som universelle koder, men mindre udbredte i praksis end f.eks. Huffman‑ eller aritmetisk kodning.