Range Coding
Die Range-Codierung ist die Ganzzahl-Variante der arithmetischen Codierung: Sie ersetzt Fließkommaoperationen durch eine Intervalluntergrenze und -breite, vermeidet Genauigkeitsprobleme und unterliegt weniger Patentbeschränkungen.
Zweck
Erreicht nahezu entropische Kompression mit Ganzzahlarithmetik und dient als patentfreier Ersatz für arithmetische Codierung.
Mechanismus
Verwaltet wird ein Intervall [low, low+range); pro Symbol wird das Intervall nach kumulativer Wahrscheinlichkeit unterteilt und renormalisiert, wobei feststehende oberste Bits ausgegeben werden. Mathematisch äquivalent zur arithmetischen Codierung, nur eben mit Ganzzahlintervallen statt Fließkomma.
Anwendungsfälle
- Entropiecodier-Backend von PPMd
- Allgemeine Kompressionsimplementierungen
- Patentfreier Ersatz für arithmetische Codierung