4. Entropy Encoding (Entropiekodierung)

Das Zstandard-Format verwendet zwei Arten der Entropiekodierung: FSE und Huffman-Kodierung. Huffman wird zur Komprimierung von Literalen (Literals) verwendet, während FSE für alle anderen Symbole (Literals_Length_Code, Match_Length_Code und Offset-Codes) und zur Komprimierung von Huffman-Headern verwendet wird.

4.1 FSE (Entropie mit endlichem Zustand)

FSE, kurz für Finite State Entropy (Entropie mit endlichem Zustand), ist ein Entropie-Codec, der auf [ANS] basiert. Die FSE-Kodierung/Dekodierung beinhaltet einen Zustand (State), der zwischen Symbolen übertragen wird, daher muss die Dekodierung in entgegengesetzter Richtung zur Kodierung erfolgen. Daher werden alle FSE-Bitstreams vom Ende zum Anfang gelesen. Beachten Sie, dass die Reihenfolge der Bits im Stream nicht umgekehrt wird; sie werden einfach in umgekehrter Reihenfolge gelesen, als sie geschrieben wurden.

Weitere Details zu FSE finden Sie unter "FiniteStateEntropy" [FSE].

Die FSE-Dekodierung beinhaltet eine Dekodierungstabelle (Decoding Table), die eine Größe als Zweierpotenz hat und drei Elemente enthält: Symbol, Num_Bits (Anzahl der Bits) und Baseline (Basislinie). Der Logarithmus zur Basis 2 der Tabellengröße ist ihr Accuracy_Log (Genauigkeitsprotokoll). Ein FSE-Zustandswert repräsentiert einen Index in dieser Tabelle.

Um den anfänglichen Zustandswert zu erhalten, konsumieren Sie Accuracy_Log Bits aus dem Stream als Little-Endian-Wert. Das nächste Symbol im Stream ist das Symbol, das in der Tabelle für diesen Zustand angegeben ist. Um den nächsten Zustandswert zu erhalten, sollte der Decoder Num_Bits Bits aus dem Stream als Little-Endian-Wert konsumieren und diese zur Baseline hinzufügen.

4.1.1 FSE Table Description (FSE-Tabellenbeschreibung)

Um FSE-Streams zu dekodieren, ist es notwendig, die Dekodierungstabelle zu konstruieren. Das Zstandard-Format kodiert FSE-Tabellenbeschreibungen wie hier beschrieben.

Eine FSE-Verteilungstabelle (Distribution Table) beschreibt die Wahrscheinlichkeiten aller Symbole von 0 bis zum letzten vorhandenen (einschließlich) auf einer normalisierten Skala von (1 << Accuracy_Log). Beachten Sie, dass es zwei oder mehr Symbole mit von Null verschiedener Wahrscheinlichkeit geben muss.

Ein Bitstream wird vorwärts im Little-Endian-Stil gelesen. Es ist nicht notwendig, seine genaue Größe zu kennen, da die Größe vom Dekodierungsprozess entdeckt und gemeldet wird. Der Bitstream beginnt damit, auf welcher Skala er operiert. Wenn low4bits die niedrigsten 4 Bits des ersten Bytes bezeichnet, dann ist Accuracy_Log = low4bits + 5.

Darauf folgt jeder Symbolwert von 0 bis zum letzten vorhandenen. Die Anzahl der von jedem Feld verwendeten Bits ist variabel und hängt ab von:

Verbleibende Wahrscheinlichkeiten + 1 : Zum Beispiel, angenommen ein Accuracy_Log von 8 und angenommen, 100 Wahrscheinlichkeitspunkte wurden bereits verteilt, kann der Decoder jeden Wert von 0 bis (256 - 100 + 1) == 157, einschließlich, lesen. Daher muss er log₂(157) == 8 Bits lesen.

Dekodierter Wert : Kleine Werte verwenden 1 Bit weniger. Zum Beispiel, angenommen Werte von 0 bis 157, einschließlich, sind möglich, bleiben 255 - 157 = 98 Werte in einem 8-Bit-Feld übrig. Die ersten 98 Werte (also von 0 bis 97) verwenden nur 7 Bits, und Werte von 98 bis 157 verwenden 8 Bits. Dies wird durch das Schema in Tabelle 20 erreicht:

+============+===============+===========+
| Value Read | Value Decoded | Bits Used |
+============+===============+===========+
|   0 - 97   |     0 - 97    |     7     |
+------------+---------------+-----------+
|  98 - 127  |    98 - 127   |     8     |
+------------+---------------+-----------+
| 128 - 225  |     0 - 97    |     7     |
+------------+---------------+-----------+
| 226 - 255  |   128 - 157   |     8     |
+------------+---------------+-----------+

