Lempel-Ziv-Markow chain-Algorithm

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 nach Andrei Andrejewitsch Markow, nach dem die Markow-Ketten benannt wurden.

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 als urheberrechtsfrei (public domain) 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 eine aktuelle Portierung 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 wie beispielsweise Karchiver und WinRAR.
• 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, welche keine 7z-Archive unterstützen. LZMA Utils verwendet aber im Gegensatz zu p7zip meist eine ältere Version des LZMA-Codes.

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
• Upack
• UPX unterstützt seit Version 2.92 (beta) optional LZMA-Kompression
• GRUB2 verwendet seit Juli 2008 standardmäßig nicht mehr LZO, sondern LZMA (vorerst aber nur für i386-pc).
• WinZip unterstützt seit Version 12.0 LZMA als Kompressionsmethode für Zip-Archive
• 7-Zip unterstützt seit Version 4.61 (beta) LZMA als Kompressionsmethode für Zip-Archive
• Gentoo Linux verwendet LZMA-Packages in welchen der SourceCode der Metadistribution enthalten ist
• Karchiver mit p7zip als Unterbau

Weblinks

• 7-Zip-Website
• p7zip-Website
• PyLZMA-Website
• Unix Werkzeug XZ Utils (alter Name: LZMA Utils)