|
Welche Standard-Tools bei den verschieden Betriebssystemen verwendet
werden. ist unten den jeweiligen Rubriken zu Windows/DOS,
Macintosh, UNIX/Linux
und Andere nachzulesen.
Doch hinter jeden Tool steckt Verfahren bzw. Algorithmus der die
Datei letztendlich kleiner macht. Folgende Verfahren sind dabei
anzutreffen:
Lauflängen Kodierung (RLE):
Die Lauflängen Kodierung (Run-length Encoding = RLE) ist ein
sehr einfaches Verfahren. Beim RLE wird der Dateiinhalt Schritt
für Schritt nach mehrfach
hintereinander vorkommenden Bytes (Anzahl > 3) durchsucht und
mit einem Markierungsbyte, das Byte selbst und die Anzahl der Wiederholungen,
versehen. Das Markierungsbyte sollte nicht in der Datei enthalten
sein. Falls aber alle 256 möglichen Zeichen sich in der Datei
befinden, definiert man ein Byte, welches in der Datei immer alleine
steht. Bei älteren RLE Verfahren wurden alle Bytes kodiert,
was dazu führte, daß die komprimierten Dateien manchmal
größer waren als die Originaldatei. Dies geschah, wenn
in der Datei wenig Wiederholungen vorkamen.
Huffman Verfahren (Huffman-Code):
Das Huffman Verfahren ist ein Verfahren, das sich nach der Idee
des Morsealphabets richtet. Beim ASCII-Code wird jedes Zeichen mit
8 Bit kodiert, während beim Huffman-Code dagegen häufig
vorkommende Zeichen mit wenigen Bits und selten vorkommende Zeichen
dafür mit mehr Bits kodiert. Um die Zeichenhäufigkeiten
zu bestimmen wird die Datei einmal gelesen. Zur Ermittlung des Huffman-Codes
wird ein Binärbaum aufgebaut.
Zur Dekodierung wird einfach Bit für Bit eingelesen und es
wird der Binärbaum von der Wurzel an durchwandert bis ein Zeichen
als Blatt gefunden wird. Dieses ist dann dekodiert und der Baum
fängt beim nächsten Bit wieder von der Wurzel an. Zu beachten
ist, daß der Binärbaum auch in der komprimierten Datei
mit abgespeichert werden muß, damit eine Entkomprimierung
möglich ist. Bei kleinen Dateien kann es deshalb durchaus sein,
daß die komprimierte Datei größer ist als das Original.
Das Huffman Verfahren ist sehr verbreitet und wird von vielen Komprimierprogrammen
benutzt (z.B. PKZIP/PKUNZIP oder ARJ) oder in Verbindung mit anderen
Verfahren (mit LZ77 bei LHA).
Lempel-Ziv-Welch Verfahren (LZW Algorithmus):
Es gibt mehrere Lempel-Ziv Verfahren (LZ77, LZSS, LZ78), aber das
Lempel-Ziv-Welch ist das bekannteste, obwohl es schon Weiterentwicklungen
des LZW
gibt (LZC und LZMW). Das Lempel-Ziv-Welch Verfahren ist eine Weiterentwicklung
der Lempel-Ziv Algorithmus LZ78 und basiert auf dem Prinzip eines
Wörterbuchs. Das Wörterbuch enthält am Anfang für
jedes in der Datei vorkommende Zeichen einen Eintrag. Während
der Komprimierung werden dann neue Einträge vorgenommen. Somit
wird das Wörterbuch während der Komprimierung immer größer
und der Code dadurch immer kleiner.
Beim Dekomprimieren besteht das Wörterbuch wieder nur aus
jedem in der Datei vorkommenden Zeichen und das Wörterbuch
wird während der
Dekomprimierung erstellt.
Der Vorteil im Vergleich zum Huffman-Verfahren ist, daß hier
das ganze Wörterbuch nicht mit in der Datei mit eingespeichert
werden muß.
Bitonale Kompression:
Von LuraTech
wird ein auf der Wavelet-Transformation
beruhendes Kompressionsalgorithmus für bitonale Daten entwickelt
(komplizierte mathematische Berechnung mittels Koeffizienten / Hoch-
/ Tiefpaßfilterung /
Matrizen). Der Algorithmus ist in der Lage, Texte und Strichzeichnungen
mittels der Wavelet-Transformation effektiver als vorhandene Lösungen
zu
komprimieren. Ein besonderer Vorteil wird die Fähigkeit sein,
in einem zu digitalisierenden Dokument Bilder zu erkennen. Diese
werden dann mit dem
herkömmlichen Verfahren bearbeitet.
Shannon-Fano Kodierung:
Die Shannon-Fano Kodierung basiert auf statistischen Annahmen über
die zu komprimierenden Daten. Häufige Symbole sollen durch
kurze, und seltene Symbole durch lange Bitfolgen kodiert werden.
Dabei können seltene Symbole durch Bitfolgen kodiert werden,
die länger sind als die ursprünglichen Symbole.
Aus einem Datenstrom wird für jedes Symbol, z.B. ein Byte,
in einer Tabelle die Anzahl seines Auftretens gespeichert. Die Summe
über alle Tabelleneinträge ergibt dann die Gesamtgröße
des Datenstroms. Die Tabelle wird nun so sortiert, das die häufigsten
Symbole am Anfang, und die seltensten Symbole am Ende stehen.
Die Kompression erfolgt nun dadurch, daß in der komprimierten
Datei die Häufigkeitstabelle abgespeichert wird, und dann die
Daten entsprechend der ermittelten Bitcodes zusammengefaßt
werden. Dabei ist darauf zu achten, daß die Tabelle möglichst
klein und kompakt gehalten wird, da sie als sogenannter Overhead
nur Organisationsdaten zur Dekompression enthält. Bei der Dekompression
werden wieder aus der gespeicherten Tabelle die Bitcodes gebildet
und aus den nachfolgend eingelesenen Bitcodes die entsprechenden
Symbole ermittelt und gespeichert.
Arithmetische Kodierung:
Bei der arithmetischen Kodierung werden Zeichenfolgen in einen
Code umgesetzt. Dazu müssen in einem ersten Schritt die relativen
Häufigkeiten der einzelnen Zeichen berechnet werden. Dann werden
die einzelnen Zeichen als Intervalle der Form [a;b) dargestellt.
Die Länge der Intervalle entsprechen den Häufigkeiten
der einzelnen Zeichen. Häufigkeiten lassen sich mit reellen
Zahlen zwischen 0 und 1 repräsentieren, wobei 0 für "nie
vorkommend" und 1 für "immer vorkommend" steht.
Da die Summe der Häufigkeiten 1 ist, ergibt diese Kette von
Intervallen das Intervall [0;1). Für möglichst kurze Codes
nimmt man natürlich die Zahl mit den wenigsten Stellen, die
in dem Intervall des Zeichens liegt. Da alle vorkommenden Zahlen
im Intervall [0;1) liegen, beschränkt sich die Kodierung nur
auf die Nachkommastellen.
Die Infos haben keinen Anspruch auf Vollständigkeit. Anregungen,
Kritiken oder Beiträge sind willkommen. Bitte an webmaster@archivator.net
senden.
|
