Arithmetic Coding
Arithmetische Codierung bildet die gesamte Nachricht auf eine reelle Zahl in [0,1) ab, mit endlicher Präzision dargestellt, Kompressionsrate nähert sich beliebig der Quellenentropie.
Zweck
Erreicht höhere Kompressionsrate als Huffman bei bekannter Symbolverteilung (insbesondere wenn ein Symbol Wahrscheinlichkeit nahe 1 hat).
Mechanismus
Anfangsintervall [0,1); jedes Symbol unterteilt aktuelles Intervall in Teilintervalle nach Wahrscheinlichkeit und wählt das entsprechende; schließlich wird Binärdarstellung einer Zahl im Intervall ausgegeben. Endliche Präzision nutzt ganzzahlige Intervalle und Renormalisierung.
Anwendungsfälle
- JPEG 2000-Entropie-Codierung
- PPM-Backend
- Textkompression mit hoher Rate