Lempel-Ziv-Markov-Kettenalgorithmus – Wikipedia

Das Lempel-Ziv-Markov-Kettenalgorithmus ((LZMA) ist ein Algorithmus zur verlustfreien Datenkomprimierung. Es wird seit 1996 oder 1998 von Igor Pavlov entwickelt^[1] und wurde zuerst im 7z-Format des 7-Zip-Archivierers verwendet. Dieser Algorithmus verwendet ein Wörterbuchkomprimierungsschema, das dem 1977 von Abraham Lempel und Jacob Ziv veröffentlichten LZ77-Algorithmus ähnelt und ein hohes Komprimierungsverhältnis aufweist (im Allgemeinen höher als bzip2).^[2][3] und eine variable Größe des Komprimierungswörterbuchs (bis zu 4 GB),^[4] unter Beibehaltung der Dekomprimierungsgeschwindigkeit ähnlich wie bei anderen häufig verwendeten Komprimierungsalgorithmen.^[5]

LZMA2 ist ein einfaches Containerformat, das sowohl unkomprimierte Daten als auch LZMA-Daten enthalten kann, möglicherweise mit mehreren unterschiedlichen LZMA-Codierungsparametern. LZMA2 unterstützt eine beliebig skalierbare Multithread-Komprimierung und -Dekomprimierung sowie eine effiziente Komprimierung von Daten, die teilweise inkomprimierbar ist. Es wird jedoch behauptet, dass es unsicher und weniger effizient als LZMA ist.^[6]

Überblick[edit]

LZMA verwendet einen Wörterbuchkomprimierungsalgorithmus (eine Variante von LZ77 mit großen Wörterbuchgrößen und spezieller Unterstützung für wiederholt verwendete Übereinstimmungsentfernungen), dessen Ausgabe dann mit einem Entfernungscodierer codiert wird, wobei ein komplexes Modell verwendet wird, um eine Wahrscheinlichkeitsvorhersage für jedes Bit zu erstellen. Der Wörterbuchkompressor findet Übereinstimmungen unter Verwendung ausgefeilter Wörterbuchdatenstrukturen und erzeugt einen Strom von Literalsymbolen und Phrasenreferenzen, der vom Entfernungscodierer bitweise codiert wird: Viele Codierungen sind möglich, und ein dynamischer Programmieralgorithmus wird verwendet, um eine auszuwählen unter bestimmten Annäherungen optimal.^[7]

Vor LZMA waren die meisten Codierermodelle rein bytebasiert (dh sie codierten jedes Bit nur mit einer Kaskade von Kontexten, um die Abhängigkeiten von vorherigen Bits desselben Bytes darzustellen). Die Hauptinnovation von LZMA besteht darin, dass das LZMA-Modell anstelle eines generischen bytebasierten Modells kontextspezifische Kontexte in jeder Darstellung eines Literals oder einer Phrase verwendet: Dies ist fast so einfach wie ein generisches bytebasiertes Modell, bietet jedoch viel bessere Ergebnisse Komprimierung, da vermieden wird, dass nicht verwandte Bits im selben Kontext zusammengemischt werden. Darüber hinaus können und sind die Wörterbuchgrößen im Vergleich zur klassischen Wörterbuchkomprimierung (wie sie in den Formaten zip und gzip verwendet wird) und sind in der Regel viel größer, wobei die große Speichermenge genutzt wird, die auf modernen Systemen verfügbar ist.^[7]

Übersicht über komprimiertes Format[edit]

Bei der LZMA-Komprimierung ist der komprimierte Strom ein Bitstrom, der unter Verwendung eines adaptiven Binärbereichscodierers codiert wird. Der Stream ist in Pakete unterteilt, wobei jedes Paket entweder ein einzelnes Byte oder eine LZ77-Sequenz beschreibt, deren Länge und Entfernung implizit oder explizit codiert sind. Jeder Teil jedes Pakets wird mit unabhängigen Kontexten modelliert, sodass die Wahrscheinlichkeitsvorhersagen für jedes Bit mit den Werten dieses Bits (und verwandten Bits aus demselben Feld) in vorherigen Paketen desselben Typs korreliert sind. Sowohl das lzip^[8] Die LZMA SDK-Dokumentation beschreibt dieses Stream-Format.^[7]

Es gibt 7 Arten von Paketen:^[8]

Gepackter Code (Bitfolge)	Paketname	Paketbeschreibung
0 + byteCode	ZÜNDETE	Ein einzelnes Byte, das unter Verwendung eines adaptiven Binärbereichscodierers codiert wurde.
1 + 0 + len + dist	SPIEL	Eine typische LZ77-Sequenz, die Sequenzlänge und -abstand beschreibt.
1 + 1 + 0 + 0	SHORTREP	Eine Ein-Byte-LZ77-Sequenz. Die Entfernung entspricht der zuletzt verwendeten LZ77-Entfernung.
1 + 1 + 0 + 1 + len	LONGREP[0]	Eine LZ77-Sequenz. Die Entfernung entspricht der zuletzt verwendeten LZ77-Entfernung.
1 + 1 + 1 + 0 + len	LONGREP[1]	Eine LZ77-Sequenz. Die Entfernung entspricht der vorletzten verwendeten LZ77-Entfernung.
1 + 1 + 1 + 1 + 0 + len	LONGREP[2]	Eine LZ77-Sequenz. Die Entfernung entspricht der drittletzten verwendeten LZ77-Entfernung.
1 + 1 + 1 + 1 + 1 + len	LONGREP[3]	Eine LZ77-Sequenz. Die Entfernung entspricht der viertletzten verwendeten LZ77-Entfernung.

LONGREP[*] bezieht sich auf LONGREP[0-3] Pakete, * REP bezieht sich sowohl auf LONGREP als auch auf SHORTREP, und * MATCH bezieht sich sowohl auf MATCH als auch auf * REP.

LONGREP[n] Pakete entfernen den verwendeten Abstand aus der Liste der letzten Entfernungen und fügen ihn vorne wieder ein, um unnötige wiederholte Eingaben zu vermeiden, während MATCH den Abstand nur nach vorne hinzufügt, selbst wenn er bereits in der Liste und in SHORTREP und LONGREP vorhanden ist[0] Ändere die Liste nicht.

Die Länge wird wie folgt codiert:

Längencode (Bitfolge)	Beschreibung
0+ 3 Bits	Die mit 3 Bit codierte Länge ergibt einen Längenbereich von 2 bis 9.
1 + 0 + 3 Bits	Die mit 3 Bit codierte Länge ergibt einen Längenbereich von 10 bis 17.
1 + 1 + 8 Bits	Die mit 8 Bit codierte Länge ergibt einen Längenbereich von 18 bis 273.

Wie in LZ77 ist die Länge nicht durch die Entfernung begrenzt, da das Kopieren aus dem Wörterbuch so definiert ist, als ob die Kopie byteweise ausgeführt wurde, wobei die Entfernung konstant gehalten wird.

Entfernungen sind logisch 32-Bit und Entfernung 0 Punkte zum zuletzt hinzugefügten Byte im Wörterbuch.

Die Entfernungscodierung beginnt mit einem 6-Bit- “Entfernungsschlitz”, der bestimmt, wie viele weitere Bits benötigt werden. Entfernungen werden als binäre Verkettung von zwei Bits von höchstens bis niedrigstwertig in Abhängigkeit vom Entfernungsschlitz, einigen Bits mit einer festen Wahrscheinlichkeit von 0,5 und einigen kontextcodierten Bits gemäß der folgenden Tabelle decodiert (Entfernungsschlitze 0-3 direkt codieren) Abstände 0−3).

