> rice | adaptive | compress <
// Rice-Codierung – Adaptive Ganzzahlkomprimierung mit einstellbarem Parameter
>> funktionen
Einstellbarer Parameter
Passe k an, um verschiedene Datenverteilungen optimal zu komprimieren.
Geometrische Daten
Optimal für Daten mit geometrischer oder exponentieller Verteilung.
Schnelles Codieren
Einfache Division- und Restoperationen für hohe Geschwindigkeit.
>> technische details
Wie Rice-Codierung funktioniert:
Bei der Rice-Codierung wird jede Ganzzahl n durch 2^k geteilt, um Quotient q und Rest r zu erhalten. Der Quotient wird in Unary codiert (q Einsen gefolgt von einer Null) und der Rest in k Binärbits. So entsteht ein variabler Code, der sich über den Parameter k an die Datenverteilung anpasst.
Rice-Beispiel (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 Größeres k: weniger Unary-Bits, mehr Binärbits Kleineres k: mehr Unary-Bits, weniger Binärbits
Warum Rice-Codierung verwenden?:
- ▸Passt sich der Datenverteilung an
- ▸Einfach zu implementieren
- ▸Schnelles Codieren und Dekodieren
- ▸Gut für Sensordaten
- ▸Effizient für kleine Ganzzahlen
>> häufige fragen
Was ist Rice-Codierung?
Rice-Codierung ist ein Entropie-Codierverfahren mit variabler Länge, das besonders effizient für geometrische Verteilungen ist. Es ist ein Spezialfall der Golomb-Codierung, bei dem der Divisor M auf Potenzen von 2 (M = 2^k) beschränkt ist, was schnelle Implementierungen mit Bit-Operationen ermöglicht.
Wie wähle ich den k‑Parameter?
Der optimale k-Wert hängt von der Datenverteilung ab. Für Daten mit Mittelwert μ gilt näherungsweise k ≈ log₂(μ × ln(2)). Kleine k (0–2) funktionieren gut für sehr kleine Zahlen, größere k (4–8) für größere Werte. Nutze die Analysefunktion, um das optimale k für deine Daten zu finden.
Rice vs. Golomb-Codierung?
Rice-Codierung ist ein Spezialfall der Golomb-Codierung, bei dem M = 2^k gilt. Dadurch kann Rice-Codierung schneller sein (Bit-Shift statt Division), ist aber eventuell etwas weniger optimal. Golomb kann beliebige M-Werte wählen, während Rice etwas Kompressionseffizienz gegen Geschwindigkeit tauscht.
Wo wird Rice-Codierung eingesetzt?
Rice-Codierung wird häufig in verlustfreier Audiokompression (FLAC, ALAC), Bildkompression (JPEG-LS) und Sensordaten mit geometrischer Verteilung eingesetzt. Besonders effektiv ist sie für kleine, nichtnegative Ganzzahlen mit exponentiell abnehmender Wahrscheinlichkeit.
// Durchgerechnetes Beispiel
| 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 |
// Codebeispiele
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
>> Weitere Fragen
F: Was ist der Unterschied zwischen Rice- und Golomb-Code?
A: Der Rice-Code ist der Spezialfall des Golomb-Codes, bei dem der Parameter M eine Zweierpotenz (M = 2^k) ist. Dann ersetzen Bitverschiebung und Maske die Division, was in Hardware und Software sehr schnell ist.
F: Wie wählt man den Parameter k?
A: k sollte etwa log2 des Mittelwerts der Zahlen betragen. Zu kleines k erzeugt lange Unärfolgen, zu großes k verschwendet Bits auf den Rest. Codecs wie FLAC wählen k adaptiv pro Block.
F: Wofür eignet sich der Rice-Code?
A: Für nichtnegative Ganzzahlen, die geometrisch verteilt sind, also kleine Werte viel häufiger als große. Typisch sind Prädiktionsresiduen in verlustfreier Audiokompression (FLAC) und Bildkompression (JPEG-LS).