> golomb | optimale | kompression <
// Golomb-Codierung – Optimale Integer-Kompression mit flexiblem Divisor
>> funktionen
Flexibler Divisor
Wähle einen beliebigen M-Wert für maximale Kompressionseffizienz.
Abgeschnittenes Binärformat
Verwendet die minimale Anzahl an Bits für die Restcodierung.
Allgemeiner Einsatz
Funktioniert mit jeder Verteilung nichtnegativer Ganzzahlen.
>> technische infos
Wie die Golomb-Codierung funktioniert
Bei der Golomb-Codierung wird jede ganze Zahl n durch den Divisor M geteilt, um Quotient q und Rest r zu erhalten. Der Quotient wird unär codiert und der Rest mit abgeschnittener Binärcodierung, die nur so viele Bits wie nötig für M Werte verwendet. Dadurch entsteht ein optimaler Code für geometrische Verteilungen mit Parameter p = 1/M.
Golomb-Codierungsbeispiel (M=5)
M=5, b=⌈log₂(5)⌉=3, c=2³-5=3 0 → q=0, r=0 → 0|00 → 000 (2 Bits für r<3) 1 → q=0, r=1 → 0|01 → 001 (2 Bits für r<3) 2 → q=0, r=2 → 0|10 → 010 (2 Bits für r<3) 3 → q=0, r=3 → 0|110 → 0110 (3 Bits für r≥3) 4 → q=0, r=4 → 0|111 → 0111 (3 Bits für 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 Abgeschnittenes Binärformat: r<3 nutzt 2 Bits, r≥3 nutzt 3 Bits
Warum Golomb-Codierung verwenden
- Optimal für geometrische Verteilungen
- Flexibler M-Parameter
- Minimaler Bitverbrauch
- Einfache Implementierung
- Nachgewiesene Optimalität
>> häufig gestellte fragen
Was ist Golomb-Codierung?
Golomb-Codierung ist ein optimaler, präfixfreier Code mit variabler Länge für geometrische Verteilungen. Ganzzahlen werden durch einen einstellbaren Parameter M geteilt, der Quotient wird unär und der Rest mit abgeschnittener Binärcodierung dargestellt, was eine optimale Kompression für Daten mit P(n) = (1-p)^n × p ermöglicht.
Wie wählt man den Parameter M?
Das optimale M hängt vom geometrischen Parameter p deiner Daten ab. Für Daten mit Mittelwert μ gilt näherungsweise M ≈ μ + 1. Für exponentiell abfallende Wahrscheinlichkeiten mit Parameter p ist M = ⌈-1/log₂(1-p)⌉ optimal. Verwende die Analysefunktion, um das beste M für deine Daten zu finden.
Was ist abgeschnittene Binärcodierung?
Abgeschnittene Binärcodierung minimiert die Bitanzahl bei der Codierung eines von M möglichen Werten. Ist M eine Zweierpotenz, wird normale Binärcodierung verwendet. Andernfalls nutzen einige Werte ⌊log₂M⌋ Bits und andere ⌈log₂M⌉ Bits, wodurch eindeutige Decodierbarkeit bei minimaler mittlerer Länge gewährleistet ist.
Wo wird Golomb-Codierung eingesetzt?
Golomb-Codierung wird in der JPEG-LS-Bildkompression, in der H.264-Videocodierung (als Exp-Golomb) und in verlustfreien Audioformaten verwendet. Sie eignet sich ideal für Lauflängencodierung, Restcodierung nach Prädiktion und alle Daten mit geometrischen oder exponentiellen Verteilungen.