Tabelle 20: Dekodierte Werte

Symbolwahrscheinlichkeiten werden nacheinander in Reihenfolge gelesen. Die Wahrscheinlichkeit wird aus dem dekodierten Wert (Value Decoded) unter Verwendung der Formel P = Value - 1 erhalten. Dies bedeutet, dass der Wert 0 zur negativen Wahrscheinlichkeit -1 wird. Dies ist eine spezielle Wahrscheinlichkeit, die "kleiner als 1" bedeutet. Ihre Auswirkung auf die Verteilungstabelle wird unten beschrieben. Zum Zweck der Berechnung der gesamten zugewiesenen Wahrscheinlichkeitspunkte zählt sie als 1.

Wenn ein Symbol eine Wahrscheinlichkeit von null hat, folgt ihm ein 2-Bit-Wiederholungsflag (Repeat Flag). Dieses Wiederholungsflag gibt an, wie viele Wahrscheinlichkeiten von Nullen dem aktuellen folgen. Es liefert eine Zahl von 0 bis 3. Wenn es eine 3 ist, folgt ein weiteres 2-Bit-Wiederholungsflag, und so weiter.

Wenn das letzte Symbol eine kumulative Summe von (1 << Accuracy_Log) erreicht, ist die Dekodierung abgeschlossen. Wenn das letzte Symbol die kumulative Summe über (1 << Accuracy_Log) hinausgehen lässt, wird die Verteilung als beschädigt betrachtet.

Schließlich kann der Decoder erkennen, wie viele Bytes in diesem Prozess verwendet wurden und wie viele Symbole vorhanden sind. Der Bitstream verbraucht eine runde Anzahl von Bytes. Jedes verbleibende Bit im letzten Byte wird einfach nicht verwendet.

Der Kontext, in dem die Tabelle verwendet werden soll, spezifiziert eine erwartete Anzahl von Symbolen. Diese erwartete Anzahl von Symbolen übersteigt niemals 256. Wenn die Anzahl der dekodierten Symbole nicht der erwarteten entspricht, sollte der Header als beschädigt betrachtet werden.

Die Verteilung normalisierter Wahrscheinlichkeiten reicht aus, um eine eindeutige Dekodierungstabelle zu erstellen. Die Tabelle hat eine Größe von (1 << Accuracy_Log). Jede Zelle beschreibt das dekodierte Symbol und Anweisungen zum Erhalt des nächsten Zustands.

Symbole werden in ihrer natürlichen Reihenfolge nach "kleiner als 1"-Wahrscheinlichkeiten wie oben beschrieben gescannt. Symbolen mit dieser Wahrscheinlichkeit wird eine einzelne Zelle zugewiesen, beginnend am Ende der Tabelle und rückwärts gehend. Diese Symbole definieren eine vollständige Zustandsrücksetzung (Full State Reset), wobei Accuracy_Log Bits gelesen werden.

Alle verbleibenden Symbole werden in ihrer natürlichen Reihenfolge zugewiesen. Beginnend mit Symbol 0 und Tabellenposition 0 werden jedem Symbol so viele Zellen zugewiesen wie seine Wahrscheinlichkeit. Die Zellzuweisung ist verteilt, nicht linear; jede Nachfolgeposition folgt dieser Regel:

position += (tableSize >> 1) + (tableSize >> 3) + 3;
position &= tableSize - 1;

Eine Position wird übersprungen, wenn sie bereits von einem Symbol mit "kleiner als 1"-Wahrscheinlichkeit belegt ist. Die Position wird zwischen Symbolen nicht zurückgesetzt; sie iteriert einfach durch jede Position in der Tabelle und wechselt zum nächsten Symbol, wenn genügend Zustände dem aktuellen zugewiesen wurden.

Das Ergebnis ist eine Liste von Zustandswerten. Jeder Zustand wird das aktuelle Symbol dekodieren.

Um die Number_of_Bits und Baseline zu erhalten, die für den nächsten Zustand erforderlich sind, ist es zunächst notwendig, alle Zustände in ihrer natürlichen Reihenfolge zu sortieren. Die niedrigeren Zustände benötigen 1 Bit mehr als höhere. Der Prozess wird für jedes Symbol wiederholt.

Zum Beispiel, angenommen ein Symbol hat eine Wahrscheinlichkeit von 5, erhält es fünf Zustandswerte. Zustände werden in natürlicher Reihenfolge sortiert. Die nächste Zweierpotenz ist 8. Der Wahrscheinlichkeitsraum wird in 8 gleiche Teile geteilt. Angenommen, der Accuracy_Log ist 7, definiert dies 128 Zustände, und jeder Anteil (geteilt durch 8) hat eine Größe von 16. Um 8 zu erreichen, zählen 8 - 5 = 3 niedrigste Zustände "doppelt", verdoppeln die Anzahl der Anteile (Breite 32) und benötigen im Prozess 1 Bit mehr.

