Lempel-Ziv-Markow-Algorithmus: Unterschied zwischen den Versionen
Zur Navigation springen
Zur Suche springen
Dbt (Diskussion | Beiträge) K (1 Versionen) |
Dbt (Diskussion | Beiträge) (Wenn schon dann auch zu LZMA eine "kleine" Erläuterung ;-) |
||
| Zeile 1: | Zeile 1: | ||
'''Lempel-Ziv-Markow-Algorithmus''' ('''LZMA''') ist ein [[freie Software|freier]] | == Allgemein == | ||
'''Lempel-Ziv-Markow-Algorithmus''' ('''LZMA''') ist ein [[WP:freie Software|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 [[WP:Abraham Lempel|Abraham Lempel]] und [[WP:Jacob Ziv|Jacob Ziv]], die den LZ77-Algorithmus entwickelt haben und [[WP:Andrei Andrejewitsch Markow|Andrei Andrejewitsch Markow]] für die Markow-Ketten. Der Algorithmus arbeitet mit einem [[WP:Wörterbuchkompression|Wörterbuchverfahren]] ähnlich LZ77 und kann damit im Prinzip als Weiterentwicklung von [[WP:Deflate|Deflate]] gesehen werden. Auch das [[Tuxbox]]-Projekt verwendet LZMA in aktuellen [[SquashFS]]-[[Images]]. | |||
Der Algorithmus arbeitet mit einem [[Wörterbuchkompression|Wörterbuchverfahren]] ähnlich | |||
== Merkmale == | == Merkmale == | ||
* Sehr gute Kompression (durchschnittlich besser als [[bzip2]]) | * Sehr gute Kompression (durchschnittlich besser als [[WP:bzip2|bzip2]]) | ||
* Schnelle Dekompression – etwa 10 bis 20-Mal schneller als das Komprimieren (etwa zweimal schneller als [[bzip2]]) | * Schnelle Dekompression – etwa 10 bis 20-Mal schneller als das Komprimieren (etwa zweimal schneller als [[WP:bzip2|bzip2]]) | ||
* Es werden sehr große Wörterbücher unterstützt (bis zu einem Gigabyte) | * 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 | * 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 [[Microsoft Windows|Windows]] etwa 2 MB + Wörterbuchgröße) | * Für die Dekompression wird nur ein Bruchteil des zur Kompression verwendeten Arbeitsspeichers benötigt (unter [[WP:Microsoft Windows|Windows]] etwa 2 MB + Wörterbuchgröße) | ||
== Technik == | == Technik == | ||
LZMA nutzt eine verbesserte Variante des [[LZ77]]-Algorithmus, | LZMA nutzt eine verbesserte Variante des [[WP:LZ77|LZ77]]-Algorithmus, Markow-Ketten und einen [[WP:Bereichskodierung|Bereichskodierer]] (eine Umsetzung [[WP:arithmetisches Kodieren|arithmetischen Kodieren]]s) zur [[WP:Entropiekodierung|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. | 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 [[eingebettetes System|eingebettete]] Anwendungen. | Durch die geringe Entpackergröße und den recht geringen Speicherbedarf (besonders mit kleineren Wörterbüchern) eignet sich das Verfahren besonders gut für [[WP:eingebettetes System|eingebettete]] Anwendungen. | ||
In der [[7-Zip]]-Umsetzung werden verschiedene Varianten von [[Hash-Funktion|Hash-Knoten]], [[Binärbaum|Binärbäumen]] und [[Patricia-Trie]]s für die Wörterbuch-Suche genutzt. | In der [[WP:7-Zip|7-Zip]]-Umsetzung werden verschiedene Varianten von [[WP:Hash-Funktion|Hash-Knoten]], [[WP:Binärbaum|Binärbäumen]] und [[WP:Patricia-Trie|Patricia-Trie]]s für die Wörterbuch-Suche genutzt. | ||
== Referenzimplementation == | == 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 [[ | Die Referenzimplementation von LZMA ist als Teil des [[WP:7z|7z]]-Formates in den 7-Zip-Programmen und dem LZMA-SDK erfolgt. Deren Quellcode ist unter anderem als [[WP:freie Software|freie Software]] unter den Bedingungen der [[WP:LGPL|LGPL]] veröffentlicht. | ||
Die [[Open Source|quelloffen]]e Referenzbibliothek zur LZMA-Kompression wurde in [[C++]] geschrieben und unterstützt [[Multithreading]]. | Die [[WP:Open Source|quelloffen]]e Referenzbibliothek zur LZMA-Kompression wurde in [[WP:C++|C++]] geschrieben und unterstützt [[WP:Multithreading|Multithreading]]. | ||
=== Portabilität der Referenzimplementation === | === Portabilität der Referenzimplementation === | ||
| Zeile 27: | Zeile 26: | ||
Zur Zeit gibt es zwei funktionierende Übertragungen auf Unix-ähnliche Plattformen: | 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. | * [[WP:p7zip|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. | * [[WP:LZMA Utils|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 [[WP:gzip|gzip]] und [[WP:bzip2|bzip2]] bieten. Sie unterstützen keine 7z-Archive. | ||
== Einsatz == | == Einsatz == | ||
Neben dem [[7z]]-Archivformat wird LZMA von folgenden Programmen genutzt oder unterstützt: | Neben dem [[WP:7z|7z]]-Archivformat wird LZMA von folgenden Programmen genutzt oder unterstützt: | ||
* [[Cramfs]] und [[SquashFS]] – mit eingespielten Patches | |||
* [[ | * [http://ck.kolivas.org/apps/lrzip/ lrzip] (''long range zip'', oder ''LZMA [[WP:rzip|rzip]]'') | ||
* [http://ck.kolivas.org/apps/lrzip/ lrzip] (''long range zip'', oder ''LZMA [[rzip]]'') | * [http://www.joachim-bauch.de/projects/python/pylzma PyLZMA], eine [[WP:Python (Programmiersprache)|Python]]-Schnittstelle zu Igor Pavlovs LZMA-SDK | ||
* [http://www.joachim-bauch.de/projects/python/pylzma PyLZMA], eine [[Python (Programmiersprache)|Python]]-Schnittstelle zu Igor Pavlovs LZMA-SDK | * [http://freearc.narod.ru/ FreeArc], ein Packer und [[WP:Haskell (Programmiersprache)|Haskell]]-Schnittstelle zum LZMA-SDK | ||
* [http://freearc.narod.ru/ FreeArc], ein Packer und [[Haskell (Programmiersprache)|Haskell]]-Schnittstelle zum LZMA-SDK | * [http://www.birtles.org.uk/programming/ LZMA-SDK] für [[WP:Pascal (Programmiersprache)|Pascal]] | ||
* [http://www.birtles.org.uk/programming/ LZMA-SDK] für [[Pascal (Programmiersprache)|Pascal]] | |||
* [http://www.comprexx.com/ CompreXX], mit Explorer-Einbettung ähnlich Windows XPs ZIP-komprimierte Ordner (Shareware) | * [http://www.comprexx.com/ CompreXX], mit Explorer-Einbettung ähnlich Windows XPs ZIP-komprimierte Ordner (Shareware) | ||
* [http://www.installaware.com/ InstallAware] für den Windows Installer | * [http://www.installaware.com/ InstallAware] für den Windows Installer | ||
* [http://sourceforge.net/projects/peazip/ PeaZip], eine graphische Oberfläche für das 7z-Kommandozeilenprogramm und die POSIX-7z-Versionen ([[p7zip]]) | * [http://sourceforge.net/projects/peazip/ PeaZip], eine graphische Oberfläche für das 7z-Kommandozeilenprogramm und die POSIX-7z-Versionen ([[WP:p7zip|p7zip]]) | ||
* [[Upack]] | * [[WP:Upack|Upack]] | ||
* [[UPX]] unterstützt seit Version 2.92 (beta) optional LZMA-Kompression | * [[WP:UPX|UPX]] unterstützt seit Version 2.92 (beta) optional LZMA-Kompression | ||
== Weblinks == | == Weblinks == | ||
| Zeile 51: | Zeile 49: | ||
{{body}} | |||
Version vom 17. Juni 2008, 21:36 Uhr
Allgemein
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. Auch das Tuxbox-Projekt verwendet LZMA in aktuellen SquashFS-Images.
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:
- 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
Grundlagen - Installation - Debug-Mode - Hardware - CDK/Development
LCars - Neutrino - Enigma - Plugins - Spiele - Software - Tools - Howto - FAQ - Images
Hauptseite - News - Alle Artikel - Bewertungen - Gewünschte Seiten - Index - Neue Artikel - Impressum - Team
Hilfeportal - Seite bearbeiten - Bilder - Links - Tabellen - Textgestaltung