6-Bit-Distanzschlitz	Höchste 2 Bits	Feste 0,5 Wahrscheinlichkeitsbits	Kontextcodierte Bits
0	00	0	0
1	01	0	0
2	10	0	0
3	11	0	0
4	10	0	1
5	11	0	1
6	10	0	2
7	11	0	2
8	10	0	3
9	11	0	3
10	10	0	4
11	11	0	4
12	10	0	5
13	11	0	5
14–62 (gerade)	10	((Steckplatz / 2) – 5)	4
15–63 (ungerade)	11	(((Steckplatz – 1) / 2) – 5)	4

^[7]

Details zum Dekomprimierungsalgorithmus[edit]

Es scheint keine vollständige natürliche Sprachspezifikation des komprimierten Formats zu existieren, außer der im folgenden Text versuchten.

Die folgende Beschreibung basiert auf dem kompakten XZ Embedded-Decoder von Lasse Collin, der in der Linux-Kernelquelle enthalten ist^[9] Daraus lassen sich die Details des LZMA- und LZMA2-Algorithmus relativ leicht ableiten: Obwohl das Zitieren des Quellcodes als Referenz nicht ideal ist, sollte jeder Programmierer in der Lage sein, die folgenden Ansprüche mit ein paar Stunden Arbeit zu überprüfen.

Bereichscodierung von Bits[edit]

LZMA-Daten werden auf der niedrigsten Ebene bitweise vom Entfernungsdecoder in Richtung des LZMA-Decoders decodiert.

Die kontextbasierte Bereichsdecodierung wird vom LZMA-Algorithmus aufgerufen, der ihm einen Verweis auf den “Kontext” übergibt, der aus der vorzeichenlosen 11-Bit-Variablen besteht prob (typischerweise unter Verwendung eines 16-Bit-Datentyps implementiert), der die vorhergesagte Wahrscheinlichkeit darstellt, dass das Bit 0 ist, was vom Entfernungsdecoder gelesen und aktualisiert wird (und auf 2 ^ 10 initialisiert werden sollte, was eine Wahrscheinlichkeit von 0,5 darstellt).

Die Dekodierung des Bereichs mit fester Wahrscheinlichkeit geht stattdessen von einer Wahrscheinlichkeit von 0,5 aus, unterscheidet sich jedoch geringfügig von der kontextbasierten Dekodierung des Bereichs.

Der Bereichsdecoderstatus besteht aus zwei vorzeichenlosen 32-Bit-Variablen. Angebot (repräsentiert die Bereichsgröße) und Code (repräsentiert den codierten Punkt innerhalb des Bereichs).

Die Initialisierung des Entfernungsdecoders besteht aus der Einstellung Angebot zu 2³² – 1 und Code auf den 32-Bit-Wert ab dem zweiten Byte im Stream, der als Big-Endian interpretiert wird; Das erste Byte im Stream wird vollständig ignoriert.

Die Normalisierung erfolgt folgendermaßen:

1. Verschieben Sie beide Angebot und Code links von 8 Bits
2. Lesen Sie ein Byte aus dem komprimierten Stream
3. Setzen Sie die niedrigstwertigen 8 Bits von Code auf den gelesenen Bytewert

Kontextbasierte Bereichsdecodierung eines Bits mit dem prob Die Wahrscheinlichkeitsvariable geht folgendermaßen vor:

1. Wenn Angebot ist kleiner als 2 ^ 24, führen Sie eine Normalisierung durch
2. einstellen gebunden zum Boden(Angebot / 2 ^ 11) * prob
3. Wenn Code ist weniger als gebunden::
   1. einstellen Angebot zu gebunden
   2. einstellen prob zu prob + Etage ((2 ^ 11 – prob) / 2 ^ 5)
   3. Rückgabebit 0
4. Ansonsten (wenn Code ist größer oder gleich dem gebunden):
   1. einstellen Angebot zu Angebot – – gebunden
   2. einstellen Code zu Code – – gebunden
   3. einstellen prob zu prob – Fußboden(prob / 2 ^ 5)
   4. Bit 1 zurückgeben

Die Dekodierung eines Bits im Bereich mit fester Wahrscheinlichkeit erfolgt folgendermaßen:

1. Wenn Angebot ist kleiner als 2 ^ 24, führen Sie eine Normalisierung durch
2. einstellen Angebot zum Boden(Angebot / 2)
3. Wenn Code ist weniger als Angebot::
   1. Rückgabebit 0
4. Ansonsten (wenn Code ist größer oder gleich als Angebot):
   1. einstellen Code zu Code – – Angebot
   2. Bit 1 zurückgeben

Die Linux-Kernel-Implementierung der Dekodierung mit fester Wahrscheinlichkeit in rc_direct enthält aus Leistungsgründen keinen bedingten Zweig, sondern subtrahiert Angebot von Code bedingungslos und verwendet das resultierende Vorzeichenbit, um sowohl das zurückzugebende Bit zu entscheiden als auch eine Maske zu generieren, die mit kombiniert wird Code und hinzugefügt Angebot.

Beachten Sie, dass:

1. Die Division durch 2 ^ 11 beim Rechnen gebunden Die Bodenoperation erfolgt vor der Multiplikation, nicht danach (anscheinend, um eine schnelle Hardwareunterstützung für die 32-Bit-Multiplikation mit einem 64-Bit-Ergebnis zu vermeiden).
2. Die Dekodierung mit fester Wahrscheinlichkeit entspricht nicht unbedingt der kontextbasierten Dekodierung von Bereichen prob Wert, aufgrund der Tatsache, dass die kontextbasierte Bereichsdecodierung die unteren 11 Bits von verwirft Angebot vor dem Multiplizieren mit prob Wie gerade beschrieben, verwirft die Decodierung mit fester Wahrscheinlichkeit nur das letzte Bit

Bereichskodierung von ganzen Zahlen[edit]

Der Bereichsdecodierer stellt auch die Bitbaum-, Umkehrbitbaum- und Ganzzahldecodierungsfunktionen mit fester Wahrscheinlichkeit bereit, die zum Decodieren von Ganzzahlen verwendet werden, und verallgemeinert die oben beschriebene Einzelbitdecodierung. Dekodieren von vorzeichenlosen Ganzzahlen kleiner als Grenze, ein Array von (Grenze – 1) Es werden 11-Bit-Wahrscheinlichkeitsvariablen bereitgestellt, die konzeptionell als interne Knoten eines vollständigen Binärbaums mit angeordnet sind Grenze Blätter.

