Lempel-Ziv-Markow-Algorithmus

Kernidee und Bedeutung

Der Lempel-Ziv-Markow-Algorithmus, kurz LZMA, ist ein freier Datenkompressionsalgorithmus. Er wird seit 1998 von Igor Wiktorowitsch Pawlow entwickelt. LZMA erreicht vergleichsweise gute Kompressionsraten und eine hohe Geschwindigkeit beim Entpacken. Der Algorithmus ist nach Abraham Lempel und Jacob Ziv benannt, die den LZ77-Algorithmus entwickelt haben, sowie nach Andrei Andrejewitsch Markow, nach dem die Markow-Ketten benannt wurden.

LZMA arbeitet mit einem Wörterbuchverfahren ähnlich LZ77. Ein Wörterbuchverfahren sucht wiederkehrende Datenmuster und speichert sie nicht jedes Mal vollständig neu, sondern verweist auf frühere Stellen. Dadurch kann LZMA im Prinzip als Weiterentwicklung von Deflate gesehen werden.

Wichtige Eigenschaften

LZMA bietet meist eine sehr gute Kompression, oft besser als bzip2. Die Dekompression, also das Entpacken, ist schnell und etwa doppelt so schnell wie bei bzip2.

Ein wichtiges Merkmal ist die Unterstützung sehr großer Wörterbücher bis zu vier Gigabyte. Außerdem ist LZMA deutlich asymmetrisch: Das Packen braucht viel mehr Aufwand als das Entpacken. Für die Dekompression wird nur ein Bruchteil des Arbeitsspeichers benötigt, der zur Kompression verwendet wurde. Unter Windows werden beim Entpacken etwa 2 MB plus Wörterbuchgröße gebraucht, während der Speicherbedarf beim Packen ein Mehrfaches der Wörterbuchgröße beträgt.

Die Dekompression ist in der Regel etwa 10- bis 20-mal so schnell wie das Komprimieren. Dadurch eignet sich LZMA besonders für Fälle, in denen Daten einmal aufwendig komprimiert, aber oft und schnell wieder entpackt werden sollen.

Arbeitsweise von LZMA und LZMA2

Die Kompression nach dem Lempel-Ziv-Markow-Prinzip wurde als LZMA implementiert und später als LZMA2 weiterentwickelt. LZMA nutzt eine verbesserte Variante des LZ77-Algorithmus, Markow-Ketten und einen Bereichskodierer. Ein Bereichskodierer ist eine Umsetzung des arithmetischen Kodierens und dient der Entropiekodierung, also einer besonders effizienten Darstellung häufigerer und seltenerer Zeichen oder Muster.

LZMA komprimiert Daten linear in einem einzigen Block beziehungsweise Schritt. Deshalb ist die Komprimierung bei LZMA immer auf einen Prozessorkern beschränkt und nicht parallelisierbar. Ein großer Vorteil ist aber, dass der ausführbare Code zum Entpacken typischerweise nur etwa 5 kByte belegt. Der beim Entpacken benötigte Arbeitsspeicher hängt von der Größe des beim Packen erzeugten Wörterbuchs ab. Wegen der kleinen Entpackergröße und des relativ geringen Speicherbedarfs beim Entpacken eignet sich LZMA besonders gut für eingebettete Anwendungen.

In der 7-Zip-Umsetzung werden für die Wörterbuch-Suche verschiedene Varianten von Hash-Knoten, Binärbäumen und Patricia-Tries verwendet.

LZMA2 ist anders entworfen: Es kann mehrere Prozessorkerne gleichzeitig nutzen. Dazu wird die gesamte zu komprimierende Datenmenge in Abschnitte aufgeteilt, die von separaten Prozessen oder Threads komprimiert werden. Auch die spätere Dekompression erfolgt parallel. Bei der Kompression bauen alle Prozesse ein gemeinsames Wörterbuch auf. Die Restdaten der Entropiekodierung werden als separate Datenströme verarbeitet. Die Suboptimalität der Bereichskodierung beträgt unter ein Byte pro Eingangsdatenabschnitt. Jeder erzeugte Block des Komprimats erhält einen minimalen Datenkopf. Dadurch kann das Packen und Entpacken auf Multi-Prozessor- und Multicore-Systemen zum Teil erheblich beschleunigt werden.

Datenstrom und Pakettypen

Bei der LZMA-Komprimierung ist der komprimierte Datenstrom ein Bitstrom, der mit einem adaptiven Binärbereichscodierer codiert wird. Adaptiv bedeutet hier, dass die Wahrscheinlichkeitsvorhersagen während der Verarbeitung an vorherige Daten angepasst werden. Der Datenstrom wird in Pakete aufgeteilt. Jedes Paket beschreibt entweder ein einzelnes Byte oder eine LZ77-Sequenz mit Länge und Entfernung. Die Länge und Entfernung können implizit oder explizit codiert sein.

Es gibt sieben Pakettypen: LIT steht für ein einzelnes Byte. MATCH ist eine typische LZ77-Sequenz mit Länge und Distanz. SHORTREP ist eine 1 Byte lange LZ77-Sequenz, deren Distanz der zuletzt verwendeten LZ77-Distanz entspricht. LONGREP[0], LONGREP[1], LONGREP[2] und LONGREP[3] sind LZ77-Sequenzen, deren Distanz der zuletzt, vorletzt, drittletzt oder viertletzt verwendeten LZ77-Distanz entspricht.

