> golomb | optimal | komprimering <
// Golomb-kodning - Optimal heltalskomprimering med fleksibel divisor
>> funktioner
Fleksibel divisor
Vælg en vilkårlig M-værdi for maksimal komprimeringseffektivitet.
Trunkerede binære tal
Bruger det minimale antal bits til restkodning.
Generel brug
Virker for enhver fordeling af ikke-negative heltal.
>> teknisk info
Sådan fungerer Golomb-kodning
Golomb-kodning dividerer hvert heltal n med en divisor M for at få kvotienten q og resten r. Kvotienten kodes unært, og resten kodes med trunkeret binær, som bruger færrest mulige bits til de M mulige værdier. Dette giver en optimal kode til geometriske fordelinger med parameter p = 1/M.
Eksempel på Golomb-kodning (M=5)
M=5, b=⌈log₂(5)⌉=3, c=2³-5=3 0 → q=0, r=0 → 0|00 → 000 (2 bits for r<3) 1 → q=0, r=1 → 0|01 → 001 (2 bits for r<3) 2 → q=0, r=2 → 0|10 → 010 (2 bits for r<3) 3 → q=0, r=3 → 0|110 → 0110 (3 bits for r≥3) 4 → q=0, r=4 → 0|111 → 0111 (3 bits 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 Trunkeret binær: r<3 bruger 2 bits, r≥3 bruger 3 bits
Hvorfor bruge Golomb-kodning
- Optimal til geometriske fordelinger
- Fleksibel M-parameter
- Minimalt bitforbrug
- Simpel implementering
- Dokumenteret optimalitet
>> ofte stillede spørgsmål
Hvad er Golomb-kodning?
Golomb-kodning er en optimal, præfiksfri kode med variabel længde til geometriske fordelinger. Heltal divideres med en justerbar parameter M, kvotienten kodes unært og resten med trunkeret binær, hvilket giver optimal komprimering for data med P(n) = (1-p)^n × p.
Hvordan vælger jeg M-parameteren?
Det optimale M afhænger af den geometriske parameter p for dine data. For data med middelværdi μ gælder cirka M ≈ μ + 1. For eksponentielt faldende sandsynligheder med parameter p er det optimale M = ⌈-1/log₂(1-p)⌉. Brug analysefunktionen til at finde det bedste M for dine data.
Hvad er trunkeret binær kodning?
Trunkeret binær kodning minimerer antallet af bits ved kodning af en af de M mulige værdier. Hvis M er en potens af 2, bruges standard binær. Ellers bruger nogle værdier ⌊log₂M⌋ bits og andre ⌈log₂M⌉ bits, hvilket sikrer entydig dekodning med minimal gennemsnitlig længde.
Hvor bruges Golomb-kodning?
Golomb-kodning bruges i JPEG-LS-billedkomprimering, H.264-videokodning (som Exp-Golomb) og tabsfri lydformater. Den er ideel til run length-kodning, restkodning efter prediktion og alle data med geometriske eller eksponentielle fordelinger.