Datenkompression
Als Datenkompression werden Verfahren und Algorithmen bezeichnet, die große Datenmengen verkleinern, sodass sie weniger Speicherplatz oder Übertragungs-Bandbreite benötigen. Ein brauchbares Kompressionsverfahren besteht dabei aus zwei Algorithmen:
- einem Algorithmus zum Komprimieren, der die Daten verkleinert
- einem Algorithmus zum Dekomprimieren, der aus komprimierten Daten wieder das Original herstellt.
Dabei unterscheidet man zwischen verlustbehafteter und verlustfreier Kompression. Der Unterschied ist der, dass sich bei der verlustfreien Kompression alle ursprünglich enthaltenen Informationen aus den komprimierten Daten rekonstruieren lassen, während bei der verlustbehafteten Kompression Information verloren geht.
Nach der Kompression dividiert man dann die Größe der komprimierten Daten durch die Größe der unkomprimierten Daten und erhält den Kompressionsfaktor.
Verlustbehaftete Kompression
Ein einfaches verlustbehaftetes Kompressionsverfahren ist es, einfach alle Vokale aus einem Wort zu streichen: aus VERLUSTBEHAFTETE KOMPRESSION wird VRLSTBHFTT KMPRSSN.
Für dieses Beispiel ergibt sich ein Kompressionsfaktor von , was nicht schlecht ist.
Allerdings lassen sich die ursprünglichen Daten nicht immer eindeutig rekonstruieren: aus dem komprimierten Wort RGNTNN lassen sich zum Beispiel die Wörter ARGENTINIEN und REGENTONNE dekomprimieren. Hier geht also Information verloren.
Verlustbehaftete Kompression wird überall dort eingesetzt, wo kleinere Datenmengen wichtiger sind als perfekte Vollständigkeit der Information, etwa bei Bildern (JPEG) oder Musik (MP3).
Denken wir beispielsweise an Videostreaming: ein Frame eines Full-HD-Videos besteht aus Pixeln. Jeder Pixel umfasst typischerweise 24 Bit Farbinformation. Nehmen wir außerdem mal dreißig Frames pro Sekunde an, dann multipliziert sich das auf , also ca. 1,5 Gigabit Daten pro Sekunde – und da ist der Ton noch nicht mal mit berücksichtigt.
Also muss man die Daten komprimieren. Beim MP3-Verfahren geschieht dies zum Beispiel dadurch, dass für Menschen unhörbare Frequenzbereiche herausgefiltert werden. Beim JPEG-Verfahren für Bildkompression wird ein Bild in Quadrate zerlegt, deren Inhalt durch mathematische Beschreibungen angenähert wird. Je größer die Quadrate (siehe Bild), desto mehr leidet die Qualität.
Verlustfreie Kompression
Auch ohne Datenverlust können Daten komprimiert werden. Damit lassen sich natürlich nicht so hohe Kompressionsraten wie bei verlustbehafteten Formaten erzielen, aber dafür lassen sich die Daten vollständig rekonstruieren.
Verlustfreie Kompressionen wie PNG oder FLAC beruhen meistens auf der Idee, gleichförmig Muster zu erkennen und verkürzt abzuspeichern. Bei Bildern können das z.B. große einheitliche Farbflächen sein, bei Texten Segmente, die sich wiederholen.
Mit Algorithmen wie der Lauflängencodierung, der Huffman-Codierung oder der LZW-Codierung lassen sich beliebige Daten verlustfrei komprimieren.
Nehmen wir das Wort RHABARBERBARBARABARBARBARENBARTBARBIERBIERBARBABY[1], das aus 57 Zeichen besteht. In diesem Wort finden sich gewisse Muster, die man abkürzen kann: zum Beispiel können wir alle BAR durch $ ersetzen und erhalten RHA$BER$$A$$$EN$T$BIERBIER$BABY, das nur noch aus 39 Zeichen besteht. Verbunden mit der Information, dass das $ zu BAR aufgelöst werden muss, lässt sich das RHABARBERBARBARABARBARBARENBARTBARBIERBIERBARBABY also mit 44 Zeichen darstellen als $BAR:RHA$BER$$A$$$EN$T$BIERBIER$BABY, ohne dass ein Stück Information verloren geht.