Die nicht umgekehrte Bitbaumdecodierung funktioniert, indem ein Zeiger auf den Variablenbaum beibehalten wird, der an der Wurzel beginnt. Solange der Zeiger nicht auf ein Blatt zeigt, wird ein Bit mit der durch den Zeiger angegebenen Variablen dekodiert und der Zeiger wird entweder zu den linken oder rechten untergeordneten Elementen bewegt, je nachdem, ob das Bit 0 oder 1 ist. Wenn der Zeiger auf ein Blatt zeigt, wird die dem Blatt zugeordnete Nummer zurückgegeben.

Die nicht umgekehrte Bitbaumdecodierung erfolgt somit vom höchstwertigen zum niedrigstwertigen Bit und stoppt, wenn nur ein Wert im gültigen Bereich möglich ist (dies ermöglicht konzeptionell Bereichsgrößen, die keine Zweierpotenzen sind, obwohl LZMA dies nicht tut Verwendung davon).

Die umgekehrte Bitbaumdecodierung decodiert stattdessen vom niedrigstwertigen Bit zum höchstwertigen Bit und unterstützt daher nur Bereiche mit Zweierpotenzen und decodiert immer die gleiche Anzahl von Bits. Dies entspricht der Durchführung einer nicht umgekehrten Bittree-Decodierung mit einer Zweierpotenz Grenzeund Umkehren des letzten log2 (Grenze) Bits des Ergebnisses.

In der Funktion rc_bittree im Linux-Kernel werden Ganzzahlen tatsächlich im zurückgegeben [limit, 2 * limit) range (with limit added to the conceptual value), and the variable at index 0 in the array is unused, while the one at index 1 is the root, and the left and right children indices are computed as 2i and 2i + 1. The rc_bittree_reverse function instead adds integers in the [0, limit) range to a caller-provided variable, where limit is implicitly represented by its logarithm, and has its own independent implementation for efficiency reasons.

Fixed probability integer decoding simply performs fixed probability bit decoding repeatedly, reading bits from the most to the least significant.

LZMA configuration[edit]

Der LZMA-Decoder wird von einem konfiguriert lclppb Byte “Eigenschaften” und eine Wörterbuchgröße. Der Wert des lclppb Byte ist lc + lp * 9 + pb * 9 * 5, wobei:

• lc ist die Anzahl der hohen Bits des vorherigen Bytes, die als Kontext für die Literalcodierung verwendet werden sollen (der vom LZMA SDK verwendete Standardwert ist 3).
• lp ist die Anzahl der niedrigen Bits der Wörterbuchposition, die enthalten sein sollen literal_pos_state (Der vom LZMA SDK verwendete Standardwert ist 0)
• pb ist die Anzahl der niedrigen Bits der Wörterbuchposition, die enthalten sein sollen pos_state (Der vom LZMA SDK verwendete Standardwert ist 2)

In Nicht-LZMA2-Streams lc darf nicht größer als 8 sein und lp und pb darf nicht größer als 4 sein. In LZMA2-Streams (lc + lp) und pb darf nicht größer als 4 sein.

Im 7-Zip-LZMA-Dateiformat wird die Konfiguration durch einen Header durchgeführt, der das Byte “Eigenschaften” enthält, gefolgt von der 32-Bit-Little-Endian-Wörterbuchgröße in Byte. In LZMA2 kann das Eigenschaftenbyte optional zu Beginn von LZMA2-LZMA-Paketen geändert werden, während die Wörterbuchgröße wie später beschrieben im LZMA2-Header angegeben wird.

LZMA-Codierungskontexte[edit]

Das LZMA-Paketformat wurde bereits beschrieben, und dieser Abschnitt gibt an, wie LZMA die LZ-codierten Streams statistisch modelliert oder mit anderen Worten, welche Wahrscheinlichkeitsvariablen an den Bereichsdecoder übergeben werden, um jedes Bit zu decodieren.

Diese Wahrscheinlichkeitsvariablen werden als mehrdimensionale Arrays implementiert. Vor ihrer Einführung werden einige Werte definiert, die als Indizes in diesen mehrdimensionalen Arrays verwendet werden.

Das Zustand Der Wert basiert konzeptionell darauf, welches der Muster in der folgenden Tabelle mit den neuesten 2-4 Pakettypen übereinstimmt, und wird als Zustandsmaschinenzustand implementiert, der bei jeder Ausgabe eines Pakets gemäß der in der Tabelle aufgeführten Übergangstabelle aktualisiert wird.

Der Anfangszustand ist 0, und daher wird angenommen, dass Pakete vor dem Beginn LIT-Pakete sind.

Zustand	vorherige Pakete				nächster Zustand, wenn das nächste Paket ist
	4. vorheriger	3. vorheriger	2. vorheriger	Bisherige	ZÜNDETE	SPIEL	LONGREP[*]	SHORTREP
0		ZÜNDETE	ZÜNDETE	ZÜNDETE	0	7	8	9
1		SPIEL	ZÜNDETE	ZÜNDETE	0	7	8	9
2		LONGREP[*]	ZÜNDETE	ZÜNDETE	0	7	8	9
	*SPIEL	SHORTREP
3	ZÜNDETE	SHORTREP	ZÜNDETE	ZÜNDETE	0	7	8	9
4			SPIEL	ZÜNDETE	1	7	8	9
5			LONGREP[*]	ZÜNDETE	2	7	8	9
		*SPIEL	SHORTREP
6		ZÜNDETE	SHORTREP	ZÜNDETE	3	7	8	9
7			ZÜNDETE	SPIEL	4	10	11	11
8			ZÜNDETE	LONGREP[*]	5	10	11	11
9			ZÜNDETE	SHORTREP	6	10	11	11
10			*SPIEL	SPIEL	4	10	11	11
11			*SPIEL	* REP	5	10	11	11

Das pos_state und literal_pos_state Werte bestehen jeweils aus den pb und lp (bis zu 4 aus dem LZMA-Header oder dem LZMA2-Eigenschaftenpaket) niedrigstwertige Bits der Wörterbuchposition (die Anzahl der Bytes, die seit dem letzten Zurücksetzen des Wörterbuchs codiert wurden, modulo die Wörterbuchgröße). Beachten Sie, dass die Wörterbuchgröße normalerweise das Vielfache einer großen Zweierpotenz ist. Daher werden diese Werte äquivalent als die niedrigstwertigen Bits der Anzahl unkomprimierter Bytes beschrieben, die seit dem letzten Zurücksetzen des Wörterbuchs gesehen wurden.

Das prev_byte_lc_msbs Wert wird auf die gesetzt lc (bis zu 4 aus dem LZMA-Header oder dem LZMA2-Eigenschaftenpaket) höchstwertige Bits des vorherigen unkomprimierten Bytes.

Das is_REP Der Wert gibt an, ob ein Paket, das eine Länge enthält, eher ein LONGREP als ein MATCH ist.

