bzip2 (Deutsch)

Bzip2 verwendet mehrere übereinander gestapelte Schichten von Komprimierungstechniken, die während der Komprimierung in der folgenden Reihenfolge und während der Dekomprimierung in umgekehrter Reihenfolge auftreten:

1. Lauflängencodierung (RLE) der Anfangsdaten.
2. Burrows-Wheeler-Transformation (BWT) oder Blocksortierung.
3. MTF-Transformation (Move-to-Front).
4. Run-Length-Codierung (RLE) des MTF-Ergebnisses.
5. Huffman-Codierung.
6. Auswahl zwischen mehreren Huffman-Tabellen.
7. Unäre Basis-1-Codierung der Huffman-Tabellenauswahl.
8. Delta-Codierung (Δ) der Huffman-Code-Bitlängen.
9. Sparse-Bit-Array, das zeigt, welche Symbole verwendet werden.

Anfängliche LauflängencodierungEdit

Jede Folge von 4 bis 255 aufeinanderfolgenden doppelten Symbolen wird durch die ersten 4 Symbole und eine Wiederholungslänge zwischen 0 und 251 ersetzt. Somit ist die Folge AAAAAAABBBBCCCD wird durch AAAA\3BBBB\0CCCD ersetzt, wobei \3 und \0 repräsentiert die Bytewerte 3 bzw. 0. Symbolläufe werden immer nach 4 aufeinanderfolgenden Symbolen transformiert, auch wenn die Lauflänge auf Null gesetzt ist, um die Transformation reversibel zu halten.

Im schlimmsten Fall kann dies zu einer Erweiterung von 1,25 und in führen im besten Fall eine Reduzierung auf < 0,02. Während die Spezifikation theoretisch die Codierung von Läufen der Länge 256–259 ermöglicht, erzeugt der Referenzcodierer keine solche Ausgabe.

Der Autor von bzip2 hat angegeben, dass der RLE-Schritt ein historischer Fehler war und nur beabsichtigt war um die ursprüngliche BWT-Implementierung vor pathologischen Fällen zu schützen.

Burrows-Wheeler-TransformationEdit

Dies ist die reversible Block-Sortierung ist das Kernstück von bzip2. Der Block ist vollständig in sich geschlossen, wobei die Eingabe- und Ausgabepuffer gleich groß bleiben. In bzip2 liegt die Betriebsgrenze für diese Stufe bei 900 kB. Für die Blocksortierung wird eine (fiktive) Matrix erstellt, in der Zeile i den gesamten Puffer enthält, die vom i-ten Symbol ausgehend gedreht wird. Nach der Drehung werden die Zeilen der Matrix in alphabetischer (numerischer) Reihenfolge sortiert. Ein 24-Bit-Zeiger wird gespeichert, der die Startposition markiert, wenn der Block nicht transformiert ist. In der Praxis ist es nicht erforderlich, die vollständige Matrix zu erstellen. Vielmehr wird die Sortierung unter Verwendung von Zeigern für jede Position im Puffer durchgeführt. Der Ausgabepuffer ist die letzte Spalte der Matrix. Dieser enthält den gesamten Puffer, ist jedoch neu angeordnet, sodass er wahrscheinlich große Mengen identischer Symbole enthält.

Move-to-Front-TransformationEdit

Auch diese Transformation ändert die Größe des verarbeiteten Blocks nicht. Jedes der im Dokument verwendeten Symbole wird in einem Array platziert. Wenn ein Symbol verarbeitet wird, wird es durch seine Position (Index) im Array ersetzt und dieses Symbol wird an die Vorderseite des Arrays gemischt. Der Effekt ist, dass sofort wiederkehrende Symbole durch Nullsymbole ersetzt werden (lange Läufe eines beliebigen Symbols werden somit zu Läufen von Nullsymbolen), während andere Symbole entsprechend ihrer lokalen Häufigkeit neu zugeordnet werden.

