Lempel-Ziv-Markow-Algorithmus

Lempel-Ziv-Markow-Algorithmus (LZMA) ist ein freier Datenkompressionsalgorithmus, der von Igor Pavlov seit 1998 entwickelt wird und vergleichsweise gute Kompressionsraten und eine hohe Geschwindigkeit beim Entpacken erreicht. Er ist benannt nach Abraham Lempel und Jacob Ziv, die den LZ77-Algorithmus entwickelt haben und Andrei Andrejewitsch Markow für die Markow-Ketten.

Der Algorithmus arbeitet mit einem Wörterbuchverfahren ähnlich LZ77 und kann damit im Prinzip als Weiterentwicklung von Deflate gesehen werden.

Merkmale

• Sehr gute Kompression (durchschnittlich besser als bzip2)
• Schnelle Dekompression – etwa 10 bis 20-Mal schneller als das Komprimieren (etwa zweimal schneller als bzip2)
• Es werden sehr große Wörterbücher unterstützt (bis zu einem Gigabyte)
• Der Bedarf an Arbeitsspeicher beim Packen beträgt ein Mehrfaches der Wörterbuchgröße
• Für die Dekompression wird nur ein Bruchteil des zur Kompression verwendeten Arbeitsspeichers benötigt (unter Windows etwa 2 MB + Wörterbuchgröße)

Technik

LZMA nutzt eine verbesserte Variante des LZ77-Algorithmus, Markow-Ketten und einen Bereichskodierer (eine Umsetzung arithmetischen Kodierens) zur Entropiekodierung.

Der Code zum Entpacken von LZMA belegt in kompilierter Form üblicherweise nur etwa 5 KB. Die beim Entpacken benötigte Menge Arbeitsspeicher hängt von der Größe des beim Packen verwendeten Wörterbuchs ab. Durch die geringe Entpackergröße und den recht geringen Speicherbedarf (besonders mit kleineren Wörterbüchern) eignet sich das Verfahren besonders gut für eingebettete Anwendungen.

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

Referenzimplementation

Die Referenzimplementation von LZMA ist als Teil des 7z-Formates in den 7-Zip-Programmen und dem LZMA-SDK erfolgt. Deren Quellcode ist unter anderem als freie Software unter den Bedingungen der LGPL veröffentlicht.

Die quelloffene Referenzbibliothek zur LZMA-Kompression wurde in C++ geschrieben und unterstützt Multithreading.

Portabilität der Referenzimplementation

Im Quelltext wird ausgedehnter Gebrauch Windows-spezifischer Eigenschaften gemacht, sodass bis zum Erscheinen einer Unix-kompatiblen Version einige Zeit verging, obwohl es sich um ein freies Programm handelt.

Zur Zeit gibt es zwei funktionierende Übertragungen auf Unix-ähnliche Plattformen:

• p7zip ist ein Port des Kommandozeilenwerkzeugs 7z, bietet also vollständige Unterstützung des 7z-Archivformates und dient oft als Unterbau für die 7z-Funktionen graphischer Werkzeuge mit 7z-Unterstützung.
• LZMA Utils sind eine Portierung des LZMA-Codes von 7-Zip, die unter Linux für die LZMA-Packmethode eine weitgehend gleiche Handhabung wie die etablierten gzip und bzip2 bieten. Sie unterstützen keine 7z-Archive.

Einsatz

Neben dem 7z-Archivformat wird LZMA von folgenden Programmen genutzt oder unterstützt:

• Nullsoft Scriptable Install System
• Inno Setup
• CramFS und SquashFS – mit eingespielten Patches
• lrzip (long range zip, oder LZMA rzip)
• PyLZMA, eine Python-Schnittstelle zu Igor Pavlovs LZMA-SDK
• FreeArc, ein Packer und Haskell-Schnittstelle zum LZMA-SDK
• LZMA-SDK für Pascal
• CompreXX, mit Explorer-Einbettung ähnlich Windows XPs ZIP-komprimierte Ordner (Shareware)
• InstallAware für den Windows Installer
• PeaZip, eine graphische Oberfläche für das 7z-Kommandozeilenprogramm und die POSIX-7z-Versionen (p7zip)
• Upack
• UPX unterstützt seit Version 2.92 (beta) optional LZMA-Kompression

Weblinks

• 7-Zip-Website
• p7zip-Website
• PyLZMA-Website