Zip-Verfahren

Zip-Verfahren

von Marc Seifert

INHALTSVERZEICHNIS

I. Einleitung

II. Datenkompression

III. Vergleich ausgewählter Kompressionsverfahren

III.1 WinZip
III.2 Bzip
III.3 WinRAR

IV. Der Ziv-Lempel-Algorithmus

IV.1 LZ77
IV.2 LZSS
IV.3 LZ78
IV.4 LZW

V. Sprachwissenschaftliche Aspekte

V.1 Entropie, Redundanz und Paradigma
V.2 Einige Vorüberlegungen

V.3 Maschinelle Textanalyse
V.3.1 Bestimmung der relativen Entropie
V.3.2 Erkennung der Sprache
V.3.3 Erkennung der Autorenschaft
V.3.4 Korpus-Klassifizierung

VI. Zusammenfassung

VII. Anhang

VII.1 Literaturverzeichnis
VII.2 Verzeichnis der Tabellen und Bilder

I. Einleitung

Ziel der vorliegenden Arbeit ist es, den besonderen Nutzen von Algorithmen zur Datenkompression, hier in erster Linie die sogenannten Zip-Algorithmen, für die Sprach- und Literaturwissenschaften aufzuzeigen.
Dazu erfolgt zunächst eine allgemeine Einführung zum Thema Datenkompression, anschließend werden verschiedene Verfahren und Algorithmen untersucht und miteinander verglichen. Im zweiten Teil werden einige linguistisch relevante Fragen vorgestellt, für deren maschinelle Lösung Zip-Verfahren interressante Möglichkeiten eröffnen. Dabei erfolgt auch eine Einführungen in die Themen der Entropielehre, des Paradigmenwechsels und der sprachlichen Redundanz. Ein besonderes Augenmerk des Verfassers liegt darauf, sowohl den mathematisch-informationstheoretischen, als auch den sprachwissenschaftlichen Aspekten des Themas in gleicher Weise gerecht zu werden.

II. Datenkompression

Unter dem Begriff Komprimieren (umgangssprachlich oftmals auch als ′Zippen′ bezeichnet) versteht man das Verkleinern von Dateien mit Hilfe bestimmter Algorithmen.
Dabei unterscheidet man zunächst zwischen verlustbehafteter und verlustfreier Kompression. Verlustbehaftete Kompression, bei deren Dekomprimierung es zu einem Informationsdefizit kommt, tritt meist bei Speicher-Standards auf, bei denen ein Algorithmus zur Kompression bereits implementiert ist und hauptsächlich zur Komprimierung von Bild-, Audio- und Videodateien (z.B. JPG oder MP3) verwendet wird. Verlustfreie Kompression wird hingegen immer dort eingesetzt, wo es auf eine genaue Wiedergabe der komprimierten Daten ankommt. Als Vertreter der verlustfreien Datenkompression sind in erster Linie die Huffmann-Kodierung, die arithmetische Kodierung, die Lauflängen-Kodierung und die Gruppe der Lempel-Ziv-Kodierung zu nennen (Hrabowski 1999: 1).
Bis 1977 richtete sich das Augenmerk der Wissenschaft in erster Linie auf die Methoden zur Steuerung von Huffmann-Codierungsprogrammen, die mit Binärbäumen und Symbolen arbeiten. In den Jahren 1977 und 1978 begründeten Jacob Ziv und Abraham Lempel, zwei israelische Forscher, die am Technion in Haifa arbeiteten, mit ihren Algorithmen den Ursprung der modernen tabellengesteuerten Komprimierung. Jedoch erst nachdem Terry Welch diesen Algorithmus 1984 nochmals verbesserte erschienen erste Komprimierungsprogramme für Unix und MS-DOS (Jäger 2002: 1).
Zu den großen Vorteilen der Datenkompression gehört die geringe Größe der komprimierten Dateien, die einen verringerten Bedarf an Speicherplatz sowie einen raschen Datenversand ermöglichen. Hinzu kommen noch wissenschaftliche Anwendungsgebiete, die im Folgenden besprochen werden. Allerdings treten bei komprimierten Dateien auch zwei - nicht unbedeutende - Nachteile auf. Zum Einen muss zur Dekomprimierung in den allermeisten Fällen die gleiche Software zur Verfügung stehen, wie zum Komprimieren (nur sehr einfache Standards wie z.B. JPG lassen sich mit Hilfe von Internetbrowsern etc. dekomprimieren oder ermöglichen es, wie im Falle einiger weniger, komplexerer Algorithmen, .exe-Anwendungen zu bauen, die in der Lage sind, sich selbst zu entpacken) zum Anderen ist eine Suche mit Suchmaschinen in komprimierten Dateien so gut wie unmöglich bzw. erfolglos (Leiß 2000).

III. Vergleich ausgewählter Kompressionsverfahren

[...]