Viele „natürliche“ Daten enthält identische Symbole, die innerhalb eines begrenzten Bereichs wiederkehren (Text ist ein gutes Beispiel). Da die MTF-Transformation Symbolen, die häufig wieder auftauchen, niedrige Werte zuweist, führt dies zu einem Datenstrom, der viele Symbole im niedrigen ganzzahligen Bereich enthält, von denen viele identisch sind (verschiedene wiederkehrende Eingabesymbole können tatsächlich demselben Ausgabesymbol zugeordnet werden). Solche Daten können mit jeder älteren Komprimierungsmethode sehr effizient codiert werden.

Lauflängencodierung von MTF resultEdit

Lange Nullzeichenfolgen in der Ausgabe der Move-to-Front-Transformation ( die von wiederholten Symbolen in der Ausgabe des BWT stammen) werden durch eine Folge von zwei speziellen Codes, RUNA und RUNB, ersetzt, die die Lauflänge als Binärzahl darstellen. Tatsächliche Nullen werden in der Ausgabe niemals codiert. Eine einsame Null wird zu RUNA. (Dieser Schritt wird tatsächlich zur gleichen Zeit wie MTF ausgeführt. Wenn MTF Null erzeugt, erhöht es stattdessen einen Zähler, um dann mit RUNA und RUNB zu codieren.)

Die Sequenz 0, 0, 0, 0, 0, 1 würde als RUNA, RUNB, 1 dargestellt werden; RUNA, RUNB repräsentiert den Wert 5 wie unten beschrieben. Der Lauflängencode wird durch Erreichen eines anderen normalen Symbols beendet. Dieser RLE-Prozess ist flexibler als der anfängliche RLE-Schritt, da er beliebig lange Ganzzahlen codieren kann (in der Praxis ist dies normalerweise durch die Blockgröße begrenzt, sodass dieser Schritt keinen Lauf von mehr als 900000 Bytes codiert). Die Lauflänge wird auf diese Weise codiert: Zuweisen von Ortswerten von 1 zum ersten Bit, von 2 zum zweiten, von 4 zum dritten usw. in der Sequenz, multiplizieren Sie jeden Ortswert in einem RUNB-Punkt mit 2 und addieren Sie alle die resultierenden Ortswerte (für RUNA- und RUNB-Werte gleichermaßen) zusammen. Dies ähnelt der bijektiven Basis-2-Nummerierung.Somit ergibt die Sequenz RUNA, RUNB den Wert (1 + 2 × 2) = 5. Als komplizierteres Beispiel:

RUNA RUNB RUNA RUNA RUNB (ABAAB) 1 2 4 8 16 1 4 4 8 32 = 49

Huffman-CodierungEdit

Dieser Prozess ersetzt Symbole mit fester Länge im Bereich von 0 bis 258 durch Codes mit variabler Länge, basierend auf der Verwendungshäufigkeit. Häufiger verwendete Codes sind kürzer (2–3 Bit), während seltene Codes bis zu 20 Bit zugewiesen werden können. Die Codes werden sorgfältig ausgewählt, damit keine Bitfolge für einen anderen Code verwechselt werden kann.

Der Code am Ende des Streams ist besonders interessant. Wenn in den unkomprimierten Daten n verschiedene Bytes (Symbole) verwendet werden, besteht der Huffman-Code aus zwei RLE-Codes (RUNA und RUNB), n – 1 Symbolcodes und einem End-of-Stream-Code. Aufgrund des kombinierten Ergebnisses der MTF- und RLE-Codierungen in den beiden vorherigen Schritten ist es nie erforderlich, explizit auf das erste Symbol in der MTF-Tabelle zu verweisen (wäre in der normalen MTF Null), wodurch ein Symbol für das Ende gespeichert wird. of-stream-Marker (und Erklärung, warum im Huffman-Baum nur n – 1 Symbole codiert sind). Im Extremfall, in dem nur ein Symbol in den unkomprimierten Daten verwendet wird, gibt es im Huffman-Baum überhaupt keine Symbolcodes, und der gesamte Block besteht aus RUNA und RUNB (impliziert implizit das einzelne Byte) und einem Ende von -stream-Marker mit Wert 2.

0: RUNA, 1: RUNB, 2–257: Byte-Werte 0–255, 258: Ende des Streams, Verarbeitung beenden (möglicherweise nur 2).

Mehrere Huffman-TabellenEdit

