> elias | gamma | universell <
// Elias Gamma – universell kod för positiva heltal utan parametrar
Universell kod
Fungerar för alla positiva heltal utan extra parametrar.
Prefixfri
Ingen kod är prefix till en annan, vilket ger entydig avkodning.
Asymptotiskt optimal
Närmar sig optimal komprimering för vissa sannolikhetsfördelningar.
>> teknisk information
Hur Elias Gamma fungerar:
Elias Gamma kodar ett positivt heltal n enligt: 1) Beräkna N = ⌊log₂(n)⌋, 2) Skriv N nollor som en unärkod, 3) Lägg till den binära representationen av n (med N+1 bitar). Resultatet är en kod på (2N+1) bitar.
Exempel på kodning:
n=1: log₂(1)=0 Kod: 1 (inga nollor + "1") n=2: log₂(2)=1 Kod: 010 (en nolla + "10") n=5: log₂(5)=2 Kod: 00101 (två nollor + "101") n=10: log₂(10)=3 Kod: 0001010 (tre nollor + "1010") Längdformel: 2⌊log₂(n)⌋ + 1
Varför använda Elias Gamma:
- >Inga parametrar krävs
- >Enkel implementation
- >Bra för små heltal
- >Universellt kodningsschema
- >Viktigt inom informations‑ och kompressionsteori
>> vanliga frågor
Vad är Elias Gamma‑kodning?
Elias Gamma är en universell kod för positiva heltal som utvecklades av Peter Elias. Varje tal kodas med längden på dess binärrepresentation i unär form, följt av själva binärtalet. Koden kallas "universell" eftersom den fungerar utan att känna till datafördelningen.
När är Elias Gamma effektiv?
Elias Gamma är mest effektiv för tal som följer en potenslagfördelning (P(n) ∝ n^-2). Den använder cirka 2log₂(n)+1 bitar, vilket är bra för små värden men mindre effektivt för stora n.
Gamma vs Delta vs Omega?
Elias Gamma använder 2log₂(n)+1 bitar. Delta förbättrar detta till log₂(n)+2log₂(log₂(n)+1)+1 bitar, och Omega ger ännu bättre komprimering för mycket stora tal. Gamma är enklast, Delta är bättre för medelstora värden och Omega för stora n.
Var används Elias‑koder?
Elias‑koder används inom informationsteori, forskning om datakomprimering och vissa specialiserade komprimeringsalgoritmer. De är teoretiskt viktiga som universella koder men används i praktiken mer sällan än till exempel Huffman‑ eller aritmetisk kodning.