Kompressionsverfahren

Bei der Kompression von Informationen gibt es zwei Herangehensweisen, die verlustfreie und die verlustbehaftete.
Warum man über Datenverlust hinnimmt und welche spezifischen Verfahren in die Kategorien fallen, erklären wir jetzt.

expand_more

Verlustfreie Datenkompression

Bei der verlustfreien Kompression geht es darum, den Informationsinhalt so zu reduzieren, dass man ihn bei Reproduktion exakt wiederherstellen kann. Dabei werden redundante Datenbestände komprimiert, ohne Informationen zu verändern oder zu entfernen. Die Kompression erfolgt durch Datenreduktion und ist am häufigsten in Textkompression, Audiokompression und Bildkompression vertreten.

Bekannte und wichtige Verfahren:
ZIP-Dateiformat
RAR-Dateiformat
LZW-Algorithmus

Die HUFFMAN-Codierung ist eine Quellencodierung für Text- und Bildkompression und basiert auf Redundanz der Zeichenhäufigkeit, zum Beispiel hat man in einem Text Buchstaben wie "e", die häufig vorkommen und diese werden durch kurze Signalcodes ersetzt (3 Bit "short hand"), wobei man 5 Bit spart, Buchstaben wie "y", die etwas seltener vorkommen, werden dann durch etwas längere Signalcodes ersetzt. Dies wird genauso auf Farben angewandt, Farben wie Grün kommen häufiger vor als Farben wie Gelb, dadurch ist die HUFFMAN-Codierung variable und kann anhand der Häufigkeit festgelegt werden.

Beispiel einer Huffman-Codierung auf ITWissen

Bei der Lauflängencodierung haben die codierten Ziffern, Zeichen und Buchstaben eine unterschiedliche Anzahl an Bits und da die Länge der codierten Zeichen unterschiedlich ist, heißt die Codierung Lauflängencodierung. Es geht hierbei darum, eine Folge von gleichen Zahlen, Zeichen oder Buchstaben durch ein einziges Symbol zu ersetzen (RUN), hierbei können viele Buchstaben mit 2 Bytes ersetzt werden. Die Lauflängencodierung beseitigt Redundanzen in Form von Wiederholungen und eignet sich besonders für Grafiken.

Beispiel unterschiedlicher Effizienzraten bei Lauflängencodierung auf ITWissen
Zeichen Häufigkeit Codierung Speichergröße

Verlustbehaftete Datenkompression

Bei der verlustbehafteten Datenkompression wird die Größe einer Datei verringert, wobei Informationen, welche in der Datei vorhanden sind verloren gehen. Die Änderungen sind meist in einem Maße vorgenommen, indem sie nicht die Qualität des Inhaltes beeinträchtigen. Einige der bekanntesten komprimierten Dateitypen sind JPEG, MP3 und MP4.

Bei dem JPEG Format werden in der Originaldatei große Mengen an Pixeln, welche eine sehr Ähnliche Farbe haben zu einer Einzelnen Farbe geändert. Ein gutes Beispiel dafür ist ein blauer Himmel. Hier gibt es sehr viele verschiedene Blautöne, welche man kaum voneinander unterscheiden kann. Somit werden sie zu weniger Blautönen zusammengefasst und dadurch können diese per verlustfreien Kompressionsverfahren effizienter gespeichert werden.

Bei den MP3 Dateien werden von der Originaldatei Töne entfernt, welche ein Mensch nicht hören kann. Zudem werden sehr ähnlich klingende Töne hier auch zusammengefasst. Da ein Ton ein durchgängiges Geräusch ist, muss ein passender Intervall, in dem die Töne gespeichert werden gewählt werden, da ein Ton in einer Sekunde theoretisch unendlich viel Speicherplatz bräuchte.

Das MP4 Format ist etwas komplexer als JPEG, da hier ein Video und damit auch der zeitliche Aspekt untersucht werden muss. Nehmen wir zur Erklärung an, dass wir in einem Video mit 20 Frames komprimieren. In diesem Abschnitt des Videos sind 10 Frames gleich. Deshalb muss dies nur einmal abgespeichert werden. Die einzelnen Frames werden wie bei JPEG komprimiert, wobei man hier noch einmal prüft, ob es in den Frames ein durchgehend gleiches Element, zum Beispiel ein schwarzes Quadrat, enthalten ist. Wenn dieses Quadrat in mehreren Frames auftaucht, wird es auch nur einmal gespeichert und auf mehrere Frames angewandt. Zuletzt wird die gleiche Methode wie bei JPEG bei den noch nicht komprimierten Teilen genutzt

Bild von Simon Berger auf Unsplash

Aufgaben

Verlustfreie Datenkompression
  1. Komprimiere die Ente wie in den oberen Beispielen! Hinweiß: das Feld ist 10x10 Pixel groß Weiß=w; Gelb=g; Schwarz=s; Rosa=r, Orange=o; Rot=f;
Eine kleine Pixel-Ente (Künstler: Lucas)
Lösung

2w, 6g, 2w
1w, 2g, 1s, 2g, 1s, 2g, 1w,
1w, 1g, 1r, 2g, 1o, 1g, 1r, 1g, 1w,
1w, 3g, 2o, 3g, 1w
2w, 6g, 2w
10g
10g
1w, 8g, 1w
2w, 6g, 2w
3w, 1f, 2w, 1f, 3w

Verlustbehaftete Datenkompression
  1. Füge ein Bild von deinem Computer in ein Programm wie IrfanView ein und exportiere es als .jpg in verschiedenen Komprimierungsraten. Ab wann ist der Unterschied an Qualität deutlich sichtbar?
  2. Fertige selbst einen Huffman-Baum von der Buchstabenfolge: "ABEDBADDEBAABBBCEECA" (insgesamt 20 Zeichen) an und überprüfe dein Ergebnis mit unserem Huffman-Generator. (Beachte, dass Zeichen mit einer gleichen Häufigkeit vertauscht angeordnet werden kann.) Wie viel Speicherplatz hast du dadurch gespart?

Quellen

Hero Image
Bild von Martin Vorel auf LibreShot | leicht verändert
Verlustfreie Datenkompression
Verlustfreie Verfahren (Universität zu Köln)
Lauflängencodierung (Margarita Isjurowa)
Huffman-Codierung (ITWissen)
Lauflängencodierung (ITWissen)
Verlustbehaftete Datenkompression
How File Compression Works (Youtube: Mental Outlaw)
Datenkompression (Wikipedia)
Kein Internet ohne Datenkomprimierung! Wie funktioniert Zip, MP4 Filme, JPEG Bilder, MP3 Musik ? (Youtube: Rene Fürst)
Datenkompression (Erasmus-Reinhold-Gymnasium)
JPEG (Wikipedia)
MP4 (Wikipedia)
MP3 (Wikipedia)