> rice | adaptiv | komprimer <
// Rice-kodning – Adaptiv heltalskomprimering med justerbar parameter
>> funktioner
Justerbar parameter
Justér k for at optimere forskellige datadistributioner.
Geometriske data
Optimal til data med geometrisk eller eksponentiel fordeling.
Hurtig kodning
Enkle divisions- og restoperationer for høj ydeevne.
>> teknisk info
Hvordan Rice-kodning virker:
Rice-kodning deler hvert heltal n med 2^k for at få kvotient q og rest r. Kvotienten kodes unært (q ettaller efterfulgt af et nul), og resten kodes i k binære bits. Dette giver en variabel længdekode, der tilpasser sig datadistributionen via k-parameteren.
Rice-kodningseksempel (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 bits, flere binære bits Mindre k: flere unære bits, færre binære bits
Hvorfor bruge Rice-kodning?:
- ▸Tilpasser sig datadistributionen
- ▸Let at implementere
- ▸Hurtig kodning og dekodning
- ▸God til sensordata
- ▸Effektiv til små heltal
>> ofte stillede spørgsmål
Hvad er Rice-kodning?
Rice-kodning er en entropikodningsmetode med variabel længde, der er særligt effektiv til geometriske fordelinger. Det er et specialtilfælde af Golomb-kodning, hvor divisoren M er begrænset til potenser af 2 (M = 2^k), hvilket muliggør hurtige implementationer med bitoperationer.
Hvordan vælger jeg k-parameteren?
Den optimale k-værdi afhænger af datadistributionen. For data med middelværdi μ gælder omtrent k ≈ log₂(μ × ln(2)). Små k (0–2) fungerer godt til meget små tal, mens større k (4–8) er bedre til data med større værdier. Brug analysefunktionen til at finde det optimale k for dine data.
Rice vs Golomb-kodning?
Rice-kodning er en undergruppe af Golomb-kodning, hvor M = 2^k. Denne begrænsning gør Rice hurtigere (bitshift i stedet for division), men til tider lidt mindre optimal. Golomb kan vælge vilkårlige M-værdier for bedre komprimering, mens Rice bytter lidt effektivitet for hastighed.
Hvor bruges Rice-kodning?
Rice-kodning bruges bredt i tabsfri lydkomprimering (FLAC, ALAC), billedkomprimering (JPEG-LS) og sensordata med geometriske fordelinger. Den er især effektiv til små ikke-negative heltal med eksponentielt faldende sandsynlighed.
// Gennemregnet 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ørgsmål
S: Hvad er forskellen på Rice-kode og Golomb-kode?
S: Rice-kode er et specialtilfælde af Golomb-kode, hvor parameteren M er en topotens (M = 2^k). Bitskift og maske erstatter divisionen, hvilket er meget hurtigt.
S: Hvordan vælger man parameteren k?
S: k bør være omtrent log2 af middelværdien. For lille k giver lange unære følger, for stor k spilder bit på resten. Kodeks som FLAC vælger k pr. blok.
S: Hvad egner Rice-kode sig til?
S: Ikke-negative heltal med geometrisk fordeling, hvor små værdier er langt hyppigere. Typisk prædiktionsrester i tabsfri lyd (FLAC) og billeder (JPEG-LS).