Komprimierverfahren

[Sven Rautenberg]

Moin!

Kennst du vieleicht einen Link oder so:

Denn ich würde es gerne ganz genau wissen wie das Bit für Bit abläuft.

Datenkompression läuft üblicherweise durch Reduzierung der Redundanz ab.

Ein Beispiel:

Du hast die vier Symbole A, B, C und D. Diese vier Symbole kann man binär recht simpel so darstellen:
A = 00
B = 01
C = 10
D = 11

Mit dieser Methode kann man dann beliebige Symbolabfolgen speichern.

Wenn nun aber das Symbol A wesentlich häufiger vorkommt, als die anderen Symbole, dann ist es Verschwendung, ganze zwei Bit für dieses Symbol aufzuwenden.

Angenommen, die Symbolhäufigkeit der Symbole liegt so verteilt:
A = 50%
B = 25%
C = 20%
D = 5%

Dann läßt sich eine Kodierung finden, die letztendlich kürzer ist:
A = 0
B = 10
C = 110
D = 111

Vergleich: Wenn du die Symbolfolge DCCCCBBBBBAAAAAAAAAA (das sind 20 Symbole mit exakt der angegebenen Häufigkeit) hast, wird gemäß der 2-Bit-Codierung die entstehende Bitfolge 40 Bit lang sein.

Mit der angepaßten Codierung sparst du:
10x A  = 10 Bit
5x  B  = 10 Bit
5x C+D = 15 Bit
Summe  = 35 Bit = 5 Bit oder 12,5% Datenmenge weniger.

Du darfst das ganze gerne mal für 256 ASCII-Zeichen durchprobieren.

Das ist nur ein Beispiel (und dürfte IIRC unter "Quellencodierung" laufen). Weitere Möglichkeiten bestehen natürlich, wenn man die Regelmäßigkeit der Zeichenabfolge berücksichtigt.

Im Beispielstring kommen die Buchstabenfolge A hintereinander relativ häufig vor. Wenn man das ausnutzen könnte...

Das Zeichen D ist am seltensten. Deshalb wird es zum Sonderzeichen erklärt, um eine Komprimierungssequenz einzuleiten. Wenn ein D vorkommt, folgt als nächstes Zeichen das komprimierte Zeichen, und als nächstes Zeichen die Anzahl der komprimierten Zeichen - dazu wird dann der Binärcode des Zeichens genommen (siehe erste Codiertabelle). Auf diese Weise kann man Null bis drei Zeichen zusammenfassen. Null Zeichen macht keinen Sinn, also sollte noch 1 addiert werden, um von 1 bis 4 Zeichen zusammenzufassen.

Aus
DCCCCBBBBBAAAAAAAAAA
wird
DDADCDDBDDBADADDADDAB
1xD4xC4xB1xB4xA4xA2xA

Irgendwie nicht so erfolgreich - die Zeichenfolge wird länger. Das liegt daran, dass maximal vier Zeichen leider nur in drei Zeichen komprimiert werden können.

Eine andere Strategie: Hinter jedem echten Zeichen kommt die Anzahl seiner Wiederholungen (a = 1x, d= 4x, die Kleinbuchstaben nur zur Unterscheidung)
DaCdBdBaAdAdAb
statt
DCCCCBBBBBAAAAAAAAAA
Immerhin 6 Zeichen gespart, weil so viele Zeichen mindestens doppelt vorkommen.

Du siehst: Je nach Datenmaterial kann bzw. muß man eine unterschiedliche Strategie benutzen und unter Umständen die Art der Codierung anpassen, um optimale Ergebnisse zu erhalten.

Unter Linux weit verbreitet ist z.B. gzip, was im Grunde nichts anderes als der bekannte ZIP-Mechanismus ist. Außerdem gibt es bzip2, welches wesentlich bessere Komprimierungsraten erzielt. Der Grund ist, dass bzip2 einfach einen anderen Ansatz zur Komprimierung gewählt hat (in irgendeiner c't war der Algorithmus mal beschrieben: Die Datenbytes werden in ein Array geschrieben, jeder Eintrag mit einem anderen Startoffset. Dieses Array wird dann sortiert und irgendwie komprimiert. Die spannende Frage: Wenn 1 Megabyte an Daten zu komprimieren ist, müssen alle Offsets dieses 1-Megabyte-Strings in einem Array sortiert werden. 1 Megabyte Daten mal 1 Megabyte an Offsets ist aber 1 Terabyte  an Daten - das läßt sich ohne Tricks unmöglich sortieren), der offensichtlich erfolgreicher allgemeine Daten komprimiert. Von den ganzen Spezialverfahren für verlustbehaftete Komprimierung (MP3, Ogg Vorbis, RealAudio, ...) mal ganz zu schweigen.

- Sven Rautenberg