Eine kurze Einführung in die Datenkomprimierung
- Einleitung - Lauflängenkodierung - Kodierung mit variabler Länge - Der Huffman-Algorithmus - Implementation in C bzw. C++
Einleitung
Es gibt unterschiedliche Ansätze wie Daten komprimiert werden können, ich werde im folgenden auf zwei Ansätze eingehen, wobei ich zuerst eine Einfache, die sog. Lauflängenkodierung, und dann eine Optimale, sehr effizientere Methode, die Huffman-Kodierung, besprechen werde. Alle Komprimierungsalgorithmen beruhen auf Verfahren, die Redundanzen (z.B. Zeichenwiederholungen) ausnutzen um diese kürzer zu fassen, zu Komprimieren. Daher sind Dateien, die aus perfekt zufälligen Bits bestehen nicht komprimierbar, wogegen Dateien mit hoher Redundanz sehr stark komprimierbar sind. Dateien, die nicht komprimierbar sind, entweder wegen den perfekten Zufallsbits oder weil sie schon einmal mit dem gleichen Verfahren komprimiert wurden, werden bei einer erneuten Komprimierung nicht mehr kleiner, sondern um ein paar Bits, die vom Verfahren abhängen, größer. Allerdings wird von einigen Verfahren eine absichtliche Redundanz in die komprimierte Datei eingebaut, damit Fehler bei der Dekomprimierung evtl. behoben oder übersprungen werden können. Es ist daher unter Umständen möglich, ein Verfahren, das eine relativ hohe "Rest-Redundanz" hat mit einem Verfahren, das eine geringere "Rest-Redundanz" hat, weiter zu komprimieren.
Lauflängenkodierung
Die Lauflängenkodierung (run-length encoding) nutzt die einfachste Art einer Redundanz aus, die Wiederholung von Zeichen. Ein Beispiel ist folgende Zeichenkette: AAAAAAAAAAVVVVVVVCCCCCCCCCSSSSSSSSSDDDDDDGGGGGGGGGGGGGG Diese Zeichenkette könnte man Komprimieren, indem man vor dem entsprechenden Zeichen seine Anzahl angibt: 10A7V9C6D14G Wenn allerdings nur ein Zeichen ein Mal auftritt würde aus einem Zeichen nach der Kodierung zwei Zeichen werden, daher werden einzelne Zeichen nicht kodiert. Zeichenpaare können entweder kodiert werden, oder nicht, das ergibt hier erstmal keinen Unterschied. Man kann diese Form der Kodierung sehr gut auf binäre Daten erweitern. Bei binären Daten kommen nur Bits vor. Bits können nur zwei Werte annehmen 0 oder 1, der Vorteil ist, dass man weiss, dass nach jeder 0 eine 1 folgen muss, daher braucht man bei der Lauflängenkodierung nur die Länge zu speichern. Beispiel: 0000000000111111111111111001111111111 -> 10 15 02 10 1111111111111111111111111111111111111 -> 37 0111111111111111111111111111111111110 -> 01 35 01 0001111111111111111111111111111111000 -> 03 31 03 Beim ersten Beispiel haben wir das Problem, dass keine Zahlen auftreten dürfen, damit die Kodierung klappt, dies haben wir in der binären Variante nicht, allerdings funktioniert die binäre Variante nur, wenn oft, lange Folgen von Nullen und Einsen aufeinander folgen, dies ist schon bei einfachem Text nicht der Fall. Man kann die Lauflängenkodierung durch sog. Escape-Zeichen, zum Beispiel bei der Text-Kodierung ein Zeichen, das nie im Text auftreten wird (z.B. ASCII 0x02), weiter verfeinern, aber gut Komprimierbar sind die meisten Texte, wegen der fehlenden Lauflängenredundanz, nicht. Hier noch ein Beispiel einer Implementation in C <lauflaengen_kompimierung.c>, es können nur Texte kodiert werden, da für die Kodierung das Escape-Zeichen 0x02 ge- nutzt wird, das in binären Dateien jedoch auch auftritt. Nach dem Escape-Zeichen wird die Länge des sich wiederholenden Zeichens und das eigentliche Zeichen ein gefügt. Es entsteht daher eine binäre Datei.