Ein Range Coder ist eine praktische Implementierungsform der arithmetischen Kodierung, die vollständig mit Ganzzahlarithmetik arbeitet. Statt eines Intervalls [0, 1) mit Gleitkommazahlen verwaltet er ein ganzzahliges Fenster [low, low + range) über dem Zahlenraum. Dadurch vermeidet er die bei der theoretischen Intervallarithmetik wachsende Präzision und eignet sich für schnelle, ressourcenschonende Encoder und Decoder.
Wie funktioniert es?
Der Encoder hält zwei ganze Zahlen: low (Untergrenze) und range (Breite). Für jedes Symbol wird range proportional zur Symbolwahrscheinlichkeit geteilt und das Fenster auf den Teilbereich des Symbols eingeschränkt. Sobald die führenden Bytes von low und low + range übereinstimmen, sind sie stabil: Sie werden als Ausgabebytes ausgegeben, und Fenster sowie range werden nach oben skaliert (Renormalisierung). Am Ende wird der Wert im finalen Fenster als Bytefolge geschrieben. Der Decoder arbeitet spiegelbildlich und liest die Bytes nach, sobald sie zur Entscheidung nötig werden.
Die Grundidee geht auf G. Nigel Martin zurück (1979, Range Encoding); populäre Implementierungen verbreiteten sich Ende der 1990er-Jahre, als die früheren Patente auf arithmetische Kodierung die Nutzung nicht mehr blockierten. Der Rechenaufwand pro Symbol liegt bei wenigen Multiplikationen und Divisionen — deutlich geringer als bei naiven Gleitkomma-Varianten.
Einsatzgebiete
- LZMA beziehungsweise LZMA2 in 7-Zip und XZ: Kombination aus LZ77-Fenster und adaptivem binärem Range Coder
- H.264/H.265: CABAC ist eine kontextadaptive binäre Range-Coder-Variante
- Verschiedene Bild- und Audioformate als Entropiestufe nach der Transformation
Eine neuere Konkurrenz mit ähnlicher Kompressionsdichte, aber noch höherem Durchsatz sind die Asymmetric Numeral Systems (ANS), die unter anderem in Zstandard zum Einsatz kommen.
Verwandte Grundlagen: Datenkompression, verlustfreie Kompression, Huffman-Codierung.