> rice | adaptiv | komprimering <
// Rice-koding – Adaptiv heltallskompresjon med justerbar parameter
>> funksjoner
Justerbar parameter
Juster k for å optimalisere ulike datafordelinger.
Geometriske data
Optimalt for data med geometrisk eller eksponentiell fordeling.
Rask koding
Enkle divisjons- og restoperasjoner for høy ytelse.
>> teknisk info
Hvordan Rice-koding fungerer:
Rice-koding deler hvert heltall n på 2^k for å få kvotient q og rest r. Kvotienten kodes unært (q ére etterfulgt av en null), og resten kodes i k binærbiter. Dette gir en variabel lengdekode som tilpasser seg datafordelingen via k-parameteren.
Rice-kodingseksempel (k=2):
k=2, M=2^2=4 0 → q=0, r=0 → 0|00 → 000 1 → q=0, r=1 → 0|01 → 001 2 → q=0, r=2 → 0|10 → 010 3 → q=0, r=3 → 0|11 → 011 4 → q=1, r=0 → 10|00 → 1000 5 → q=1, r=1 → 10|01 → 1001 6 → q=1, r=2 → 10|10 → 1010 7 → q=1, r=3 → 10|11 → 1011 8 → q=2, r=0 → 110|00 → 11000 Større k: færre unære biter, flere binærbiter Mindre k: flere unære biter, færre binærbiter
Hvorfor bruke Rice-koding?:
- ▸Tilpasser seg datafordelingen
- ▸Enkel å implementere
- ▸Rask koding og dekoding
- ▸God for sensordata
- ▸Effektiv for små heltall
>> ofte stilte spørsmål
Hva er Rice-koding?
Rice-koding er en entropikoding med variabel lengde som er spesielt effektiv for geometriske fordelinger. Det er et spesialtilfelle av Golomb-koding der divisor M er begrenset til potenser av 2 (M = 2^k), noe som gir raske implementasjoner med bitoperasjoner.
Hvordan velger jeg k-parameteren?
Den optimale k-verdien avhenger av datafordelingen. For data med gjennomsnitt μ gjelder omtrent k ≈ log₂(μ × ln(2)). Små k (0–2) fungerer godt for veldig små tall, mens større k (4–8) er bedre for data med større verdier. Bruk analysefunksjonen for å finne optimal k for dine data.
Rice vs Golomb-koding?
Rice-koding er en undergruppe av Golomb-koding der M = 2^k. Denne begrensningen gjør Rice raskere (bit-skift i stedet for divisjon), men noen ganger litt mindre optimal. Golomb kan velge vilkårlige M-verdier for bedre kompresjon, mens Rice bytter bort litt effektivitet for hastighet.
Hvor brukes Rice-koding?
Rice-koding brukes mye i tapsfri lydkompresjon (FLAC, ALAC), bildekompresjon (JPEG-LS) og sensordata med geometriske fordelinger. Det er spesielt effektivt for små ikke-negative heltall med eksponentielt avtagende sannsynlighet.
// Gjennomregnet eksempel
| n | q | r | k=2 |
|---|---|---|---|
| 0 | 0 | 00 | 000 |
| 1 | 0 | 01 | 001 |
| 2 | 0 | 10 | 010 |
| 3 | 0 | 11 | 011 |
| 4 | 1 | 00 | 1000 |
| 5 | 1 | 01 | 1001 |
| 6 | 1 | 10 | 1010 |
| 7 | 1 | 11 | 1011 |
| 8 | 2 | 00 | 11000 |
// Kodeeksempler
Rice code with parameter k (Golomb code with M = 2^k) q = n >> k quotient, written as q ones followed by a zero r = n & (2^k - 1) remainder, written as k plain bits code = unary(q) + r k = 2, n = 9 -> q = 2, r = 01 -> 110 01 Decode: count the leading 1s (q), skip the 0, read k bits (r), n = (q << k) | r Choose k about log2(mean value): small values -> small k
>> Flere spørsmål
S: Hva er forskjellen på Rice-kode og Golomb-kode?
S: Rice-kode er et spesialtilfelle av Golomb-kode der parameteren M er en tipotens (M = 2^k). Bitskift og maske erstatter divisjonen, noe som er svært raskt.
S: Hvordan velger man parameteren k?
S: k bør være omtrent log2 av gjennomsnittet. For liten k gir lange unære følger, for stor k sløser bit på resten. Kodeker som FLAC velger k per blokk.
S: Hva egner Rice-kode seg til?
S: Ikke-negative heltall med geometrisk fordeling, der små verdier er langt vanligere. Typisk prediksjonsrester i tapsfri lyd (FLAC) og bilder (JPEG-LS).