Generelles
Hier soll eine Reihe von Caches entstehen, die sich mit dem kodieren von Informationen beschäftigt - warum nicht auch mal etwas Wissen in einem Mysterie vermitteln. Diese Reihe baut aufeinander auf und daher wird sie auch Schritt für Schritt schwieriger. Während man am Anfang noch alles mit Stift und Papier berechnen kann, wird später der Einsatz von Programmierkenntnissen doch sehr zu empfehlen sein.
Dabei sollt ihr, wie gesagt, auch noch was praktisches Lernen: Wer sich schon immer mal gefragt hat, wieso eine Datei, wenn man sie zippt plötzlich viel kleiner ist gegenüber der ursprünglichen, der wird hier einige Antworten finden. Wir behandeln hier also Kompressionsverfahren.
Prinzipiell unterscheidet man zwischen verlustfreier und verlustbehafteter Kompressionsverfahren. Verlustbehaftete Kompression findet z.B. bei der Bilddatenkomprimierung statt: minimale Farbunterschiede, die für das Auge kaum wahrnehmbar sind, werden nicht mehr dargestellt. Oder bei Audiodateien: bei mp3 werden Töne, die der Mensch nicht oder nur sehr schwer hören kann, einfach weggelassen.
Diese Serie von Caches beschäftigt sich ausschließlich mit verlustfreier Kompression. Diese kommt beispielsweise bei der Verarbeitung von Texten vor, da hier keine Informationen weggelassen werden können sondern der originale Text wiederhergestellt werden muss.
Die Caches der Serie, die bislang veröffentlicht wurden, sind:
Grundlagen
Wie jedes Kind weiß, kann ein Computer nur 0 und 1 verarbeiten, eine solche Einheit nennt man 1 Bit. Wenn man Buchstaben darstellen will, muss man diese in eine Folge von 0 und 1 "übersetzen". Eine Tabelle für eine mögliche Übersetzung findet ihr hier (für Experten und solche, die es werden wollen: hier wird latin-1 verwendet, ich will hier nicht auf Details wie Zeichenkodierungen sowie Umrechnung in Binärform aufhalten. Daher: für diejenigen, denen so etwas fremd ist, der kann einfach die Tabelle benutzen.)
| A |
01000001 |
N |
01001110 |
| B |
01000010 |
O |
01001111 |
| C |
01000011 |
P |
01010000 |
| D |
01000100 |
Q |
01010001 |
| E |
01000101 |
R |
01010010 |
| F |
01000110 |
S |
01010011 |
| G |
01000111 |
T |
01010100 |
| H |
01001000 |
U |
01010101 |
| I |
01001001 |
V |
01010110 |
| J |
01001010 |
W |
01010111 |
| K |
01001011 |
X |
01011000 |
| L |
01001100 |
Y |
01011001 |
| M |
01001101 |
Z |
01011010 |
| Leerzeichen |
00100000 |
° |
10110000 |
| . |
00101110 |
ü |
11011100 |
Wie aus obiger Tabelle ersichtlich wird jedes Zeichen aus einer Folge von 8 Stellen mit jeweils dem Wert von 0 oder 1 definiert (diese Stellen nennt man Bits). Mit 8 Bits, die man auch als 1 Byte bezeichnet, kann man 256 verschiedene Kombinationen von 0 und 1 erzeugen und somit 256 verschiedene Zeichen darstellen. In unserer obigen Tabelle sind aber nur 30 Zeichen enthalten, man braucht also gar nicht die ganze Bandbreite an Möglichkeiten. Dies eröffnet verschiedene Möglichkeiten die Daten zu komprimieren.
Teil 1 - Lauflängenkodierung
Die Lauflängenkodierung ist ein recht simples Verfahren und funktioniert, abhängig von den Eingangsdaten mal mehr mal weniger gut. Man zählt nun einfach die Anzahl der aufeinander folgenden Nullen und anschließend der aufeinander folgenden Einsen und speichert diese ab. So wäre 1 1 5 1 zu übersetzen in 01000001, was einem "A" entspricht.
Das ist dann eigentlich auch schon alles. Der Cache befindet sich dann bei:
1123316111122121211131111111213161232131111111111111231112616112112111131131111121212161112211311111
4211214111222113212321311111111111112331611122112121113111114121311111233161511142112141111141612421
6131111122313211126161321213312321323113211122112121113111114121311111233161232111111111223122416111
122121211131111111211
Noch eine letzte Anmerkung für die Theoretiker unter uns: die ursprüngliche Zeichenkette ist 69 Zeichen lang, kodiert man jedes Zeichen mit 8 Bit (=1 Byte), benötigt man 552 Bits insgesamt. Die kodierte Zeichenkette sind 322 Zeichen. Es kommt maximal die Zahl 6 vor, dann genügt für jede Stelle 3 Bits (2^3 = 8). Man benötigt also für die kodierte Zeichenkette 996 Bit - deutlich mehr als für die ursprüngliche Zeichenfolge. Wer kennt das nicht, man zippt eine Datei am Computer und wenn's dumm läuft verkleinert sie sich gar nicht und wird im Extremfall sogar mal größer. Wie es besser geht, erfahrt ihr im nächsten Teil.