Mehrere Huffman-Tabellen mit identischer Größe können mit einem Block verwendet werden, wenn der Gewinn aus ihrer Verwendung größer ist als die Kosten für die Aufnahme der zusätzlichen Tabelle. Es können mindestens 2 und bis zu 6 Tabellen vorhanden sein, wobei die am besten geeignete Tabelle vor jeweils 50 verarbeiteten Symbolen erneut ausgewählt wird. Dies hat den Vorteil einer sehr reaktionsschnellen Huffman-Dynamik, ohne dass ständig neue Tabellen bereitgestellt werden müssen, wie dies in DEFLATE erforderlich wäre. Die Lauflängencodierung im vorherigen Schritt wurde entwickelt, um Codes zu berücksichtigen, deren inverse Verwendungswahrscheinlichkeit höher ist als der kürzeste verwendete Huffman-Code.

Unäre Codierung der Huffman-TabellenauswahlEdit

Wenn mehrere Huffman-Tabellen verwendet werden, erfolgt die Auswahl jeder Tabelle (nummeriert von 0 bis 5) aus einer Liste durch ein nullterminiertes Bit mit einer Länge zwischen 1 und 6 Bit. Die Auswahl erfolgt in einer MTF-Liste der Tabellen. Die Verwendung dieser Funktion führt zu einer maximalen Ausdehnung von etwa 1,015, im Allgemeinen jedoch weniger. Diese Erweiterung wird wahrscheinlich durch den Vorteil der Auswahl geeigneterer Huffman-Tabellen stark überschattet, und der übliche Fall, dass dieselbe Huffman-Tabelle weiterhin verwendet wird, wird als einzelnes Bit dargestellt. Anstelle einer unären Codierung ist dies effektiv eine extreme Form eines Huffman-Baums, bei der jeder Code die Hälfte der Wahrscheinlichkeit des vorherigen Codes aufweist.

Delta-CodierungEdit

Huffman-Code-Bitlängen sind erforderlich, um jede der verwendeten kanonischen Huffman-Tabellen zu rekonstruieren. Jede Bitlänge wird als codierte Differenz zur Bitlänge des vorherigen Codes gespeichert. Ein Nullbit (0) bedeutet, dass die vorherige Bitlänge für den aktuellen Code dupliziert werden sollte, während ein Einbit (1) bedeutet, dass ein weiteres Bit gelesen und die Bitlänge basierend auf diesem Wert erhöht oder verringert werden sollte. P. >

Im allgemeinen Fall wird ein einzelnes Bit pro Symbol und Tabelle verwendet, und im schlimmsten Fall – von Länge 1 bis Länge 20 – würden ungefähr 37 Bits benötigt. Infolge der früheren MTF-Codierung würden die Codelängen bei 2 bis 3 Bit beginnen (sehr häufig verwendete Codes) und allmählich zunehmen, was bedeutet, dass das Delta-Format ziemlich effizient ist und etwa 300 Bit (38 Byte) pro vollständiger Huffman-Tabelle erfordert .

Sparse Bit ArrayEdit

Eine Bitmap zeigt an, welche Symbole im Block verwendet werden und in den Huffman-Bäumen enthalten sein sollten. Binärdaten verwenden wahrscheinlich alle 256 Symbole, die durch ein Byte dargestellt werden können, während Textdaten möglicherweise nur eine kleine Teilmenge der verfügbaren Werte verwenden und möglicherweise den ASCII-Bereich zwischen 32 und 126 abdecken. Das Speichern von 256 Nullbits wäre ineffizient, wenn sie größtenteils nicht verwendet würden. Es wird eine Sparse-Methode verwendet: Die 256 Symbole sind in 16 Bereiche unterteilt, und nur wenn Symbole in diesem Block verwendet werden, ist ein 16-Bit-Array enthalten. Das Vorhandensein jedes dieser 16 Bereiche wird durch ein zusätzliches 16-Bit-Bit-Array an der Vorderseite angezeigt.

Die gesamte Bitmap verwendet zwischen 32 und 272 Bit Speicher (4–34 Byte). Im Gegensatz dazu würde der DEFLATE-Algorithmus das Fehlen von Symbolen zeigen, indem die Symbole so codiert werden, dass sie eine Nullbitlänge mit Lauflängencodierung und zusätzlicher Huffman-Codierung haben