> rice | adaptacyjne | kompresja <
// Kodowanie Rice’a – adaptacyjna kompresja liczb całkowitych z regulowanym parametrem
>> funkcje
Regulowany parametr
Dostosuj k, aby zoptymalizować różne rozkłady danych.
Dane geometryczne
Optymalne dla danych o rozkładzie geometrycznym lub wykładniczym.
Szybkie kodowanie
Proste operacje dzielenia i reszty zapewniają wysoką wydajność.
>> informacje techniczne
Jak działa kodowanie Rice’a:
Kodowanie Rice’a dzieli każdą liczbę całkowitą n przez 2^k, aby uzyskać iloraz q i resztę r. Iloraz jest kodowany unarnie (q jedynek zakończonych zerem), a reszta w k bitach binarnych. Tworzy to kod o zmiennej długości, który dopasowuje się do rozkładu danych poprzez parametr k.
Przykład kodowania Rice’a (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 Większe k: mniej bitów unarnych, więcej binarnych Mniejsze k: więcej bitów unarnych, mniej binarnych
Dlaczego warto używać kodowania Rice’a?:
- ▸Dopasowuje się do rozkładu danych
- ▸Łatwe do zaimplementowania
- ▸Szybkie kodowanie i dekodowanie
- ▸Dobre dla danych z czujników
- ▸Wydajne dla małych liczb całkowitych
>> najczęstsze pytania
Czym jest kodowanie Rice’a?
Kodowanie Rice’a to metoda entropijnego kodowania o zmiennej długości, szczególnie wydajna dla rozkładów geometrycznych. Jest to szczególny przypadek kodowania Golomba, w którym dzielnik M jest ograniczony do potęg liczby 2 (M = 2^k), co umożliwia szybkie implementacje oparte na operacjach bitowych.
Jak wybrać parametr k?
Optymalna wartość k zależy od rozkładu danych. Dla danych o średniej μ przybliżenie wynosi k ≈ log₂(μ × ln(2)). Małe wartości k (0–2) sprawdzają się dla bardzo małych liczb, natomiast większe (4–8) są lepsze dla danych z większymi wartościami. Użyj funkcji analizy, aby znaleźć optymalne k dla swoich danych.
Rice vs kodowanie Golomba?
Kodowanie Rice’a jest podzbiorem kodowania Golomba, w którym M = 2^k. To ograniczenie sprawia, że Rice jest szybsze (przesunięcia bitowe zamiast dzielenia), ale czasem nieco mniej optymalne. Golomb może wybierać dowolne wartości M dla lepszej kompresji, podczas gdy Rice wymienia część efektywności na szybkość.
Gdzie stosuje się kodowanie Rice’a?
Kodowanie Rice’a jest szeroko stosowane w bezstratnej kompresji dźwięku (FLAC, ALAC), kompresji obrazów (JPEG-LS) oraz w danych z czujników o rozkładach geometrycznych. Jest szczególnie skuteczne dla małych, nieujemnych liczb całkowitych o wykładniczo malejącym prawdopodobieństwie.
// Przykład krok po kroku
| 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 |
// Przykłady kodu
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
>> Więcej pytań
P: Czym różni się kod Rice’a od kodu Golomba?
O: Kod Rice’a to szczególny przypadek kodu Golomba, w którym parametr M jest potęgą dwójki (M = 2^k). Przesunięcie bitowe i maska zastępują dzielenie, co jest bardzo szybkie.
P: Jak dobrać parametr k?
O: k powinno wynosić około log2 średniej wartości. Zbyt małe daje długie ciągi unarne, zbyt duże marnuje bity na resztę. Kodeki takie jak FLAC wybierają k dla każdego bloku.
P: Do czego nadaje się kod Rice’a?
O: Do nieujemnych liczb całkowitych o rozkładzie geometrycznym, gdzie małe wartości są znacznie częstsze. Typowo reszty predykcji w bezstratnym audio (FLAC) i obrazie (JPEG-LS).