Dieser Artikel kann für diejenigen von Interesse sein, die sich mit Datenkomprimierung beschäftigen oder einen eigenen Archivierer schreiben möchten.
Der Artikel basiert hauptsächlich auf den Materialien des
Blogs , das von Fabian Giesen gepflegt wird.
Einführung
Die Entropiecodierungsmethode rANS (
r ange + ANS) ist das Geschwister des FSE-Algorithmus, über den ich
zuvor geschrieben habe . Die Abkürzung ANS bedeutet
Asymmetric Numeral Systems , und der Wortbereich im Namen weist auf die Ähnlichkeit dieser Methode mit der
Intervallcodierung hin . Der Autor von rANS ist
Yarek Duda .
Mit der rANS-Methode können Sie bei sehr hoher Geschwindigkeit eine nahezu optimale Komprimierung erzielen. Dabei ist rANS nicht schlechter als FSE, was nicht verwunderlich ist: Beide Algorithmen basieren auf einer gemeinsamen theoretischen Basis. Der rANS-Algorithmus ist jedoch viel einfacher zu implementieren als FSE.
Zuerst wird es einen langen „theoretischen“ Teil geben, und dann werden wir versuchen, einen einfachen Archivierer zu schreiben.
Methodenbeschreibung
Die Funktionsweise des Algorithmus wird durch die folgenden einfachen Formeln bestimmt:
Codierung: C(s,x): x := (x / Fs) * M + Bs + (x % Fs)Decodierung: D(x): s = sym[x % M], x := Fs * (x / M) + (x % M) - BsLassen Sie uns sie im Detail analysieren.
Die Codierungsfunktion
C (s, x) empfängt das zu codierende Zeichen
s (sei es eine ganze Zahl) und den aktuellen Zustand des Codierers
x (auch eine ganze Zahl).
F s - Symbolfrequenz
s . Die obige Division durch Fs ist eine ganze Zahl.
M ist die Summe der Häufigkeiten aller Symbole des Alphabets (
M = Σ
F s ).
In s der Beginn des Intervalls, das dem codierten Zeichen entspricht (in der folgenden Abbildung).
x %
Fs ist der Rest der Division von
x durch
F s .
Das Funktionsprinzip ist das gleiche wie bei der
arithmetischen Codierung : Wir nehmen das Segment
[ 0,
M) und teilen es in Teile, so dass jedes Zeichen
s einem Intervall entspricht, dessen Größe der Häufigkeit des Zeichens
F s entspricht . Das Auftreten des Wertes
x% M in einem beliebigen Intervall bezeichnet die Codierung des entsprechenden Symbols.
Initialisieren Sie zu Beginn der Codierung
x mit einem beliebigen geeigneten Wert und berechnen Sie dann die Funktion
C (s, x) für alle codierten Zeichen nacheinander.
Jede Berechnung der Funktion
C (s, x) erhöht den Wert von
x . Wenn es zu groß wird, sollten Sie die Daten in der Ausgabe sichern:
while (x >= x_max) { writeToStream(x % b);
Dieser Schritt wird als
Renormierung bezeichnet . Danach können Sie mit dem Codieren fortfahren.
Oben im Code erschienen neue Konstanten:
x_max und
b .
Theoretisch hängen die Zahlen
M ,
b und
x_max durch einige Beziehungen zusammen. In der Praxis ist es jedoch am effektivsten, die folgenden Werte zu verwenden, wenn der Zustand uint32 für den Zustand
x :
M = 2 ^
k , wobei
k <= 16 ist
b = 2 ^ 16 (halb so groß wie uint32)
Die Wahl von
M = 2 ^
k beruht auf der Tatsache, dass es in der Decodierungsfunktion eine Division durch
M gibt, so dass die Division mit dem Rest durch bitweise Operationen ersetzt werden kann.
Der Wert von
k wird aus den folgenden Überlegungen ausgewählt: Je größer er ist, desto höher ist die Genauigkeit von
F s und desto effizienter ist die Komprimierung. In diesem Fall muss ein gewisser Aufwand für das Speichern der Frequenztabelle berücksichtigt werden, sodass es sich nicht immer lohnt, die Maximalwerte von
k zu verwenden .
Der Wert von
x_max sollte so sein, dass kein Überlauf auftritt. Basierend auf der Codierungsfunktion erhalten wir
x <
uint32_max *
Fs /
M oder einen etwas anderen Weg:
x_max <= (
b *
L ) *
Fs /
M , wobei
L <=
uint32_max /
b . Im realen Code hat die Bedingung die Form x / b> = L / M * Fs, um einen Überlauf in den Berechnungen zu vermeiden.
Der Wert
b = 2 ^ 16 (halb so groß wie uint32) wird so gewählt, dass, wenn
x x_max überschreitet, eine Division durch
b ausreicht, um weiterzuarbeiten. Infolgedessen endet die
while nach der ersten Iteration, was bedeutet, dass sie durch ein einfaches
if .
Infolgedessen hat die Codierungsfunktion die folgende Form:
typedef uint32_t RansState; constexpr uint32_t RANS_L = 1u << 16; constexpr uint32_t k = 10;
Am Ende der Codierung müssen Sie den Wert von
x speichern, da die Decodierung von dort aus beginnt. Und ja, wir werden vom Ende bis zum Anfang dekodieren, dh vom letzten codierten Zeichen bis zum ersten. (In einem Artikel über
FSE wird dieser Punkt ausreichend ausführlich erläutert.)
Ich möchte etwas näher darauf eingehen, wie die Codierungsformel funktioniert.
x := (x / Fs) * M + Bs + (x % Fs)
Nach der Berechnung von (
x / Fs) * M enthält die Variable
x die
k niedrigstwertigen Bits (denken Sie daran, dass
M = 2 ^
k ist ). Das Hinzufügen von
+ Bs + (x % Fs) schreibt im Wesentlichen einen bestimmten Wert aus dem
Intervall des Zeichens
s in diese Bits, da
Bs der Beginn des Intervalls ist und (x% Fs) die Zahl innerhalb dieses Intervalls ist (die Größe des Intervalls ist Fs). Somit können wir beim Decodieren das codierte Zeichen durch das Intervall bestimmen, in das es fällt (x% M).
DekodierungFahren wir mit der Dekodierungsfunktion fort.
D(x): s = sym[x % M], x := Fs * (x / M) + (x % M) - Bs
Wie wir oben bereits verstanden haben, wird das gewünschte Zeichen
s durch den Rest der Division
x %
M bestimmt. In welchem Intervall der Wert (x% M) gefallen ist, wurde ein solches Zeichen codiert.
Zuvor haben wir speziell M = 2 ^ k definiert, um die Decodierungsfunktion zu vereinfachen. Es endete so:
uint32_t RansDecode(RansState& x, RansInBuf& in) { assert(x >= RANS_L);
Die Decodierung beginnt mit demselben
x , das am Ende der Codierung erhalten wurde. Dazu muss es zusammen mit den codierten Daten gespeichert werden.
Am Ende der Decodierung sollte der Zustand des Decodierers
x genau dem der Codierung entsprechen. Im Allgemeinen muss
x bei jedem Schritt genau das gleiche sein wie beim entsprechenden Codierungsschritt. Diese Tatsache hilft beim Debuggen sehr.
Wie Sie sehen können, funktioniert die Dekodierung schneller als die Kodierung, da keine Teilungsoperationen vorhanden sind.
Der schwierigste Moment in der Decodierungsfunktion ist die Methode zur Bestimmung, in welchem Intervall der Wert gefallen ist (x% M).
Die einfachste und schnellste Methode ist die Verwendung der
sym [] -Tabelle, Größe
M. In diesem Fall erhalten wir eine Tabelle mit der gleichen Größe wie im FSE-Algorithmus, mit dem Unterschied, dass in rANS die Tabelle nicht „verwechselt“ wird, die Zeichen in Ordnung sind und eine solche Tabelle viel einfacher zu erstellen ist.
Der Hauptnachteil dieses Ansatzes ist die Größe der
Sym- Tabelle, die mit zunehmendem
k exponentiell wächst.
Alias-Methode
Eine
Alias-Methode wurde erfunden, um den Treffer in einem Intervall effizienter zu bestimmen. Mit dieser Methode können Sie das gewünschte Intervall anhand kleiner Tabellen schnell bestimmen - anhand der Anzahl der Zeichen im Alphabet.
Eine lange und ausführliche Erklärung finden Sie hier:
Pfeile, Würfel und Münzen . Ich werde das Wesentliche der Methode kurz beschreiben: Wir nehmen ein Stück des längsten Intervalls und hängen es an das kürzeste Intervall an, sodass die Gesamtgröße genau
M /
N beträgt (wobei
N die Anzahl der Zeichen im Alphabet ist). Es stellt sich heraus, dass Sie, wenn Sie dies nacheinander tun, immer
N Paare der Größe
M /
N erhalten.Natürlich muss
M durch
N teilbar sein
. Und wenn wir uns daran erinnern, dass wir
M = 2 ^
k haben , dann stellt sich heraus, dass die Größe des Alphabets auch eine Zweierpotenz ist. Dies ist kein Problem, da Sie das Alphabet jederzeit mit nicht verwendeten Zeichen mit einer Häufigkeit von Null auf die gewünschte Größe ergänzen können.
Die Tatsache, dass das Zeichenintervall in mehrere Teile unterteilt ist, erschwert den Codierungsvorgang ein wenig, aber nicht viel. Wenn Sie sich an die FSE erinnern, waren die Intervalle dort im Allgemeinen über den gesamten Bereich verteilt, als hätte ein verrückter Mixer daran gearbeitet, und nichts hat funktioniert =)
Das gewünschte Intervall zu bestimmen ist nicht schwierig: Teilen Sie
x durch
N und fallen Sie in eines der Paare. Als nächstes vergleichen wir den Rest der Division von
x% N mit der Grenze zwischen den Segmenten in einem Paar und fallen entweder in ein Intervall oder in ein anderes.
Wir versuchen es in der Praxis
Wir werden den Code des
fertigen Beispiels verwenden .
Wir nehmen die Daten zur Komprimierung aus der Datei:
size_t in_size; uint8_t* in_bytes = read_file("book1", &in_size);
1. Zuerst müssen Sie sich für
die Datenstruktur entscheiden.
Wir verwenden die einfachste Option: Wir codieren ein Byte mit dem Alphabet [0 ... 255].
2. Im nächsten Schritt bestimmen Sie die
Häufigkeit der Alphabetzeichen:
(Funktion
stats.count_freqs )
for (size_t i = 0; i < in_size; i++) { freqs[in_bytes[i]]++; }
3. Wir haben also Symbolfrequenzen, aber jetzt müssen wir sie
normalisieren , dh proportional verringern (oder erhöhen), so dass wir insgesamt M = 2 ^ k erhalten. Dies ist keine so einfache Aufgabe, wie es scheint, daher verwenden wir eine vorgefertigte Funktion:
stats.normalize_freqs(...);
Übrigens müssen Sie den Wert von
k bestimmen. Da unser Alphabet aus 256 Zeichen besteht, sollten
k weniger als 8 nicht genommen werden. Nehmen Sie zuerst das Maximum - 16 und versuchen Sie es später mit anderen Werten.
4. Erstellen Sie eine
Alias-Tabelle :
stats.make_alias_table();
5. Wir codieren
vom Ende , um dann in der normalen Reihenfolge zu decodieren.
RansState rans;
Ferner decodiert das Referenzbeispiel komprimierte Daten unter Verwendung vorgefertigter Statistiken. Im wirklichen Leben müssen Sie zum Dekodieren eine Tabelle mit Frequenzen (Statistiken) zusammen mit komprimierten Daten speichern. Im einfachsten Fall müssen Sie N * k Bits dafür ausgeben.
Schauen wir uns, wie oben versprochen, die Komprimierungsergebnisse für verschiedene Werte von k an (im Code ist es
prob_bits ), wobei wir die Zunahme der Größe aufgrund der Aufzeichnung der Häufigkeitstabelle berücksichtigen:
(
Original book1 Dateigröße : 768771)
k = 16: 435059 + 512 = 435571 Bytes
k =
15 : 435078 + 480 =
435558 Bytes
k = 14: 435113 + 448 = 435561 Bytes
k = 13: 435239 + 416 = 435655 Bytes
k = 12: 435603 + 384 = 435987 Bytes
k = 11: 436530 + 352 = 436882 Bytes
k = 10: 440895 + 320 = 441215 Bytes
k = 9: 453418 + 288 = 453706 Bytes
k = 8: 473126 + 256 = 473382 Bytes
Sie können sehen, dass die Komprimierung umso besser ist, je höher k ist. Ab einem bestimmten Punkt (bei k = 16) überwiegt jedoch der Overhead der Frequenztabelle die Vorteile einer Erhöhung der Genauigkeit. Wenn Sie eine kleinere Datei komprimieren, wird dieser Effekt auf kleinerem k angezeigt.
Sie müssen auch ein paar Worte über den Trick "Interleaved RANS" sagen, der
in diesem Beispiel zusätzlich implementiert wird. Die Idee ist, dass die abwechselnde Verwendung von zwei unabhängigen Zustandsvariablen die Prozessorparallelität besser nutzt. Dadurch ist die Dekodierung noch schneller.
Abschließend möchte ich darauf hinweisen, dass die ausgewählte Dateikomprimierungsmethode zu einfach ist. Die Merkmale der Daten werden nicht berücksichtigt, weshalb die Komprimierung bei weitem nicht optimal ist. Wenn Sie sich die Eingabe genau ansehen, können Sie feststellen, dass einige
Buchstabenkombinationen häufiger als andere sind und einige überhaupt nicht vorkommen. Durch diese Tatsache kann die Komprimierung erheblich verbessert werden. Dies ist jedoch ein Thema für einen separaten Artikel.
Nachwort
Warum einen eigenen Archivierer schreiben, wenn es viele bewährte Dienstprogramme gibt? Die Antwort ist ganz einfach: Archivare, die auf ein bestimmtes Format zugeschnitten sind, komprimieren viel besser.
Bei der Entwicklung von Spielen bei
Playrix verlassen wir uns häufig auf die Notwendigkeit, die Build-Größe zu reduzieren. Spiele entwickeln sich ständig weiter, die Menge an Inhalten wächst und der Platz ist begrenzt.
Bei einem
sehnsüchtigen Blick auf die Ressourcen stellten wir erneut fest, dass einige Dateien aufgrund ihrer Struktur viel besser komprimiert werden können als zip. Während der Experimente ist es uns gelungen, die Größe unseres eigenen Animationsformats erheblich zu reduzieren. Außerdem gibt es einige Verschiebungen bei der Komprimierung von Grafikdateien.
Bei der Entwicklung von Komprimierungsalgorithmen ist ein universeller Entropiecodierer wie rANS oder FSE ein unverzichtbares Werkzeug. Es übernimmt vollständig die Aufgabe, Zeichen mit der geringsten Anzahl von Bits zu schreiben, sodass sich der Entwickler auf die Hauptdetails des Algorithmus konzentrieren kann. Und es funktioniert sowohl beim Codieren als auch beim Decodieren sehr schnell.
Ich hoffe, dieser Artikel hilft Ihnen, rANS kennenzulernen und in Ihren Projekten zu verwenden.
Referenzen
Hier sehen Sie Arbeitsbeispiele für die rANS-Implementierung (mit verschiedenen Optimierungsoptionen):
Fabian Giesen:
github.com/rygorous/ryg_ransSie können interessante Details und Details auf Fabians Blog lesen (auf Englisch):
→
rANS Notizen→
RANS mit statischen Wahrscheinlichkeitsverteilungen→
RANS in der Praxis