Datenkompremierung File Compression

1) Datenkompremierung (File Compression):

Dieser Algorithmus behandelt in erster Linie die Platzreduzierung und erst in zweiter Linie behandelt er die Zeitreduzierung. Diese Technik heißt auch Kodierungsmethode.

Im allgemeinen haben Dateien einen hohen Grad an Redundanz. Die Verfahren die wir untersuchen sparen Platz weil die meisten Dateien einen relativ geringen Informationsgehalt haben

Einsparungen kann man bei einer Textdatei von 20% bis 50% haben, jedoch bei einer binären

Datei hat man Einsparungen von 50% bis 90%. Doch es gibt auch Datentypen bei dem man nur wenig einsparen kann, solche die aus zufälligen Bits bestehen.

Tatsächlich ist es so, daß Mehrzweck-Verfahren gewisse Dateien verlängern müssen, den sonst könnte man das Verfahren wiederholen und dadurch beliebig kleine Dateien erzeugen.

2) Lauflängenkodierung (Run-Length Encoding):

Man spricht hier von einen Lauf (run) dann, wenn sich lange Folgen sich wiederholender

Zeichen darstellt.

Siehe dieses Bsp sprich 1.Metode:

AAAABBBAABBBBBCCCCCCCCDABAAABBBBCCCD

Diese Zeilenfolge kann viel Kompakter kodiert werde, indem man die wiederholenden Zeichen nur einmal angibt und die Anzahl der Wiederholungen davor schreibt.

Also würde dann unser Bsp. kodiert so aussehen:

4A3B2A5B8CDABCB3A4B3CD

Bei einem Bitraster würde die Lauflängenkodierung so aussehen:

2. Methode oder Bsp.:

28 14 9

26 18 7

23 14 4

22 26 3

20 30 1

19 7 18 7

19 5 22 5

19 3 26 3

19 3 26 3

19 3 26 3

19 3 26 3

20 4 23 3 1

22 3 20 3 3

1 50

1 50

1 50

1 50

1 50

1 2 46 2

Hier in diesem Bitraster sieht man rechts eine Liste von Zahlen, die einen Buchstaben in einer kompremierten Form speichern können.

Man gibt nun links davon die jeweiligen Häufigkeiten an wie oft nun diese Null oder Eins

vorkommt, zB.: in der ersten Zeile, sie besteht aus 28 Nullen 14 Einsen und dann folgen wieder

9 Nullen usw geht es mit den anderen Zeilen.

Man sieht also, daß es wesentlich besser ist die kodierte Form zu übergeben als die unkodierte,

und man kann auch so wieder den Bitraster rekonstruieren.

Man hat dadurch eine recht große Einsparung, denn man 975 Bits bei unkodierten Darstellung verwenden, aber jedoch nur 384 Bits bei der kodierten Darstellung, ergibt eine Einsparung von 591 Bits.

3) Kodierung mit variabler Länge (Variable-Length Encoding):

Dieses Datenkompressionsverfahren spart beträchtlich Platz bei Textdateien.

Nehmen wir an wir wollen eine Zeichenfolge "ABRACADABRA" kodieren, und dieses mit dem herkömmlichen Verfahren des binären-Codes, bei einer Binärdarstellung mit Hilfe von 5 Bits zu

Darstellung eines Buchstabens. Dann lautet die Bitfolge so:

0000100010100100000100011000010010000001000101001000001

Um diese zu dekodieren, nimmt man sich 5 Bits her und wandelt sich nach dem Binärcode um.

Nun ist dieses ziemlich unpraktisch, denn der Buchstabe D kommt nur einmal vor, aber der Buchstabe A jedoch 5 mal und ich muß A jedesmal die selbe Bitfolge aufschreiben und wieder dekodieren.

Es wäre doch besser wenn man versuchen würde, häufig verwendete Buchstaben eine kürzere Bitfolge zuzuweisen, indem man sagt A wird mit 0 kodiert, B mit 1, R mit 01, C mit 10 und D

mit 11, so daß dann aus ABRACADABRA dann diese

0 1 01 0 10 0 11 0 1 01 0

Bitfoge dann werden würde. Diese ist schon wesentlich kürzer denn diese Bitfolge hat nur mehr

15 Bits benutzt als die vorhergehende die 55 Bits verbraucht hat. Doch hat dieser Code einen Haken, denn es ist kein wirklicher Code, da er abhängig ist von den Leerzeichen, ohne diese Leerzeichen würde nämlich 010101001101010 als RRRARBRRA heraus kommen.