Die Baseline wird beginnend von den höheren Zuständen mit weniger Bits zugewiesen und natürlich fortfahrend, dann beim ersten Zustand wieder aufnehmend, wobei jeder seine zugewiesene Breite von der Baseline nimmt.

+----------------+-------+-------+--------+------+-------+
|  state order   |   0   |   1   |   2    |  3   |   4   |
+----------------+-------+-------+--------+------+-------+
|     width      |   32  |   32  |   32   |  16  |   16  |
+----------------+-------+-------+--------+------+-------+
| Number_of_Bits |   5   |   5   |   5    |  4   |   4   |
+----------------+-------+-------+--------+------+-------+
|  range number  |   2   |   4   |   6    |  0   |   1   |
+----------------+-------+-------+--------+------+-------+
|    Baseline    |   32  |   64  |   96   |  0   |   16  |
+----------------+-------+-------+--------+------+-------+
|     range      | 32-63 | 64-95 | 96-127 | 0-15 | 16-31 |
+----------------+-------+-------+--------+------+-------+

Tabelle 21: Baseline-Zuweisungen

Der nächste Zustand wird aus dem aktuellen Zustand bestimmt, indem die erforderlichen Number_of_Bits gelesen und die angegebene Baseline hinzugefügt werden.

Siehe Anhang A für die Ergebnisse dieses Prozesses, die auf die Standardverteilungen angewendet werden.

4.2 Huffman Coding (Huffman-Kodierung)

Zstandard Huffman-kodierte Streams werden rückwärts gelesen, ähnlich wie FSE-Bitstreams. Daher ist es notwendig, den Offset des letzten Bytes des Huffman-kodierten Streams zu kennen, um den Anfang des Bitstreams zu finden.

Nach dem Schreiben des letzten Bits, das Informationen enthält, schreibt der Kompressor ein einzelnes 1-Bit und füllt dann den Rest des Bytes mit 0-Bits. Das letzte Byte des komprimierten Bitstreams kann aus diesem Grund nicht 0 sein.

Beim Dekomprimieren ist das letzte Byte, das die Auffüllung enthält, das erste zu lesende Byte. Der Dekompressor muss bis zu 7 Bits der 0-Auffüllung sowie das erste auftretende 1-Bit überspringen. Danach beginnt der nützliche Teil des Bitstreams.

Der Bitstream enthält Huffman-kodierte Symbole in Little-Endian-Reihenfolge, mit den unten definierten Codes.

4.2.1 Huffman Tree Description (Huffman-Baumbeschreibung)

Präfixkodierung (Prefix Coding) repräsentiert Symbole aus einem a priori bekannten Alphabet durch Bitsequenzen (Codewörter), ein Codewort für jedes Symbol, auf eine Weise, dass verschiedene Symbole durch Bitsequenzen unterschiedlicher Längen dargestellt werden können, aber ein Parser immer eindeutig eine kodierte Zeichenfolge Symbol für Symbol parsen kann.

Bei gegebenem Alphabet mit bekannten Symbolfrequenzen ermöglicht der Huffman-Algorithmus die Konstruktion eines optimalen Präfixcodes unter Verwendung der wenigsten Bits aller möglichen Präfixcodes für dieses Alphabet.

Der Präfixcode darf eine maximale Codelänge nicht überschreiten. Mehr Bits verbessern die Genauigkeit, führen aber zu einer größeren Header-Größe und erfordern mehr Speicher oder komplexere Dekodierungsoperationen. Diese Spezifikation begrenzt die maximale Codelänge auf 11 Bits.

Alle Literalwerte von null (einschließlich) bis zum letzten vorhandenen (ausschließlich) werden durch Weight (Gewicht) mit Werten von 0 bis Max_Number_of_Bits dargestellt. Die Transformation von Weight zu Number_of_Bits folgt diesem Pseudocode:

if Weight == 0:
    Number_of_Bits = 0
else:
    Number_of_Bits = Max_Number_of_Bits + 1 - Weight

Das Weight des letzten Symbols wird aus den zuvor dekodierten abgeleitet, indem zur nächsten Zweierpotenz vervollständigt wird. Diese Zweierpotenz ergibt Max_Number_of_Bits, die Tiefe des aktuellen Baums.

(Fortsetzung mit Tabellen 22-26 und Huffman-Kodierungsdetails)

---