imported>SchlurcherBot: Bot: http → https

2025-12-05T21:23:13Z

Bot: http → https

Neue Seite

Der '''Lempel-Ziv-Markow-Algorithmus''' ('''LZMA''') ist ein [[Freie Software|freier]] [[Datenkompression]]salgorithmus, der von Igor Wiktorowitsch Pawlow 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 (Mathematiker, 1856)|Andrei Andrejewitsch Markow]], nach dem die [[Markow-Kette]]n benannt wurden.

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

== Merkmale ==
* Sehr gute Kompression (meist besser als [[bzip2]])
* Schnelle Dekompression (etwa doppelt so schnell wie bzip2)
* Es werden sehr große Wörterbücher unterstützt (bis zu vier Gigabyte)
* ausgeprägte Asymmetrie
** Für die Dekompression (Entpacken) wird nur ein Bruchteil des zur Kompression (Packen) verwendeten Arbeitsspeichers benötigt (unter [[Microsoft Windows|Windows]] etwa 2 MB + Wörterbuchgröße) während der Bedarf an Arbeitsspeicher 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.

== Funktionsweise ==
Die Kompression anhand von Lempel-Ziv-Markow wurde als LZMA implementiert und als LZMA2 weiterentwickelt.

LZMA nutzt eine verbesserte Variante des [[LZ77]]-Algorithmus, [[Markow-Kette]]n und einen [[Bereichskodierung|Bereichskodierer]] (eine Umsetzung [[Arithmetisches Kodieren|arithmetischen Kodierens]]) zur [[Entropiekodierung]].

LZMA komprimiert die Daten linear in einem einzigen Block bzw. Schritt. Hierdurch ist die Komprimierung durch LZMA immer auf einen Prozessorkern beschränkt, d. h., LZMA ist nicht parallelisierbar.

Der wesentliche Vorteil von LZMA ist, dass der ausführbare Code zum Entpacken von LZMA-komprimierten Daten typischerweise nur etwa 5 kByte belegt. Die beim Entpacken benötigte Menge Arbeitsspeicher hängt von der Größe des beim Packen erzeugten Wörterbuchs ab.
Durch die geringe Entpackergröße und den recht geringen Speicherbedarf beim Entpacken (besonders mit kleineren Wörterbüchern) eignet sich das Verfahren besonders gut für [[Eingebettetes System|eingebettete]] Anwendungen.

In der [[7-Zip]]-Umsetzung werden verschiedene Varianten von [[Hashfunktion|Hash-Knoten]], [[Binärbaum|Binärbäumen]] und [[Patricia-Trie]]s für die Wörterbuch-Suche genutzt.

LZMA2 sieht im Gegensatz zu LZMA per Entwurf die gleichzeitige Ausführung auf mehreren Prozessorkernen vor. Hierzu teilt LZMA2 die gesamte zu komprimierende Datenmenge in Abschnitte auf, die jeweils von separaten Prozessen, bzw. Threads komprimiert werden. Die spätere Dekompression erfolgt ebenfalls parallel. Bei der Kompression bauen alle Prozesse ein gemeinsames Wörterbuch auf. Die Restdaten der Entropiekodierung werden zwangsläufig 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.<ref name="LZMA2">https://sourceforge.net/projects/sevenzip/forums/forum/45797/topic/2965956</ref> Durch die mögliche Parallelisierung wird das Packen und Entpacken auf Multi-Prozessor- und Multicore-Systemen z. T. erheblich beschleunigt.

Bei der LZMA-Komprimierung ist der komprimierte Datenstrom ein [[Bitstrom]], der mit einem adaptiven Binärbereichscodierer codiert wird. Der [[Datenstrom]] wird in [[Datenpaket|Pakete]] aufgeteilt, wobei jedes Paket entweder ein einzelnes Byte oder eine [[LZ77]]-Sequenz mit implizit oder explizit codierter Länge und Entfernung beschreibt. Jeder Teil jedes Pakets wird mit unabhängigen Kontexten modelliert, sodass die Wahrscheinlichkeitsvorhersagen für jedes Bit mit den Werten dieses Bits und verwandter Bits aus demselben Feld in vorherigen Paketen desselben Typs korreliert werden. Sowohl die [[lzip]] als auch die LZMA-SDK-Dokumentation beschreiben dieses Datenstromformat.