Also muß man die Zahl mit Begrenzern dekodieren, aber dann noch ist die Zahl von 15 Bits plus

10 Begrenzern noch immer Kleiner als der Standart-Code.

Wenn kein Zeichencode mit dem Anfang eines anderen übereinstimmt werden keine Begrenzer benötigt. Deswegen werden wir die zu kodierenden Buchstaben anders gewählt, nämlich:

A mit 11, B mit 00, C mit 010,D mit 10 und R mit 011

so gäbe es nur eine Möglichkeit die 25 Bits Zeichenfolge

1100011110101110110001111

zu dekodieren.

Eine noch einfachere Methode zur Darstellung eines Codes ist ein Trie.

Dazu ein Bsp.: Wir wollen wieder ABRACADABRA kodieren, aber dieses mal mit dem Trie.

Dazu sollte man wissen, daß man bei einem Trie immer von der "Wurzel"

ausgeht und so sein Zeichen bestimmt. Wenn man bei einem Knoten angelangt

ist, muß man sich entscheiden ob nach links oder rechts.

Für links muß man mit 0 codieren und für rechts mit 1.

1.Bsp 2.Bsp:

1100011110101110110001111 01101001111011100110100

A

R

B D A

B

C R

D

[E1]  C

Nun, man sieht hier, daß der rechte Code um 2 Bits kürzer ist als der andere.

Die Trie-Darstellung garantiert also, daß kein Code für ein Zeichen mit den Anfang eines anderen Zeichen übereinstimmt, so daß sich die Decodierung für die Zeichenfolge eindeutig

festlegen läßt.

Doch welchen Trie soll man Benutzen? Hier gibt es eine Lösung bei der man bei gegebener Zeichenfolge einen Trie berechnen kann und der eine minimale Bitfolge hat.

Dieses Verfahren wird Huffman Kodierung genannt.

4) Erzeugung des Huffman-Codes (Building the Huffman Code):

Bei dem Erzeugen des Huffman-Codes kommt es in erster Linie darauf an wieviel Zeichen

zu decodieren sind plus Leerzeichen. Nun ermittelt das folgende Programm die unterschiedlichen Häufigkeit der Buchstaben eines Zeichenfeldes, und trägt sie dann in ein Feld count[0-26] ein.

Nun wieder ein Beispiel das wir kodieren möchten, die Zeichenfolge lautet: "A SIMPLE STRING TO BE ENCODED USING A MINIMAL NUMBERS OF BITS".

Der erste schritt ist der Aufbau eines Tries entsprechend seiner Häufigkeiten, dazu sollte man

sich eine Buchstabentabelle machen.

A B C D E F G H I J K L M N O P Q R S T U V W X Y Z

k                     0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26

count[k]        11 3 3 1 2 5 1 2 0 6 0 0 2 4 5 3 1 0 2 4 3 2 0 0 0 0 0

Danach kann man schon mit dem Trie beginnen, man fängt an in dem man die Buchstaben (Knoten) mit der Häufigkeit 0 wegläßt, und alle anderen Knoten mit ihrer Häufigkeit in einer Ebene darstellt. Nun nimmt man die Knoten mit den niedrigsten Häufigkeiten und fasse sie zusammen. Man nimmt nun die nächst höhere Häufigkeit und fasse sie wieder zusammen, dieses geht so lange weiter bis alle Häufigkeiten in einem Baum dargestellt sind.

Beachten muß man jedoch daß die sich Knoten mit geringer Häufigkeit weit unten im Baum befinden und Knoten mit hoher Häufigkeit weit oben im Baum befinden.

Die Quadratischen Knoten sind Häufigkeitszähler und die runden Knoten sind Summen Knoten und lassen sich durch ihre Nachfolger wieder darstellen.

5) Implementation (Implementation):

Bei der Implementation kommt es mehr darauf an den Huffman-Code richtig anzuwenden bzw.

die Vorausberechnen richtig zu rechnen um denn daraus eine effiziente Kodierung zu kriegen.

Man sollte hier einen Trie finden der die Häufigkeit der Buchstaben berechnet oder für Zeichen

verwendet, deren Häufigkeit in einem Pascal Programm auftritt zB.: ; und dafür eine Bitfolge reserviert.

So ein Kodierungsalgorithmus kann mit Hilfe des Huffman Codes 23% Einsparung liefern.