Filter: Kodierung

Bei vielen Kompressionsarten kommt, als Filter, die Lauflängenkodierung zum Einsatz. Sie ist sehr einfach, sehr schnell aber auch sehr spezialisiert, da bei ihr gleiche aufeinander folgende Symbole zusammengefasst werden. Diese Kodierung ist anzutreffen bei vielen Grafikformaten (inklusive JPEG).

Beispiel (Quellcode): rle.cpp
Download (Quellcode): rle.zip

Beschreibung

Wie schon erwähnt, werden gleiche aufeinander folgende Symbole zusammengefasst. Dies geschieht oft durch einen Marker, ein Spezialsymbol oder durch eine andere Art von Metadaten innerhalb des Ausgabedatenstroms. Bei Kodierungsverfahren mit Codewörtern, lassen sich extra Codes verwenden. Die Länge der Symbolwiederholungen, die benötigt wird, um eine Datenkompression zu erreichen hängt vom Kodierungsverfahren ab. Bei einfachsten Implementationen, lohnt sich der Aufwand oft erst, wenn mindestens vier oder fünf gleiche aufeinander folgende Symbole möglich sind.

Wie bei eigentlich allen Kompressionsverfahren, kann auch bei RLE unter Umständen ü…

Die Bereichskodierung ist, neben der Huffman-Kodierung, eine mittlerweile häufig anzutreffende Entropiekodierung. Sie ist einfach zu realisieren, kommt der theoretischen Entropie näher, ist aber etwas langsamer. Vor allem in Szenarien mit starken dynamischen oder extremen Symbolwahrscheinlichkeiten macht sich diese Kodierung bezahlt. Im Gegensatz zur Huffman-Kodierung ist die Untergrenze von einem Bit pro Symbol in der Ausgabe aufgehoben, so dass rein vom Betrachter aus, mehr als ein Symbol pro Bit gespeichert werden kann. Dieses Verfahren wird z.B. bei LZMA/7Zip, PPM, PAQ und bei sehr vielen aktuellen Audio-/Videokompressionen eingesetzt.

Beispiel (Quellcode): rangecoder.cpp
Download (Quellcode): rangecoder.zip

Beschreibung

Eine Bereichskodierung ist eine Art der arithmetischen Kodierung, jedoch wird nur mit einem Ausschnitt des Ausgabewertes gerechnet. Die arithmetische Kodierung besitzt einen Ausgabewert und den Bereichswert. Der Ausgabewert ist mit Null initialisiert und der Wert, der später in die A…

Die Speicherung von Ganzzahlen kann, je nach Datentypgröße viel Platz auf dem Datenträger oder im Speicher in Anspruch nehmen. Werden aber hauptsächlich kleine Werte erwartet, zum Beispiel bei Deltaeinträgen, ist der Großteil des Wertes nicht belegt. Hier springt diese Art der Kodierung ein und versucht die Werte soweit es geht zu kürzen.

Beispiel (Quellcode): vlq.cpp
Download (Quellcode): vlq.zip

Beschreibung

Die Ganzzahl wird in Teile (meist) gleicher Größe aufgeteilt. Alle oberen Teile die keine Bits gesetzt haben werden nicht in die Ausgabe geschrieben. Alle Teile, bis auf den Letzten, bekommen einen Marker, dass der nachfolgende Teil nicht das Ende darstellt. Häufig werden die Zahlen in 7-Bit Teile gebrochen und mit übrigen Bit des Ausgabebytes markiert.

Es gibt hier allerdings viele Varianten, die häufigsten Unterscheidungen sind:

• Richtung
  • höherwertiger Teil zuerst
  • niederwertiger Teil zuerst
• Position des Markers im Ausgabebyte
• Vorzeichenbehandlu…

Die Huffman-Kodierung stellt neben der arithmetischen Kodierung bzw. der Bereichskodierung eine der häufigsten Formen der Entropiekodierung dar. Es wird und wurde vor allem, wegen der hohen Geschwindigkeit in älteren Kompressionsverfahren eingesetzt, von ZIP/Deflate über RAR bis hin zu JPEG. Allerdings gibt es auch einen kleinen Nachteil: Die Kodierung erreicht nicht immer die theoretische Entropie, da sie nur auf Bitbasis arbeitet.

Beispiel (Quellcode): huffman.cpp
Download (Quellcode): huffman.zip

Beschreibung

Diese Art der Kodierung, errechnet mit Hilfe der Symbolauftrittswahrscheinlichkeiten (oder auch Häufigkeiten), einen möglichst kurzen und eindeutigen Code. Kommt ein Symbol häufiger vor, wird es durch einen kürzeren binären Code ausgedrückt. Werden nicht alle Symbole des Alphabets benötigt, fließen diese nicht weiter in die Bearbeitung ein. Grundsätzlich kann unterschieden werden zwischen statischer, dynamischer und adaptiver Huffman-Kodierung. Die statische hat festgelegte Symbolhäufigkeiten, die…