Das match_byte value ist das Byte, das dekodiert worden wäre, wenn ein SHORTREP-Paket verwendet worden wäre (mit anderen Worten, das Byte, das im Wörterbuch in der zuletzt verwendeten Entfernung gefunden wurde); Es wird nur direkt nach einem * MATCH-Paket verwendet.

literal_bit_mode ist ein Array von 8 Werten im Bereich von 0-2, einer für jede Bitposition in einem Byte, die 1 oder 2 sind, wenn das vorherige Paket ein * MATCH war und es entweder die höchstwertige Bitposition oder alle höherwertigen Bits ist im zu codierenden / decodierenden Literal sind gleich den Bits an den entsprechenden Positionen in match_byte, während es sonst 0 ist; Die Wahl zwischen den Werten 1 oder 2 hängt vom Wert des Bits an derselben Position in ab match_byte.

Der Literal / Literal-Satz von Variablen kann als “Pseudobitbaum” angesehen werden, der einem Bitbaum ähnlich ist, jedoch mit 3 Variablen anstelle von 1 in jedem Knoten, der abhängig von der ausgewählt wird literal_bit_mode Wert an der Bitposition des nächsten zu decodierenden Bits nach dem vom Knoten angegebenen Bitbaumkontext.

Die in einigen Quellen gefundene Behauptung, dass Literale nach einem * MATCH als XOR des Bytewerts mit codiert werden match_byte ist falsch; Sie werden stattdessen einfach als Bytewert codiert, verwenden jedoch den gerade beschriebenen Pseudobitbaum und den in der folgenden Tabelle aufgeführten zusätzlichen Kontext.

Die in LZMA verwendeten Wahrscheinlichkeitsvariablengruppen sind folgende:

XZ Name	LZMA SDK Name	Parametriert von	Wird verwendet, wenn	Codierungsmodus	Wenn Bit 0 dann	Wenn Bit 1 dann
is_match	IsMatch	Zustand, pos_state	Paketstart	bisschen	ZÜNDETE	*SPIEL
is_rep	IsRep	Zustand	nach Bitfolge 1	bisschen	SPIEL	* REP
is_rep0	IsRepG0	Zustand	nach Bitfolge 11	bisschen	SHORTREP / LONGREP[0]	LONGREP[1-3]
is_rep0_long	IsRep0Long	Zustand, pos_state	nach der Bitfolge 110	bisschen	SHORTREP	LONGREP[0]
is_rep1	IsRepG1	Zustand	nach der Bitfolge 111	bisschen	LONGREP[1]	LONGREP[2/3]
is_rep2	IsRepG2	Zustand	nach Bitfolge 1111	bisschen	LONGREP[2]	LONGREP[3]
wörtlich	Wörtlich	prev_byte_lc_msbs, literal_pos_state, literal_bit_mode[bit position], Bitbaumkontext	nach Bitfolge 0	256-Werte-Pseudobitbaum	Literalbytewert
dist_slot	PosSlot	Mindest(match_length, 5), Bitbaumkontext	Entfernung: Start	64-Werte-Bitbaum	Distanzschlitz
dist_special	SpecPos	distance_slot, umgekehrter Bitbaumkontext	Entfernung: 4–13 Entfernungsschlitze	((distance_slot >> 1) – 1) -Bit-Reverse-Bitbaum	geringe Entfernung
dist_align	Ausrichten	umgekehrter Bitbaumkontext	Entfernung: 14+ Entfernungsschlitze nach Bits mit fester Wahrscheinlichkeit	4-Bit-Reverse-Bitbaum	geringe Entfernung
len_dec.choice	LenChoice	is_REP	Spieldauer: Start	bisschen	2–9 Länge	10+ Länge
len_dec.choice2	LenChoice2	is_REP	Übereinstimmungslänge: nach Bitfolge 1	bisschen	10–17 Länge	Länge 18+
len_dec.low	LenLow	is_REP, pos_state, Bitbaumkontext	Übereinstimmungslänge: nach Bitfolge 0	8-Werte-Bitbaum	geringe Länge
len_dec.mid	LenMid	is_REP, pos_state, Bitbaumkontext	Übereinstimmungslänge: nach Bitfolge 10	8-Werte-Bitbaum	mittlere Länge
len_dec.high	LenHigh	is_REP, Bitbaumkontext	Übereinstimmungslänge: nach Bitfolge 11	256-Werte-Bitbaum	hohe Bits der Länge

LZMA2-Format[edit]

Der LZMA2-Container unterstützt mehrere Läufe von komprimierten LZMA-Daten und unkomprimierten Daten. Jeder komprimierte LZMA-Lauf kann eine andere LZMA-Konfiguration und ein anderes Wörterbuch haben. Dies verbessert die Komprimierung von teilweise oder vollständig inkomprimierbaren Dateien und ermöglicht die Multithread-Komprimierung und Multithread-Dekomprimierung, indem die Datei in Läufe aufgeteilt wird, die unabhängig voneinander parallel komprimiert oder dekomprimiert werden können. Kritik an den Änderungen von LZMA2 gegenüber LZMA besteht darin, dass Header-Felder nicht von CRCs abgedeckt werden und eine parallele Dekomprimierung in der Praxis nicht möglich ist.^[6]

Der LZMA2-Header besteht aus einem Byte, das die Wörterbuchgröße angibt:

• 40 gibt eine Wörterbuchgröße von 4 GB – 1 an
• Gerade Werte unter 40 zeigen eine 2 an^{v/ 2 + 12} Bytes Wörterbuchgröße
• Ungerade Werte unter 40 zeigen 3 × 2 an^{((v – 1) / 2 + 11} Bytes Wörterbuchgröße
• Werte über 40 sind ungültig

LZMA2-Daten bestehen aus Paketen, die mit einem Steuerbyte beginnen, mit den folgenden Werten:

• 0 bezeichnet das Ende der Datei
• 1 bezeichnet ein Zurücksetzen des Wörterbuchs, gefolgt von einem unkomprimierten Block
• 2 bezeichnet einen unkomprimierten Block ohne Zurücksetzen des Wörterbuchs
• 3-0x7f sind ungültige Werte
• 0x80-0xff bezeichnet einen LZMA-Block, wobei die niedrigsten 5 Bits als Bit 16-20 der unkomprimierten Größe minus eins verwendet werden und Bit 5-6 angibt, was zurückgesetzt werden soll

Die Bits 5-6 für LZMA-Chunks können sein:

• 0: nichts zurückgesetzt
• 1: Status zurücksetzen
• 2: Zurücksetzen des Status, Zurücksetzen der Eigenschaften mithilfe des Eigenschaftenbytes
• 3: Zurücksetzen des Status, Zurücksetzen der Eigenschaften mithilfe des Eigenschaftenbytes, Zurücksetzen des Wörterbuchs

Das Zurücksetzen des LZMA-Status bewirkt ein Zurücksetzen des gesamten LZMA-Status mit Ausnahme des Wörterbuchs und insbesondere:

• Der Entfernungscodierer
• Das Zustand Wert
• Die letzten Entfernungen für wiederholte Spiele
• Alle LZMA-Wahrscheinlichkeiten

Unkomprimierte Stücke bestehen aus:

• Ein 16-Bit-Big-Endian-Wert, der die Datengröße minus eins codiert
• Die Daten, die wörtlich in das Wörterbuch und die Ausgabe kopiert werden sollen

LZMA-Stücke bestehen aus:

• Ein 16-Bit-Big-Endian-Wert, der die niedrigen 16-Bit-Werte der unkomprimierten Größe minus eins codiert
• Ein 16-Bit-Big-Endian-Wert, der die komprimierte Größe minus eins codiert
• Ein Eigenschaften / lclppb-Byte, wenn Bit 6 im Steuerbyte gesetzt ist
• Die komprimierten LZMA-Daten, beginnend mit den 5 Bytes (von denen das erste ignoriert wird), die zum Initialisieren des Bereichscodierers verwendet werden (die in der komprimierten Größe enthalten sind)

xz- und 7z-Formate[edit]

Das .xz-Format, das LZMA2-Daten enthalten kann, ist unter dokumentiert tukaani.org,^[10] Das .7z-Dateiformat, das entweder LZMA- oder LZMA2-Daten enthalten kann, ist in der Datei 7zformat.txt dokumentiert, die im LZMA-SDK enthalten ist.^[11]

Details zum Komprimierungsalgorithmus[edit]

Ähnlich wie in der Situation des Dekomprimierungsformats scheint keine vollständige Spezifikation der Codierungstechniken in 7-zip oder xz in natürlicher Sprache zu existieren, außer der im folgenden Text versuchten.

Die folgende Beschreibung basiert auf dem XZ for Java-Encoder von Lasse Collin,^[12] Dies scheint unter mehreren Umschreibungen des ursprünglichen 7-zip mit denselben Algorithmen am besten lesbar zu sein: Auch wenn das Zitieren des Quellcodes als Referenz nicht ideal ist, sollte jeder Programmierer in der Lage sein, die folgenden Ansprüche mit ein paar Stunden Arbeit zu überprüfen .

Bereichsgeber[edit]

Der Entfernungscodierer kann keine interessanten Entscheidungen treffen und kann leicht basierend auf der Decodiererbeschreibung konstruiert werden.

Initialisierung und Beendigung sind nicht vollständig festgelegt; Der xz-Encoder gibt 0 als erstes Byte aus, das vom Dekomprimierer ignoriert wird, und codiert die Untergrenze des Bereichs (der für die letzten Bytes von Bedeutung ist).

Der xz-Encoder verwendet eine vorzeichenlose 33-Bit-Variable namens niedrig (normalerweise als 64-Bit-Ganzzahl implementiert, auf 0 initialisiert), eine vorzeichenlose 32-Bit-Variable namens Angebot (initialisiert auf 2³² – 1), eine vorzeichenlose 8-Bit-Variable namens Zwischenspeicher (auf 0 initialisiert) und eine vorzeichenlose Variable namens cache_size Dies muss groß genug sein, um die unkomprimierte Größe zu speichern (initialisiert auf 1, normalerweise als 64-Bit-Ganzzahl implementiert).

Das Zwischenspeicher/.cache_size Variablen werden verwendet, um Übertragungen richtig zu handhaben, und stellen eine Zahl dar, die durch eine Big-Endian-Sequenz definiert ist, die mit dem beginnt Zwischenspeicher Wert und gefolgt von cache_size 0xff Bytes, die aus dem verschoben wurden niedrig registrieren, wurde aber noch nicht geschrieben, da es aufgrund eines Übertrags um eins erhöht werden könnte.

Beachten Sie, dass die erste Byte-Ausgabe immer 0 ist, da Zwischenspeicher und niedrig werden auf 0 initialisiert und die Encoder-Implementierung; Der xz-Decoder ignoriert dieses Byte.

Die Normalisierung erfolgt folgendermaßen:

1. Wenn niedrig ist kleiner als (2 ^ 32 – 2 ^ 24):
   1. Geben Sie das in gespeicherte Byte aus Zwischenspeicher zum komprimierten Stream
   2. Ausgabe cache_size – 1 Byte mit 0xff-Wert
   3. einstellen Zwischenspeicher zu den Bits 24-31 von niedrig
   4. einstellen cache_size bis 0
2. Wenn niedrig ist größer oder gleich 2 ^ 32:
   1. Geben Sie das in gespeicherte Byte aus Zwischenspeicher plus eins zum komprimierten Stream
   2. Ausgabe cache_size – 1 Byte mit 0 Wert
   3. einstellen Zwischenspeicher zu den Bits 24-31 von niedrig
   4. einstellen cache_size bis 0
3. Zuwachs cache_size
4. einstellen niedrig auf die niedrigsten 24 Bits von niedrig um 8 Bit nach links verschoben
5. einstellen Angebot zu Angebot um 8 Bit nach links verschoben

Kontextbasierte Bereichskodierung eines Bits mit dem prob Die Wahrscheinlichkeitsvariable geht folgendermaßen vor:

1. Wenn Angebot ist kleiner als 2 ^ 24, führen Sie eine Normalisierung durch
2. einstellen gebunden zum Boden(Angebot / 2 ^ 11) * prob
3. Wenn ein 0-Bit codiert wird:
   1. einstellen Angebot zu gebunden
   2. einstellen prob zu prob + Etage ((2 ^ 11 – prob) / 2 ^ 5)
4. Andernfalls (wenn ein 1-Bit codiert wird):
   1. einstellen Angebot zu Angebot – – gebunden
   2. einstellen niedrig bis niedrig + gebunden
   3. einstellen prob zu prob – Fußboden(prob / 2 ^ 5)

Die Codierung des Bereichs mit fester Wahrscheinlichkeit eines Bits erfolgt folgendermaßen:

1. Wenn Angebot ist kleiner als 2 ^ 24, führen Sie eine Normalisierung durch
2. einstellen Angebot zum Boden(Angebot / 2)
3. Wenn Sie ein 1-Bit codieren:
   1. einstellen niedrig zu niedrig + Angebot

Die Kündigung erfolgt folgendermaßen:

1. Führen Sie die Normalisierung fünfmal durch

Die Bitbaumcodierung wird wie die Decodierung durchgeführt, außer dass Bitwerte eher aus der zu codierenden Eingabe-Ganzzahl als aus dem Ergebnis der Bitdecodierungsfunktionen entnommen werden.

Für Algorithmen, die versuchen, die Codierung mit der kürzesten Post-Range-Codierungsgröße zu berechnen, muss der Codierer auch eine Schätzung davon bereitstellen.

Datenstrukturen für die Wörterbuchsuche[edit]

Der Encoder muss in der Lage sein, Übereinstimmungen im Wörterbuch schnell zu finden. Da LZMA sehr große Wörterbücher (möglicherweise in der Größenordnung von Gigabyte) verwendet, um die Komprimierung zu verbessern, würde das einfache Scannen des gesamten Wörterbuchs dazu führen, dass ein Encoder zu langsam ist, um praktisch verwendet werden zu können. Daher sind ausgefeilte Datenstrukturen erforderlich, um schnelle Übereinstimmungssuchen zu unterstützen.

Hash-Ketten[edit]

Der einfachste Ansatz, “Hash-Ketten” genannt, wird durch eine Konstante N parametrisiert, die entweder 2, 3 oder 4 sein kann, was typischerweise so gewählt wird, dass 2 ^ (8 ×)N.) ist größer oder gleich der Wörterbuchgröße.