Es gibt 7 Pakettypen:
{| class="wikitable" border="1"
!Bitsequenz
!Paketname
!Paketbeschreibung
|-
|0 + Bytecode
|LIT
|Ein einzelnes Byte, das mit einem adaptiven Binärbereichscodierer codiert wurde.
|-
|1+0 + Länge + Distanz
|MATCH
|Eine typische LZ77-Sequenz mit Beschreibung der Länge und Distanz.
|-
|1+1+0+0
|SHORTREP
|Eine 1 Byte lange LZ77-Sequenz. Die Distanz entspricht der zuletzt verwendeten LZ77-Distanz.
|-
|1+1+0+1 + Länge
|LONGREP[0]
|Eine LZ77-Sequenz. Die Distanz entspricht der zuletzt verwendeten LZ77-Distanz.
|-
|1+1+1+0 + Länge
|LONGREP[1]
|Eine LZ77-Sequenz. Die Distanz entspricht der vorletzten verwendeten LZ77-Distanz.
|-
|1+1+1+1+0 + Länge
|LONGREP[2]
|Eine LZ77-Sequenz. Die Distanz entspricht der drittletzten verwendeten LZ77-Distanz.
|-
|1+1+1+1+1 + Länge
|LONGREP[3]
|Eine LZ77-Sequenz. Die Distanz entspricht der viertletzten verwendeten LZ77-Distanz.
|}
LONGREP[n]-Pakete entfernen die verwendete Distanz aus der Liste der letzten Distanzen und fügen sie vorne wieder ein, um unnötige Mehrfacheingaben zu vermeiden, während MATCH die Distanz auch dann einfach vorne hinzufügt, wenn sie bereits in der Liste vorhanden ist, und SHORTREP und LONGREP[0] die Liste nicht ändern.

