Zip und Zop

Fast jeder Linux-Anwender stolpert früher oder später über Dateien mit der Endung .gz und .bz2. Gzip und Bzip2 gehören zu den gängigen Programme, um unter Linux eine einzelne Datei zu komprimieren. Dabei spart Bzip2 in der Regel etwas mehr Platz, braucht dafür aber länger. Es gibt jedoch Alternativen: Die parallelen Bzip-Varianten Pbzip, Lbzip2 sowie Neulinge wie Xz, Lzip, Lzma, Lzop und Exoten wie Kgb, Paq8L, Zp, Zpaq oder Lrzip.

Die verlustfreie Datenkompression basiert darauf, die Informationsdichte zu erhöhen und Wiederholungen zusammenzufassen. Die in diesem Artikel verwendeten Komprimier-Programme verwenden dazu unterschiedliche Algorithmen (siehe Tabelle "Verwendete Kompressionsalgorithmen").

Kurz und prägnant

Ein typischer deutscher Text besteht aus maximal 26 Klein-, 26 Groß-Buchstaben, ein paar Umlauten und ein paar Satzzeichen. Die Zeichenkodierung Latin 1 verwendet für jedes Zeichen ein Byte, also 8 Bit; das neuere UTF-8 bis zu 4 Byte. Eigentlich reichen für 32 oder 64 Zeichen fünf oder sechs Bits. Ein einfaches Komprimier-Programm könnte also ermitteln, wieviele unterschiedliche Byte-Werte eine Datei enthält, und für diese eine neue Kodierungstabelle mit weniger Bits anlegen.

Die Huffmann-Kodierung arbeitet nach diesem Prinzip, geht aber noch einen Schritt weiter und verwendet abhängig von der Häufigkeit eines Zeichens eine unterschiedlich lange Bitfolge [1]. So kodiert sie den häufig vorkommen Buchstaben E zum Beispiel mit der Bitfolge 10 (eins null), während sie für den selteneren Buchstaben Y vielleicht 11010 (eins eins null eins null) verwendet.

Auch Bzip2 verwendet die Huffman-Kodierung. Es bringt die Daten jedoch vorher blockweise in eine Reihenfolge, in der gleiche Symbole häufiger direkt hintereinanderkommen, und sortiert diese häufigen Symbole an den Anfang, damit diese kleinere Werte erhalten[2]. Die blockbasierte Arbeitsweise eignet sich gut für das Aufteilen in Threads.

Wörterbücher

Anders arbeiten Verfahren, die anhand eines Wörterbuches Sequenzen durch kürzere Sequenzen ersetzen. Die Algorithmen der Lempel-Ziv-Familie wie LZ77, Lempel-Ziv-Storer-Szymanski (LZSS), LZ78, Lempel-Ziv-Welch (LZW), Lempel-Ziv-Markow (LZMA) und Lempel-Ziv-Oberhumer (LZO) arbeiten nach diesem Prinzip.

Das älteste dieser Verfahren, LZ77 kodiert zum Beispiel das Wort "PAPAYA" wie folgt: "P" anhängen und weiter, "A" anhängen und weiter, die letzten beiden Buchstaben nochmal und "Y" anhängen, "A" anhängen [3]. Je größer der Bereich für das Suchen nach Wiederholungen desto effizienter arbeitet der Algorithmus. Allerdings wächst damit die Größe des Wörterbuches, was das Auffinden von Einträgen verlangsamt.

Die anderen Varianten modifizieren den Algorithmus, um unter anderem mit größeren Wörterbüchern höhere Informationsdichten zu erzielen – bis auf LZO, das auf hohe Geschwindigkeiten beim Packen und vor allem beim Entpacken optimiert ist. Die Verfahren LZ78 und das im GIF-Bildformat verwendete LZW waren bis zum Jahre 2004 in einigen Ländern patentiert und kamen daher in freier Software selten zum Einsatz.

Besonders effizient arbeitet das neuere LZMA, das Wahrscheinlichkeiten für zukünftige Bitfolgen ermittelt und große Wörterbücher unterstützt. Das PNG-Format verwendet wie Zip das Deflate-Verfahren, das auch für OpenDocument-Dokumente, wie sie OpenOffice.org erstellt, zum Einsatz kommt. Es kombiniert die LZ77-Variante LZSS mit der Huffman-Kodierung.

Rar verwendet Prediction by Partial Matching (PPM), um einzelne Bits vorherzusagen. Die Verfahren der PAQ-Familie verwenden dafür an verschiedene Dateitypen wie Text, Bildformate, Tabelle und ausführbare Programme angepasste Verfahren [5]. Sie arbeiten symmetrisch, benötigen also für Kompression und Dekompression etwa die gleiche Zeit.

Die Verfahren der PAQ8-Familie treiben den Aufwand mit dem Einsatz eines neuronales Netzes auf die Spitze [6],[6],[7]. Der schnellere Nachfolger Zpaq schreibt eine Beschreibung des Algorithmus in die Ausgabe-Datei, um das Problem mit der Vielzahl unterschiedlicher, zueinander inkompatibler PAQ-Versionen zu lösen.

Einige Pack-Programme bieten Multithreading oder fassen mehrere Dateien in einem Archiv zusammen. Während Zip dabei jede Datei einzeln komprimiert, verwenden Programme wie Rar und auf Wunsch auch 7-Zip für alle Dateien ein gemeinsames Wörterbuch, um eine höhere Packdichte zu erzielen.

Ein Archivierer wie Tar ergänzt Komprimier-Programme, die nur einzelne Dateien unterstützen, um diese Funktion. So fasst tar -cvf texte.tar *.txt alle Dateien mit der Endung .txt in das Archiv texte.tar zusammen, das gzip texte.tar als texte.tar.gz komprimiert. Mit der entsprechenden Option leitet Tar die zusammengefügten Dateien automatisch an Gzip, Bzip2, Xz, Lzop, Lzip oder Lzma weiter (Tabelle "Tar-Optionen").

Über die Option -I beziehungsweise --use-compress-program verwenden Sie ein anderes Komprimierprogramm an. Mit der ab Version 1.19.1 verfügbaren Option -a oder --auto-compress ermittelt Tar das Format anhand des Archivnamens automatisch. Beim Entpacken erledigen das aktuelle Tar-Versionen ohne diese Option. Mehr zum Zusammenfassen mehrerer Dateien liefert Howto im Web [8].