i-effect® *ZIP Grundlagen

Algorithmus

Der„deflation Algorithmus", der von zip und gzip benutzt wird ist eine Variation des LZ77 (Lempel-Ziv 1977, siehe Referenz weiter unten). Er findet mehrfach vorkommende Zeichenfolgen im Eingabedatenstrom. Das zweite Vorkommen einer Zeichenfolge wird durch einen Zeiger ersetzt, der auf das erste Vorkommen zeigt, und zwar in der Form einer paarweisen Angabe (Entfernung, Länge). Die Entfernungen sind begrenzt auf 32K Bytes, die Längen auf 258 Bytes. Wenn eine Zeichenfolge in den vorherigen 32K Bytes nicht vorkommt wird sie als Zeichen-Bytefolge ausgegeben. (In dieser Beschreibung ist Zeichenfolge als eine Reihenfolge von Bytes zu verstehen, die nicht notwendigerweise druckbare Zeichen enthalten muss.)
Zeichen-Bytefolgen oder Treffer-Längen werden mit einem Huffmann-Baum komprimiert und Treffer-Entfernungen werden mit einem anderen Baum komprimiert. Diese Baumstrukturen werden in kompakter Form am Anfang eines jeden Blocks gespeichert. Die Blöcke können jede beliebige Größe haben (außer der Beschränkung, dass die komprimierten Daten für einen Block in den zur Verfügung stehenden Hauptspeicher passen müssen). Ein Block wird beendet, wenn zip feststellt, dass es nützlich wäre, einen neuen Block mit leeren Baumstrukturen zu beginnen.
Doppelte Zeichenfolgen werden mit Hilfe eines Hash-Table gefunden. Alle Eingabe-Zeichenfolgen der Länge 3 werden in diesen Hash-Table eingefügt. Ein Hash-Index wird für die nächsten 3 Bytes berechnet. Wenn die Hash-Kette für diesen Index nicht leer ist werden alle Zeichenfolgen in dieser Kette mit der momentanen Eingabezeichenfolge verglichen und die größte Übereinstimmung wird ausgewählt.
Die Hash-Ketten werden beginnend mit der aktuellen Zeichenfolge durchsucht, um kurze Enterungen und folglich die Vorteile der Huffmann-Kodierung bestmöglich ausnutzen zu können.
Die Hash-Ketten sind einfach verknüpft. Es werden keine Hash-Ketten gelöscht, sondern der Algorithmus entfernt Einträge, die zu alt sind.
Um eine problematische Situation zu vermeiden, werden sehr lange Hash-Ketten willkürlich auf eine bestimmte Länge gekürzt. Festgelegt wird diese durch die Aufrufoption der Geschwindigkeit (1 bis 9). Also findet zip nicht immer die längste mögliche Übereinstimmung, in der Regel aber eine Übereinstimmung, die lang genug ist.
Zip verschiebt ebenfalls die Auswahl an Übereinstimmungen mit einem trägen Schätzalgorithmus. Nachdem eine Übereinstimmung der Länge N gefunden wurde, sucht zip nach einer längeren Übereinstimmung im nächsten Eingabebyte. Wird eine längere Übereinstimmung gefunden, wird die vorherige Übereinstimmung auf eine Länge von eins gekürzt. (So wird ein einzelnes Byte erzeugt) und die längere Übereinstimmung wird nachfolgend ausgegeben. Ansonsten wird die Original Übereinstimmung beibehalten und die Suche nach der nächsten Übereinstimmung wird nur N Schritte später eingeleitet.
Die Lazy-Match Berechnung wird außerdem durch Laufzeitparameter beeinflusst. Wenn die momentan gefundene Übereinstimmung lang genug ist reduziert zip die Suche nach einer längeren Übereinstimmung, sorgt also dafür, dass die Verarbeitungsgeschwindigkeit steigt. Wenn die Kompressionsrate wichtiger ist als Geschwindigkeit versucht ZIP eine komplette zweite Suche, auch wenn die erste Übereinstimmung schon lang genug war.
Die Lazy-Match Berechnung wird nicht für schnelle Komprimierungen durchgeführt (Geschwindigkeit 1-3). Bei diesen Methoden werden neue Einträge in die Hash-Table nur dann eingefügt, wenn keine Übereinstimmung gefunden wird, oder wenn die Übereinstimmung nicht lang genug ist. Das führt zu einer verschlechterten Komprimierungsrate, spart aber Zeit, weil sowohl weniger Einfügungen, als auch weniger Suchen durchgeführt werden müssen.
nach

Gzip-Dateiformat

Das pkzip-Format bürdet eine Menge an Overhead in verschiedenen Headern auf, die für ein Archivprogramm sehr sinnvoll sind nicht jedoch für die Komprimierung einer einzelnen Datei. Gzip benutzt eine wesentlich einfachere Struktur: Zahlen werden im „little endian" Format gespeichert und Bit 0 ist das „least significant" Bit. Eine Gzip- Datei ist eine Folge komprimierter Teildateien. Jede Teildatei hat folgende Struktur:

Das Format wurde entwickelt