LONGREP[n]-Pakete entfernen die verwendete Distanz aus der Liste der letzten Distanzen und fügen sie vorne wieder ein, damit unnötige Mehrfacheingaben vermieden werden. MATCH fügt die Distanz vorne hinzu, auch wenn sie schon in der Liste vorhanden ist. SHORTREP und LONGREP[0] verändern die Liste nicht.

Die Länge wird in drei Bereichen codiert: Mit der Bitfolge 0 plus 3 Bit ergibt sich ein Längenbereich von 2 bis 9. Mit 1+0 plus 3 Bit ergibt sich ein Bereich von 10 bis 17. Mit 1+1 plus 8 Bit ergibt sich ein Bereich von 18 bis 273. Wie bei LZ77 ist die Länge nicht durch die Distanz begrenzt, weil das Kopieren aus dem Wörterbuch so definiert ist, als würde Byte für Byte mit konstanter Distanz kopiert. Distanzen sind logisch 32 Bit lang, und Distanz 0 zeigt auf das zuletzt im Wörterbuch hinzugefügte Byte.

Einsatz und Dateiformate

LZMA wird nicht nur in speziellen Dateiformaten für komprimierte Daten verwendet, sondern ist auch in viele andere Systeme integriert. Bei der transparenten Kompression und Dekompression ausführbarer Dateien steht LZMA zum Beispiel in UPX ab Version 2.92 beta oder Upack zur Wahl. Auch komprimierende Dateisysteme wie SquashFS oder CramFS mit entsprechenden Patches können LZMA nutzen.

Viele Linux-Distributionen unterstützen oder unterstützten LZMA-komprimierte Installationspakete, darunter Arch Linux seit März 2010, seit 2020 allerdings Zstandard, Quelltextpakete von Gentoo Linux, Slackware Linux seit 8. Mai 2009, openSUSE seit dem 27. März 2008, Pardus’ Paketverwaltung und das Debian-Paketverwaltungssystem. Unter Windows können Installationssysteme wie das Nullsoft Scriptable Install System und Inno Setup selbstentpackende Archivdateien erstellen, die mit LZMA komprimiert sein können.

Ursprünglich konnte LZMA nur mit dem neuen 7z-Format von 7-Zip genutzt werden. Später kamen weitere Formate hinzu. Für xz wurde ein neues Format speziell im Hinblick auf LZMA-Unterstützung geschaffen; Ähnliches gilt für lzip. Beim neuen ALZip-Format mit .egg-Dateien wurde im Rahmen eines Kompatibilitätsbruches ein moderneres und flexibleres Dateiformat geschaffen, das nun hauptsächlich mit LZMA-komprimierten Inhalten verwendet wird. Bei Zip2, zum Beispiel mit WinZip ab Version 12.0 oder 7-Zip ab Version 4.61 beta, wurde einem bestehenden erweiterbaren Format LZMA-Unterstützung hinzugefügt.

Software und Entwicklung

Die Referenzimplementierung von LZMA ist freie Software. Sie erschien zuerst in Form der 7-Zip-Programme und wird heute auch getrennt als LZMA SDK veröffentlicht. Die freie Referenzbibliothek zur LZMA-Kompression wurde in C++ geschrieben und unterstützt Multithreading.

Für Unix-ähnliche Plattformen gibt es drei funktionierende Übertragungen: p7zip ist eine aktuelle Portierung des Kommandozeilenwerkzeugs 7z und unterstützt das 7z-Archivformat vollständig. lzip war die erste LZMA-Lösung für Unix-ähnliche Betriebssysteme, die das vertraute Konzept von gzip vollständig kopierte. XZ Utils sind eine Portierung des LZMA-Codes von 7-Zip und bieten unter Linux für die LZMA-Packmethode eine weitgehend ähnliche Handhabung wie gzip und bzip2, unterstützen aber keine 7z-Archive. GRUB2 verwendet seit Juli 2008 standardmäßig LZMA statt des früher verwendeten LZO, zunächst nur für i386-PC.

Die Referenzimplementierung 7-Zip wurde im Jahr 2000 veröffentlicht. Der Quellcode des LZMA-SDK ist seit dem 23. November 2008, Version 4.61 beta, gemeinfrei, also public domain. Mit Version 9.04 beta von 7-Zip wurde am 30. Mai 2009 LZMA2 eingeführt. Diese Variante unterstützt Multithreading besser und verbessert die Behandlung nicht komprimierbarer Inhalte.

Auf Unix-Plattformen wurde LZMA erstmals 2004 durch p7zip nutzbar. Im selben Jahr erschien auch das portablere LZMA-SDK mit dem Programm lzma_alone, das ähnlich wie gzip oder bzip2 zusammen mit tar verwendet wurde, um Datei-Metadaten und Rechteinformationen aus Unix-Systemen aufzunehmen. Später entstanden LZMA Utils und daraus XZ Utils. 2008 veröffentlichte Antonio Diaz lzip, das statt des rohen LZMA-Datenstroms ein Containerformat mit Prüfsummen und Magischen Zahlen bot. Die XZ Utils scheinen sich inzwischen als LZMA-Implementierung für Unix-ähnliche Plattformen durchzusetzen; ihr xz-Dateiformat wird auch von den Referenzimplementierungen unterstützt.