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.
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.[1] 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[2] den Ursprung der modernen tabellengesteuerten Komprimierung. Jedoch erst nachdem Terry Welch diesen Algorithmus 1984 nochmals verbesserte[3] 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).[4]
Abbildung in dieser Leseprobe nicht enthalten
Bild2: Jacob Ziv
Bild 2 und Bild 3 (Hrabowski 1999: 2)
Bild 3: Abraham Lempel
III. Vergleich ausgewählter Kompressionsverfahren
Die Untersuchung verschiedener Kompressionsverfahren in diesem Kapitel erhebt keinerlei Anspruch auf Vollständigkeit. Eine solche Untersuchung könnte Thema eines eigenständigen Aufsatzes sein und würde den eingeschränkten Rahmen dieser Arbeit übersteigen.
Aus diesem Grund werden drei, auf unterschiedlichen Konzepten basierende Kompressionsverfahren vorgestellt und miteinander verglichen.
III.1 WinZip
Bei WinZip handelt es sich um ein weit verbreitetes, für private Anwender lizenzfreies Programm zur verlustfreien Datenkompression unter Microsoft Windows-Oberflächen. WinZip arbeitet mit dem LZ-Algorithmus und bietet alle gängigen Features moderner PC-Anwendungen für Windows-Oberflächen. Erreicht werden Kompressionsraten zwischen 60% und 90%.[5]
III.2 Bzip
Bzip[6] ist ein frei erhältliches (Freeware), patentfreies (open-source) Programm zur verlustfreien Datenkompression. Bzip ist auf jedem Unix und Win32 System lauffähig und arbeitet mit dem Block-sortierenden Text-Kompressions-Algorithmus Burrows-Fenwick. Mit Bzip werden extrem hohe Kompressionsraten zwischen 85% und 90% erreicht.5 Die besondere Stärke von Bzip liegt jedoch in der Geschwindigkeit. Die Komprimierung der Daten erfolgt in der Regel doppelt so schnell als bei anderen Kompressionsprogrammen (z.B. WinRAR), bei der Dekomprimierung ist Bzip sogar bis zu sechs Mal schneller. Außerdem können auch fehlerbehaftete oder beschädigte Dateien noch fast vollständig dekomprimiert werden (Seward 1997: 7).
III.3 WinRAR
WinRAR ist ein kommerzielles Kompressionprogramm (verlustfrei und für Privatanwender ebenfalls als Shareware erhältlich) für Windows-Oberflächen, das auf dem Advanced Encryption Standard (AES) des amerikanischen National Institute of Standards and Technology (NIST) basiert. Der AES arbeitet mit dem Algorithmus 'Rijndael' von Joan Daemen und Vincent Rijmen (AES 2002: 1). Der Vorteil von WinRAR liegt in seinen extrem guten Komprimierungsraten, die sehr kleine Dateien ermöglichen. Außerdem ermöglicht es dem Anwender, ganze Archive (auch selbstentpackend) zu erstellen und zu komprimieren. Leider ist WinRAR weit weniger stark verbreitet als z.B. WinZip und in der Anwendung auch weniger komfortabel und deutlich langsamer (WinRAR 2002a).
IV. Der Ziv-Lempel-Algorithmus
Im Gegensatz zur bis dahin verwendeten, statistischen Methode[7], entwickelten Lempel und Ziv einen Algorithmus auf der Basis einer tabellengesteuerten Funktion:
"Der tabellengesteuerte Algorithmus codiert Symbolketten variabler Länge als Token, die einen Verweis in ein Phrasenverzeichnis darstellen. Sind diese Token kleiner als die Phrasen, die sie ersetzen, kommt es zur Komprimierung. Damit kann dieser Algorithmus immer auf den Text reagieren [...]" (Jäger 2002: 2)
"Mit zunehmender Länge sinkt der benötigte Speicherplatz einer mit dem Lempel-Ziv Algorithmus komprimierten Datei gegen die Entropie des Textes ab." (Szpiro 2002)
Die LZ-Algorithmen[8] arbeiten als substituierende Kompressoren, die einen Eingabestrom auf bereits aufgetretene Zeichenketten hin überprüfen und diese dann durch eine Referenz auf ihr erstmaliges Auftreten ersetzen. Der Algorithmus lernt dabei (unabhängig davon, um welche Art von Datei es sich handelt) jedes Mal erneut, welche Zeichenfolgen in der vorliegenden Datei vermehrt auftreten und passt seine Komprimierung dem Dateityp an. Der Unterschied zwischen den diversen Vertretern der LZ-Algorithmen besteht in der Art, wie sie die im Eingabestrom enthaltene Redundanz erfassen und substituieren. Da die Redundanz in einer Datei nicht gleichmäßig verteilt ist, sondern lokale Häufungen auftreten, wurden bis heute eine Vielzahl von LZ-Varianten entwickelt, die jeweils für einen bestimmten Datentyp optimiert sind. Allen LZ-Algorithmen gleich sind folgende Eigenschaften:
- verlustfreie Datenkompression
- kein Benötigen von zusätzlichen Informationen
- alle Informationen über die Daten werden während des Komprimierungsvorganges gewonnen.
Grundsätzlich lassen sich die LZ-Algorithmen in zwei Gruppen einteilen (nach Hrabowski 1999: 2ff):
a) LZ77-basierende, bei denen der bereits verarbeitete Datenstrom als Wörterbuch dient (implicit dictionary). An Stelle einer Wiederholung der bereits bekannten Zeichenkette wird ein Zeiger mit einer Referenz auf diese gespeichert.
b) LZ78-basierende, die bei der Kompression ein Wörterbuch aus Zeichenketten anlegen und bei wiederholtem auftreten dieser Zeichenketten lediglich den Wörterbuch-Index derselben speichern.
[...]
Das Titelbild (Bild 1) ist dem Booklet eines CD-Rohlings der Firma TEAC entnommen.
[1] Diese finden heute noch Verwendung in Standards wie z.B. TIFF oder Bzip2.
[2] LZ77 und LZ78. Beide werden in Kapitel IV. Der Ziv-Lempel-Algorithmus ausführlich vorgestellt.
[3] Dieser von Welch verbesserte LZ78-Algorithmus ist unter dem Namen LZW bekannt.
[4] Share- und Freeware zur Datenkompression findet man unter http://www.mondkind.de/packer oder http://www.tucows.at.
[5] Gemessen bei kurzen bis mäßig langen (bis max. 5 MB) wissenschaftlichen Text-Dateien.
[6] Bzip ist auch unter dem Namen Gzip bekannt.
[7] Eine Beschreibung der statistischen Methode findet sich in Jäger (2002: 2).
[8] Neben den zwei Besprochenen Haupttypen und deren wichtigsten Weiterentwicklungen gibt es noch eine Vielzahl weiterer Algorithmen, die auf LZ77 und LZ78 basieren. Hrabowski (1999: 8/9) bespricht außerdem noch folgende Typen: LZSS mit adaptiver arithmetischer Kodierung, LZSS mit adaptiver Huffmann Kodierung, LZC und LZMW.
-
Upload your own papers! Earn money and win an iPhone X. -
Upload your own papers! Earn money and win an iPhone X. -
Upload your own papers! Earn money and win an iPhone X. -
Upload your own papers! Earn money and win an iPhone X. -
Upload your own papers! Earn money and win an iPhone X. -
Upload your own papers! Earn money and win an iPhone X. -
Upload your own papers! Earn money and win an iPhone X.