Die Zeitmarke ist hauptsächlich sinnvoll, wenn eine gzip Datei über ein Netzwerk transportiert wird. In diesem Fall würde es nicht genügen, nur die Besitzattribute zu bewahren. Im vorliegenden Falle werden die Attribute von gzip beim Komprimieren/Dekomprimieren bewahrt, eine Zeitmarke Null wird ignoriert.
Bit 0 in den Flags ist nur ein optionaler Anzeiger, welcher durch ein kurzes Vorlesen in der Eingabedatei gesetzt werden kann. Im Zweifelsfall wird das Bit gelöscht um binäre Daten anzuzeigen. Auf Systemen, die unterschiedliche Dateiformate für ASCII Text und Binärdaten haben, kann der Dekompressor dieses Flag benutzen, um das richtige Format auszuwählen.
Das Extra-Feld, wenn vorhanden, muss aus einem oder mehreren Unterfeldern bestehen, jedes mit dem folgenden Format:

Unterfeld Daten

Die Unterfeld ID kann aus zwei Zeichen mit symbolischer Bedeutung bestehen.
Id's mit einem zweiten Nullbyte sind reserviert für spätere Verwendung. Die folgenden Id's sind zur Zeit definiert:

Ap (0x41, 0x70): Apollo Dateityp Information

Die Unterfeldgröße ist die Größe der Unterfelddaten und beinhaltet nicht die ID und die Größe selber.
Das Feld„Extra Feld Größe"ist die gesamte Länge des Extrafeldes, inklusive der Unterfeld-ID und Unterfeldgröße.
Es muss möglich sein, das Ende der komprimierten Daten zu ermitteln und zwar unabhängig von der Komprimierungsmethode und der tatsächlichen Größe der komprimierten Daten. Wenn die komprimierten Daten nicht in eine Datei passen (besonders bei Verwendung von Disketten/Bändern) beginnt jeder Teil mit dem oben beschriebenen Kopf, aber nur der letzte Teil hat die Angaben„crc32"und„unkomprimierte Länge". Ein Dekompressor kann für solche in mehreren Teilen komprimierte Dateien Benutzeranforderungen für weitere benötigte Teile senden.
Es ist wünschenswert aber nicht notwendig, dass einzelne Teile einer solchen Datei unabhängig voneinander dekomprimiert werden können falls ein Teil beschädigt ist. Dies ist nur möglich, wenn der Stand der Komprimierung nicht von einem Teil in den anderen übernommen wird.
Wenn die Datei auf einem System komprimiert wird, in dessen Dateisystem mit Klein- und Großbuchstaben gearbeitet wird, muss der Originaldateiname in Kleinbuchstaben umgewandelt werden. Wenn Daten von der Standard-Eingabe komprimiert werden, gibt es keinen Originaldateinamen.
Die Kompression wird immer durchgeführt, selbst dann, wenn die komprimierte Datei etwas größer als das Original ist. Im schlimmsten Fall kann die Vergrößerung ein paar Bytes für den gzip Dateikopf, plus 5 Bytes für jeden 32K Block betragen. Dies entspricht einem Faktor von 0.015% für große Dateien.
In jedem Fall wird die aktuell benötigte Anzahl von Speicherblöcken dadurch so gut wie niemals erhöht.
Die Verschlüsselung ist die von zip 1.9. Für die Verschlüsselungsprüfung wird das letzte Byte des entschlüsselten Verschlüsselungskopfes untersucht.
Es muss Null sein. Die Zeitmarke einer verschlüsselten Datei darf auf Null gesetzt werden, um zu vermeiden, dass daraus der Aufbau des Kopfes abgeleitet werden könnte.
nach

Jean-loup Gailly
gzip@prep.ai.mit.edu
jloup@gzip.org

Referenzen

[LZ77] Ziv J., Lempel A., „A Universal Algorithm for Sequential Data
Compression", IEEE Transactions on Information Theory", Vol. 23, No. 3, pp. 337-343.
APPNOTE.TXT documentation file in PKZIP 1.93a. It is available by
ftp in ftp.cso.uiuc.edu:/pc/exec-pc/pkz193a.exe [128.174.5.59]
Use „unzip pkz193a.exe APPNOTE.TXT" to extract (note: unzip, not gunzip).

ZIP-Dateiformat

Zusätzlich zum vorher beschriebenen gzip-Format unterstützt i-effect *ZIP auch das auf vielen Plattformen vorzufindende Archivformat ZIP. Auf Windowsplattformen beispielsweise ist dies durch Produkte wie WINZIP™ bekannt geworden.
Ein ZIP-Archiv ist eine Datei, in der die komprimierten Daten von mehreren Dateien untergebracht werden. Entsprechende Funktionen in der benutzen Software erlauben das Hinzufügen, Löschen, Extrahieren oder Anzeigen der komprimierten Inhalte.
i-effect^®ist mit seinem im optionalen Modul *ZIP erhältlichen Funktionsumfang voll kompatibel zu dem allgemeinen ZIP Format und erlaubt so den Austausch von Archivdateien mit anderen Plattformen (z.B. WINZIP™).
Innerhalb einer Archivdatei (.ZIP-Datei) können unterschiedliche Objektarten komprimiert sein. Zur Zeit werden unterstützt: Physische Dateien (PF-DTA), Quelldateien (SRC-PF), Sicherungsdateien (SAVF), Dateien aus dem IFS-Dateisystem und Spooldateien.
Werden diese Objektarten mit i-effect *ZIP auf einer IBM Power Systems wiederhergestellt, dann erhalten Sie die tatsächlichen Ursprungsobjektarten. Spooldateien werden als tatsächliche Spooleinträge in Ausgabewarteschlangen angelegt; Komprimierte Sicherungsdateien werden zu richtigen Sicherungsdateien u.s.w.