Es besteht aus dem Erstellen für jeden k Gleich oder kleiner als N., eine durch Tupel von indizierte Hash-Tabelle k Bytes, wobei jeder der Buckets die letzte Position enthält, an der sich die erste befindet k Bytes, die auf den Hash-Wert gehasht wurden, der diesem Hash-Tabellen-Bucket zugeordnet ist.

Die Verkettung wird durch ein zusätzliches Array erreicht, das für jede Wörterbuchposition die zuletzt gesehene vorherige Position speichert, deren erste N. Bytes-Hash auf den gleichen Wert wie der erste N. Bytes der fraglichen Position.

Längenübereinstimmungen finden N. oder höher wird eine Suche mit dem gestartet N.Hash-Tabelle mit Größe und Fortsetzung der Verwendung des Hash-Ketten-Arrays; Die Suche wird gestoppt, nachdem eine vordefinierte Anzahl von Hash-Kettenknoten durchlaufen wurde oder wenn die Hash-Ketten “umlaufen”, um anzuzeigen, dass der Teil der Eingabe, der im Wörterbuch überschrieben wurde, erreicht wurde.

Übereinstimmungen mit einer Größe von weniger als N. werden stattdessen gefunden, indem einfach die entsprechende Hash-Tabelle betrachtet wird, die entweder die letzte solche Übereinstimmung enthält, falls vorhanden, oder eine Zeichenfolge, die auf denselben Wert hasht; Im letzteren Fall kann der Encoder die Übereinstimmung nicht finden. Dieses Problem wird durch die Tatsache gemildert, dass für entfernte kurze Übereinstimmungen mit mehreren Literalen möglicherweise weniger Bits erforderlich sind und Hash-Konflikte in nahegelegenen Zeichenfolgen relativ unwahrscheinlich sind. Die Verwendung größerer Hash-Tabellen oder sogar direkter Nachschlagetabellen kann das Problem auf Kosten einer höheren Cache-Fehlerrate und damit einer geringeren Leistung verringern.

Beachten Sie, dass alle Übereinstimmungen überprüft werden müssen, um zu überprüfen, ob die tatsächlichen Bytes derzeit an dieser bestimmten Wörterbuchposition übereinstimmen, da der Hashing-Mechanismus nur garantiert, dass zu einem früheren Zeitpunkt Zeichen im Hash-Tabellen-Bucket-Index gehasht wurden (einige Implementierungen möglicherweise nicht einmal garantieren dies, da sie die Datenstrukturen nicht initialisieren).

LZMA verwendet Markov-Ketten, wie “M” in seinem Namen impliziert.

Binäre Bäume[edit]

Der Binärbaum-Ansatz folgt dem Hash-Ketten-Ansatz, außer dass logischerweise ein Binärbaum anstelle einer verknüpften Liste zum Verketten verwendet wird.

Der Binärbaum wird so gepflegt, dass er immer sowohl ein Suchbaum in Bezug auf die lexikografische Reihenfolge des Suffix als auch ein Max-Heap für die Wörterbuchposition ist^[13] (Mit anderen Worten, die Wurzel ist immer die aktuellste Zeichenfolge, und ein Kind kann nicht in jüngerer Zeit als seine übergeordnete Zeichenfolge hinzugefügt worden sein.) Unter der Annahme, dass alle Zeichenfolgen lexikografisch geordnet sind, bestimmen diese Bedingungen den Binärbaum eindeutig (dies ist durch Induktion trivial beweisbar auf die Größe des Baumes).

Da die zu suchende Zeichenfolge und die einzufügende Zeichenfolge identisch sind, können sowohl die Wörterbuchsuche als auch das Einfügen (das Drehen des Baums erforderlich ist) in einem einzigen Baumdurchlauf durchgeführt werden.

Patricia versucht es[edit]

Einige alte LZMA-Encoder unterstützten auch eine Datenstruktur, die auf Patricia-Versuchen basiert. Diese Unterstützung wurde jedoch inzwischen eingestellt, da sie den anderen Optionen unterlegen war.^[13]

LZMA-Encoder[edit]

LZMA-Encoder können frei entscheiden, welche Übereinstimmung ausgegeben werden soll oder ob das Vorhandensein von Übereinstimmungen und Ausgabeliteralen ohnehin ignoriert werden soll.

Die Fähigkeit, die 4 zuletzt verwendeten Entfernungen abzurufen, bedeutet, dass die Verwendung einer Übereinstimmung mit einer Entfernung, die später erneut benötigt wird, im Prinzip global optimal sein kann, auch wenn sie lokal nicht optimal ist, und infolgedessen eine optimale LZMA-Komprimierung erfordert wahrscheinlich die Kenntnis der gesamten Eingabe und erfordert möglicherweise Algorithmen, die zu langsam sind, um in der Praxis verwendet werden zu können.

Aus diesem Grund verwenden praktische Implementierungen in der Regel nicht globale Heuristiken.

Die xz-Encoder verwenden einen Wert namens nice_len (Standard ist 64): Wenn mindestens eine Länge übereinstimmt nice_len gefunden wird, stoppt der Encoder die Suche und gibt sie mit der maximalen Übereinstimmungslänge aus.

Schneller Encoder[edit]

Der XZ Fast Encoder^[14] (abgeleitet vom 7-Zip-Fast-Encoder) ist der kürzeste LZMA-Encoder im xz-Quellbaum.

Es funktioniert so:

1. Führen Sie eine kombinierte Suche und Einfügung in die Wörterbuchdatenstruktur durch
2. Wenn eine wiederholte Entfernung mindestens mit der Länge übereinstimmt nice_len::
   • Geben Sie die am häufigsten verwendete Distanz mit einem REP-Paket aus
3. Wenn mindestens eine Übereinstimmung gefunden wurde nice_len::
   • Geben Sie es mit einem MATCH-Paket aus
4. Stellen Sie die Hauptübereinstimmung auf die längste Übereinstimmung ein
5. Schauen Sie sich die nächste Übereinstimmung jeder Länge in absteigender Längenreihenfolge an und bis kein Ersatz mehr möglich ist:
   • Ersetzen Sie die Hauptübereinstimmung durch eine Übereinstimmung, die ein Zeichen kürzer ist, deren Abstand jedoch weniger als 1/128 der aktuellen Hauptübereinstimmungsentfernung beträgt