Die Länge wird wie folgt kodiert:
{| class="wikitable" border="1"
!Bitsequenz
!Beschreibung
|-
|0+ 3 Bit
|Die mit 3 Bit codierte Länge ergibt einen Längenbereich von 2 bis 9.
|-
|1+0+ 3 Bit
|Die mit 3 Bit codierte Länge ergibt einen Längenbereich von 10 bis 17.
|-
|1+1+ 8 Bit
|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 Distanz begrenzt, da das Kopieren aus dem Wörterbuch so definiert ist, als ob das Kopieren Byte für Byte durchgeführt würde, wobei die Distanz konstant bleibt. Distanzen sind logisch 32 Bit lang und Distanz 0 zeigt auf das zuletzt im Wörterbuch hinzugefügte Byte. Die Distanzkodierung beginnt mit einem 6-Bit-Distanzschlitz, der bestimmt, wie viele weitere Bits benötigt werden. Distanzen werden als binäre Verkettung von zwei Bits, von höchstwertig bis niedrigstwertig, je nach Distanzschlitz dekodiert, wobei einige Bits mit einer festen Wahrscheinlichkeit von 0,5 kodiert werden und einige kontextkodierte Bits gemäß der folgenden Tabelle:<ref>{{Internetquelle |url=https://www.7-zip.org/sdk.html |titel=LZMA SDK (Software Development Kit) |abruf=2024-12-02}}</ref><ref>{{Internetquelle |url=https://www.nongnu.org/lzip/manual/lzip_manual.html#Stream-format |titel=Lzip Manual |abruf=2024-12-02}}</ref>
{| class="wikitable" border="1"
!6 Bit Distanzschlitz
!höchste 2 Bits
!feste 0.5 Wahrscheinlichkeitsbits
!kontextkodierte 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
|((slot / 2) − 5)
|4
|-
|15–63 (ungerade)
|11
|(((slot − 1) / 2) − 5)
|4
|}

== Einsatz ==
Neben dem Einsatz mit speziellen Dateiformaten für komprimierte Daten wurde LZMA-Unterstützung auch in viele andere Systeme integriert. So steht bei der transparenten Kompression und Dekompression ausführbarer Dateien mit [[UPX]] (ab Version 2.92, beta) oder [[Upack]] und bei komprimierenden Dateisystemen wie [[SquashFS]] (oder [[CramFS]], mit entsprechenden Patches) auch der LZMA zur Wahl.
Bei einer großen Anzahl von Linux-Distributionen ([[Arch Linux]] seit März 2010<ref>Pierre Schmitz: [https://www.archlinux.org/news/switching-to-xz-compression-for-new-packages/ ''Switching to xz compression for new packages''] archlinux.org, 23. März 2010.</ref> (seit 2020 allerdings [[Zstandard]]), [[Quelltext]]pakete der Distribution [[Gentoo Linux]], [[Slackware Linux]] seit 8. Mai 2009, [[openSUSE]] seit dem 27. März 2008, [[Pardus (Linux-Distribution)#Paketverwaltung PiSi|Pardus’ Paketverwaltung]] und das [[Debian-Paketverwaltung]]ssystem bieten Unterstützung, …) können mittlerweile LZMA-komprimierte Installationspakete verwendet werden. Auch Software-Installationssysteme für Windows wie das [[Nullsoft Scriptable Install System]] und [[Inno Setup]] erstellen eine Art erweiterter [[Selbstextrahierendes Archiv|selbstentpackender Archivdateien]], die mit LZMA komprimiert sein können.

=== Dateiformate ===
Ursprünglich konnte es nur mit dem neuen [[7z]]-Format von 7-Zip genutzt werden. Mittlerweile stehen einige weitere Formate zur Verfügung.
Im Falle von [[xz]] wurde extra im Hinblick auf LZMA-Unterstützung ein neues Format geschaffen, das speziell für die ausschließliche Verwendung mit LZMA vorgesehen ist (ähnliches gilt auch für das [[lzip]]-Format). Im Falle des neuen [[ALZip]]-Formates (<code>.egg</code>-Dateien) ist im Zuge einer mit der Verfügbarkeit modernerer Verfahren angezeigten Modernisierung der Dateiformatfähigkeiten im Rahmen eines Kompatibilitätsbruches beim Format ein neues, moderneres (flexibleres) Dateiformat geschaffen worden, das nun hauptsächlich mit LZMA-komprimierten Inhalten verwendet wird.
Im Falle von [[ZIP-Dateiformat|Zip]]2 (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 ===
Die Referenzimplementierung von LZMA ist in freier Software erfolgt. Sie kam zunächst in Form der 7-Zip-Programme und wird mittlerweile auch isoliert in Form des LZMA SDK veröffentlicht.
Die freie Referenzbibliothek zur LZMA-Kompression wurde in [[C++]] geschrieben und unterstützt [[Multithreading]].

Zurzeit gibt es drei 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]].
* [[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, 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.

Weiterhin verwendet [[GRUB]]2 seit Juli 2008 standardmäßig LZMA anstatt des früher verwendeten [[Lempel-Ziv-Oberhumer|LZO]] (vorerst aber nur für i386-PC).

== Geschichte ==
* 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) [[Gemeinfreiheit|gemeinfrei]] (englisch „public domain“) veröffentlicht.
* Mit Version 9.04 beta von 7-Zip wurde am 30. Mai 2009 der Algorithmus ''LZMA2'' eingeführt, der eine geringfügig veränderte Variante des ursprünglichen Algorithmus darstellt, die [[Multithreading]] besser unterstützt und die Behandlung von nicht komprimierbaren Inhalten verbessert.<ref name="LZMA2" /><ref>http://sevenzip.sourceforge.jp/chm/cmdline/switches/method.htm#LZMA2</ref>

=== Unix-Plattformen ===
Da im Quelltext von 7-Zip ausgedehnter Gebrauch von Windows-spezifischen Eigenschaften gemacht wird, verging nach dessen Erstveröffentlichung einige Zeit bis zum Erscheinen einer [[Unix]]-kompatiblen Version, obwohl es sich um freie Software handelt.
LZMA wurde erstmals 2004 mit einem Port der Kommandozeilenversion von 7-Zip namens p7zip auf Unix-Plattformen nutzbar.
Im selben Jahr wurde auch das (wesentlich portablere) LZMA-SDK verfügbar, bei dem das Kommandozeilenprogramm „lzma_alone“ enthalten ist. lzma_alone wurde ähnlich gzip oder bzip2 mit tar zusammen verwendet, um Datei-Metadaten und Rechteinformationen aus Unix-Datei- und Betriebssystemen aufnehmen zu können. Weniger als ein Jahr nach der Erstveröffentlichung des LZMA SDK veröffentlichte Lasse Collin die LZMA Utils, die (zunächst nur aus einem Satz [[Wrapper (Software)|Wrapper]]-Skripte bestehend) eine für Unix-Nutzer vertraute (gzip-ähnliche) Benutzerschnittstelle zu lzma_alone schuf.

2008 veröffentlichte Antonio Diaz lzip, welches anstatt des rohen LZMA-Datenstromes ein [[Containerformat]] mit Prüfsummen und [[Magische Zahl (Informatik)|Magischen Zahlen]] bot. Damit war eine vollständige Lösung zur Nutzung von LZMA in Unix-Manier gegeben, die sich allerdings nur teilweise durchsetzen konnte, bevor die LZMA Utils entsprechend weiterentwickelt wurden und nun unter dem Namen „XZ Utils“ ähnliches boten.<ref>{{Literatur |Autor=Brian Lindholm |Titel=New Options in the World of File Compression |Sammelwerk=Linux Gazette |Nummer=162 |Datum=2009-05 |Sprache=en|Online=https://linuxgazette.net/162/lindholm.html |Abruf=2011-01-07}}</ref> Die XZ Utils scheinen sich nun als LZMA-Implementierung für Unix-ähnliche Plattformen durchzusetzen. Ihr [[xz]]-Dateiformat wird nun auch von den Referenzimplementierungen unterstützt.

== Weblinks ==
* [http://www.7-zip.de/sdk.html offizielle Website]
* [https://p7zip.sourceforge.net/ p7zip-Website]
* [https://www.joachim-bauch.de/projects/python/pylzma PyLZMA-Website]

== Quellen ==
<references />

[[Kategorie:Freie Datenkompressionssoftware]]
[[Kategorie:Kompressionsalgorithmus]]

Lempel-Ziv-Markow-Algorithmus - Versionsgeschichte

imported>SchlurcherBot: Bot: http → https