> golomb | optimal | komprimering <
// Golomb-koding - Optimal heltallskomprimering med fleksibel divisor
>> funksjoner
Fleksibel divisor
Velg en hvilken som helst M-verdi for maksimal komprimeringseffektivitet.
Trunkert binær
Bruker færrest mulig biter til restkoding.
Generell bruk
Fungerer for enhver fordeling av ikke-negative heltall.
>> teknisk info
Hvordan Golomb-koding fungerer
Golomb-koding deler hvert heltall n med en divisor M for å få kvotient q og rest r. Kvotienten kodes unært, og resten kodes med trunkert binær, som bruker færrest mulig biter for de M mulige verdiene. Dette gir en optimal kode for geometriske fordelinger med parameter p = 1/M.
Eksempel på Golomb-koding (M=5)
M=5, b=⌈log₂(5)⌉=3, c=2³-5=3 0 → q=0, r=0 → 0|00 → 000 (2 biter for r<3) 1 → q=0, r=1 → 0|01 → 001 (2 biter for r<3) 2 → q=0, r=2 → 0|10 → 010 (2 biter for r<3) 3 → q=0, r=3 → 0|110 → 0110 (3 biter for r≥3) 4 → q=0, r=4 → 0|111 → 0111 (3 biter for r≥3) 5 → q=1, r=0 → 10|00 → 1000 6 → q=1, r=1 → 10|01 → 1001 7 → q=1, r=2 → 10|10 → 1010 Trunkert binær: r<3 bruker 2 biter, r≥3 bruker 3 biter
Hvorfor bruke Golomb-koding
- Optimal for geometriske fordelinger
- Fleksibel M-parameter
- Minimalt antall biter
- Enkel implementasjon
- Dokumentert optimalitet
>> ofte stilte spørsmål
Hva er Golomb-koding?
Golomb-koding er en optimal, prefiksfri kode med variabel lengde for geometriske fordelinger. Heltall deles på en justerbar parameter M, kvotienten kodes unært og resten med trunkert binær, noe som gir optimal komprimering for data som følger P(n) = (1-p)^n × p.
Hvordan velger jeg M-parameteren?
Det optimale M avhenger av den geometriske parameteren p for dataene dine. For data med gjennomsnitt μ gjelder omtrent M ≈ μ + 1. For eksponentielt avtagende sannsynligheter med parameter p er optimalt M = ⌈-1/log₂(1-p)⌉. Bruk analysefunksjonen for å finne det beste M for dine data.
Hva er trunkert binærkoding?
Trunkert binærkoding minimerer antall biter når én av de M mulige verdiene kodes. Hvis M er en potens av 2 brukes standard binærkoding. Ellers bruker noen verdier ⌊log₂M⌋ biter og andre ⌈log₂M⌉ biter, noe som sikrer entydig dekoding med minimal gjennomsnittlig lengde.
Hvor brukes Golomb-koding?
Golomb-koding brukes i JPEG-LS-bildekomprimering, H.264-videokoding (som Exp-Golomb) og tapsfrie lydformater. Den er ideell for run-length-koding, restkoding etter prediksjon og alle data med geometriske eller eksponentielle fordelinger.