6. Setzen Sie die Hauptübereinstimmungslänge auf 1, wenn die aktuelle Hauptübereinstimmung die Länge 2 und den Abstand mindestens 128 hat
7. Wenn eine wiederholte Übereinstimmung gefunden wurde und diese um höchstens 1 Zeichen kürzer ist als die Hauptübereinstimmung:
   • Geben Sie die wiederholte Übereinstimmung mit einem REP-Paket aus
8. Wenn eine wiederholte Übereinstimmung gefunden wurde und diese um höchstens 2 Zeichen kürzer als die Hauptübereinstimmung ist und die Hauptübereinstimmungsentfernung mindestens 512 beträgt:
   • Geben Sie die wiederholte Übereinstimmung mit einem REP-Paket aus
9. Wenn eine wiederholte Übereinstimmung gefunden wurde und diese um höchstens 3 Zeichen kürzer als die Hauptübereinstimmung ist und die Hauptübereinstimmungsentfernung mindestens 32768 beträgt:
   • Geben Sie die wiederholte Übereinstimmung mit einem REP-Paket aus
10. Wenn die Hauptübereinstimmungsgröße weniger als 2 beträgt (oder keine Übereinstimmung vorliegt):
11. Führen Sie eine Wörterbuchsuche nach dem nächsten Byte durch
12. Wenn das nächste Byte um höchstens 1 Zeichen kürzer als die Hauptübereinstimmung ist, der Abstand weniger als das 1/128-fache der Hauptübereinstimmungsentfernung beträgt und die Hauptübereinstimmungslänge mindestens 3 beträgt:
13. Wenn das nächste Byte eine Übereinstimmung hat, die mindestens so lang wie die Hauptübereinstimmung ist und weniger Abstand als die Hauptübereinstimmung hat:
14. Wenn das nächste Byte eine Übereinstimmung hat, die mindestens ein Zeichen länger als die Hauptübereinstimmung ist und so dass 1/128 seiner Entfernung kleiner oder gleich der Hauptübereinstimmungsentfernung ist:
15. Wenn das nächste Byte eine Übereinstimmung hat, die mehr als ein Zeichen länger als die Hauptübereinstimmung ist:
16. Wenn eine wiederholte Übereinstimmung um höchstens 1 Zeichen kürzer ist als die Hauptübereinstimmung:
    • Geben Sie die am häufigsten verwendete Distanz mit einem REP-Paket aus
17. Geben Sie die Hauptübereinstimmung mit einem MATCH-Paket aus

Normaler Encoder[edit]

Der normale XZ-Encoder^[15] (abgeleitet vom normalen 7-Zip-Encoder) ist der andere LZMA-Encoder im xz-Quellbaum, der einen ausgefeilteren Ansatz verwendet, der versucht, die Post-Range-Codierungsgröße der generierten Pakete zu minimieren.

Insbesondere codiert es Teile der Eingabe unter Verwendung des Ergebnisses eines dynamischen Programmieralgorithmus, bei dem die Teilprobleme die annähernd optimale Codierung (die mit minimaler Post-Range-Codierungsgröße) des Teilstrings der Länge L finden, beginnend mit dem zu komprimierenden Byte .

Die Größe des Teils der Eingabe, der in dem dynamischen Programmieralgorithmus verarbeitet wird, wird als das Maximum zwischen der längsten Wörterbuchübereinstimmung und der längsten wiederholten Übereinstimmung an der Startposition bestimmt (die durch die maximale LZMA-Übereinstimmungslänge 273 begrenzt wird); außerdem, wenn ein Spiel länger als nice_len Wird an jedem Punkt in dem gerade definierten Bereich gefunden, stoppt der dynamische Programmieralgorithmus, die Lösung für das Teilproblem bis zu diesem Punkt wird ausgegeben, die nice_lenEine Übereinstimmung in Größe wird ausgegeben, und eine neue Instanz für ein dynamisches Programmierproblem wird am Byte gestartet, nachdem die Übereinstimmung ausgegeben wurde.

Teilproblemkandidatenlösungen werden schrittweise mit Kandidatencodierungen aktualisiert, wobei die Lösung für einen kürzeren Teilstring der Länge L ‘verwendet wird, der mit allen möglichen “Schwänzen” erweitert wird, oder Sätze von 1-3 Paketen mit bestimmten Einschränkungen, die die Eingabe an der Position L’ codieren . Sobald die endgültige Lösung eines Teilproblems gefunden ist, werden der LZMA-Status und die am wenigsten verwendeten Abstände dafür berechnet und dann verwendet, um die Post-Range-Codierungsgrößen seiner Erweiterungen angemessen zu berechnen.

Am Ende der dynamischen Programmieroptimierung wird die gesamte optimale Codierung des längsten betrachteten Teilstrings ausgegeben, und die Codierung wird beim ersten nicht komprimierten Byte fortgesetzt, das noch nicht codiert ist, nachdem der LZMA-Status und die am wenigsten verwendeten Abstände aktualisiert wurden.

Jedes Teilproblem wird um eine Paketsequenz erweitert, die wir “Schwanz” nennen und die mit einem der folgenden Muster übereinstimmen muss:

1. Packung	2. Paket	3. Paket
irgendein
ZÜNDETE	LONGREP[0]
*SPIEL	ZÜNDETE	LONGREP[0]

Der Grund für die Erweiterung nicht nur mit einzelnen Paketen besteht darin, dass Teilprobleme aus Gründen der Leistung und der algorithmischen Komplexität nur die Teilstringlänge als Parameter haben, während ein optimaler dynamischer Programmieransatz auch die zuletzt verwendeten Entfernungen und LZMA erfordern würde Zustand als Parameter; Durch die Erweiterung mit mehreren Paketen kann die optimale Lösung besser angenähert und insbesondere LONGREP besser genutzt werden[0] Pakete.

Die folgenden Daten werden für jedes Teilproblem gespeichert (natürlich sind die gespeicherten Werte für die Kandidatenlösung mit Minimum Preis), wobei mit “Schwanz” auf die Pakete Bezug genommen wird, die die Lösung des kleineren Teilproblems erweitern, die direkt in der folgenden Struktur beschrieben werden:

XZ für Java-Mitgliedsname	Beschreibung
Preis	Zu minimierende Menge: Anzahl der Post-Range-Codierungsbits, die zum Codieren der Zeichenfolge benötigt werden
optPrev	unkomprimierte Größe des Teilstrings, der von allen Paketen außer dem letzten codiert wird
backPrev	-1, wenn das letzte Paket LIT ist, 0-3, wenn es sich um eine Wiederholung mit der zuletzt verwendeten Distanznummer 0–3, 4 + handelt Entfernung wenn es ein MATCH ist (dies ist immer 0, wenn prev1IsLiteral wahr ist, da das letzte Paket nur ein LONGREP sein kann[0] In diesem Fall)
prev1IsLiteral	true, wenn der “Schwanz” mehr als ein Paket enthält (in diesem Fall ist das vor dem letzten eine LIT)
hasPrev2	true, wenn der “Schwanz” 3 Pakete enthält (nur gültig, wenn prev1IsLiteral true ist)
optPrev2	unkomprimierte Größe des Teilstrings, der von allen Paketen außer dem “Schwanz” codiert wird (nur gültig, wenn prev1IsLiteral und hasPrev2 wahr sind)
backPrev2	-1 wenn das erste Paket im “Tail” LIT ist, 0-3 wenn es sich um eine Wiederholung mit der zuletzt verwendeten Distanznummer 0–3, 4 + handelt Entfernung wenn es ein MATCH ist (nur gültig, wenn prev1IsLiteral und hasPrev2 wahr sind)
Wiederholungen[4]	die Werte der 4 zuletzt verwendeten Entfernungen nach den Paketen in der Lösung (berechnet erst, nachdem die beste Teilproblemlösung ermittelt wurde)
Zustand	die LZMA Zustand Wert nach den Paketen in der Lösung (wird erst berechnet, nachdem die beste Teilproblemlösung ermittelt wurde)

Beachten Sie, dass in der XZ for Java-Implementierung die optPrev und backPrev Mitglieder werden wiederverwendet, um eine vorwärts verknüpfte Liste von Paketen als Teil der Ausgabe der endgültigen Lösung zu speichern.

LZMA2 Encoder[edit]

Der XZ LZMA2-Encoder verarbeitet die Eingabe in Chunks (von bis zu 2 MB unkomprimierter Größe oder 64 KB komprimierter Größe, je nachdem, welcher Wert niedriger ist), übergibt jeden Chunk an den LZMA-Encoder und entscheidet dann, ob ein LZMA2 LZMA-Chunk einschließlich der codierten Daten ausgegeben werden soll oder um einen unkomprimierten LZMA2-Block auszugeben, je nachdem, welcher kürzer ist (LZMA wird, wie jeder andere Kompressor, notwendigerweise einige Arten von Daten eher erweitern als komprimieren).

Der LZMA-Status wird nur im ersten Block zurückgesetzt, wenn der Aufrufer eine Änderung der Eigenschaften anfordert und jedes Mal, wenn ein komprimierter Block ausgegeben wird. Die LZMA-Eigenschaften werden nur im ersten Block geändert oder wenn der Aufrufer eine Änderung der Eigenschaften anfordert. Das Wörterbuch wird erst im ersten Block zurückgesetzt.

Obere Codierungsschichten[edit]

Vor der LZMA2-Codierung kann xz abhängig von den bereitgestellten Optionen den BCJ-Filter anwenden, der ausführbaren Code filtert, um relative Offsets durch sich wiederholende absolute zu ersetzen, oder den Delta-Filter, der jedes Byte durch die Differenz zwischen ihm und dem Byte ersetzt N. Bytes davor.

Die parallele Codierung wird durchgeführt, indem die Datei in Blöcke aufgeteilt wird, die auf Threads verteilt sind, und schließlich jede (unter Verwendung beispielsweise der xz-Blockcodierung) separat codiert wird, was zu einem Zurücksetzen des Wörterbuchs zwischen den Blöcken in der Ausgabedatei führt.

7-Zip-Referenzimplementierung[edit]

Die aus 7-Zip extrahierte LZMA-Implementierung ist als LZMA SDK verfügbar. Es war ursprünglich sowohl unter der GNU LGPL als auch unter der Common Public License doppelt lizenziert.^[16] mit einer zusätzlichen Sonderausnahme für verknüpfte Binärdateien, die jedoch von Igor Pavlov am 2. Dezember 2008 mit der Veröffentlichung von Version 4.62 öffentlich zugänglich gemacht wurde.^[11]

LZMA2-Komprimierung, eine verbesserte Version von LZMA,^[17] ist jetzt die Standardkomprimierungsmethode für das .7z-Format, beginnend mit Version 9.30 am 26. Oktober 2012.^[18]

Die Referenz-Open-Source-LZMA-Komprimierungsbibliothek wurde ursprünglich in C ++ geschrieben, jedoch auf ANSI C, C # und Java portiert.^[11] Es gibt auch Python-Bindungen von Drittanbietern für die C ++ – Bibliothek sowie Ports von LZMA zu Pascal, Go und Ada.^{[19][20][21][22]}

Die 7-Zip-Implementierung verwendet mehrere Varianten von Hash-Ketten, Binärbäumen und Patricia-Versuchen als Grundlage für ihren Wörterbuch-Suchalgorithmus.

Zusätzlich zu LZMA implementieren SDK und 7-Zip auch mehrere Vorverarbeitungsfilter, um die Komprimierung zu verbessern. Diese reichen von einfacher Delta-Codierung (für Bilder) bis hin zu BCJ für ausführbaren Code. Es bietet auch einige andere Komprimierungsalgorithmen, die in 7z verwendet werden.

Nur-Dekomprimierungscode für LZMA wird im Allgemeinen auf etwa 5 KB kompiliert, und die während der Dekomprimierung erforderliche RAM-Größe wird hauptsächlich durch die Größe des während der Komprimierung verwendeten Schiebefensters bestimmt. Aufgrund der geringen Codegröße und des relativ geringen Speicheraufwands, insbesondere bei kleineren Wörterbuchlängen, sowie des freien Quellcodes eignet sich der LZMA-Dekomprimierungsalgorithmus gut für eingebettete Anwendungen.

Andere Implementierungen[edit]

Zusätzlich zur 7-Zip-Referenzimplementierung unterstützen die folgenden das LZMA-Format.

• xz: Eine Streaming-Implementierung, die ein gzip-ähnliches Befehlszeilentool enthält, das sowohl LZMA als auch LZMA2 in seinem xz-Dateiformat unterstützt. Es hat seinen Weg in mehrere Software der Unix-ähnlichen Welt mit seiner hohen Leistung (im Vergleich zu bzip2) und geringen Größe (im Vergleich zu gzip) gefunden.^[2] Das Linux-Kernel-, dpkg- und RPM-System enthält xz-Code und viele Software-Distributoren wie kernel.org, Debian^[23] und Fedora verwenden jetzt xz zum Komprimieren ihrer Releases.
• lzip: Eine weitere LZMA-Implementierung, die hauptsächlich für Unix-ähnliche Systeme gedacht ist, um direkt mit xz zu konkurrieren.^[24] Es bietet hauptsächlich ein einfacheres Dateiformat und damit eine einfachere Fehlerbehebung.
• ZIPX: Eine Erweiterung des ZIP-Komprimierungsformats, das von WinZip ab Version 12.1 erstellt wurde. Es können auch verschiedene andere Komprimierungsmethoden wie BZip und PPMd verwendet werden.^[25]

LZHAM (LZ, Huffman, Arithmetic, Markov) ist eine LZMA-ähnliche Implementierung, die den Komprimierungsdurchsatz gegen sehr hohe Verhältnisse und einen höheren Dekomprimierungsdurchsatz eintauscht. Es wurde von seinem Autor am 15. September 2020 öffentlich zugänglich gemacht.^[26]

Verweise[edit]

Externe Links[edit]