communityWir suchen ständig neue Tutorials und Artikel! Habt ihr selbst schonmal einen Artikel verfasst und seid bereit dieses Wissen mit der Community zu teilen? Oder würdet ihr gerne einmal über ein Thema schreiben das euch besonders auf dem Herzen liegt? Dann habt ihr nun die Gelegenheit eure Arbeit zu veröffentlichen und den Ruhm dafür zu ernten. Schreibt uns einfach eine Nachricht mit dem Betreff „Community Articles“ und helft mit das Angebot an guten Artikeln zu vergrößern. Als Autor werdet ihr für den internen Bereich freigeschaltet und könnt dort eurer literarischen Ader freien Lauf lassen.

Datenkompression PDF Drucken E-Mail
Benutzerbewertung: / 10
SchwachPerfekt 
Geschrieben von: Stefan Behm   
Donnerstag, den 02. Januar 2014 um 17:20 Uhr
Beitragsseiten
Datenkompression
Huffman-Codierung
Alle Seiten

Einführung

Die Datenkompression oder Datenkomprimierung ist ein Vorgang, bei dem die Menge digitaler Daten reduziert wird. Die Vorteile der Datenkomression liegen auf der Hand. Dieselben Daten können mit erheblich weniger Speicherkapazität persistiert werden. Die Datenübertragung wird verkürzt und Ressourcen können eingespart werden. So ebnete das MP3-Format den Weg zum Austausch von Musik über das Internet. Das Verfahren zur verlustbehafteten Kompression digital gespeicherter Audiodaten wurde Anfang 1990 bekannt und ermöglichte eine Einsparung der benötigten Speichergröße um den Faktor 10, gegenüber dem bis dato verwendeten WAV-Format, bei nicht oder nur kaum verringerter wahrgenommener Audioqualität.

Bei der Datenkompression ist man primär an einem sog. Codiergewinn interessiert, der sich als Differenz aus der Darstellung der Information gegenüber einer alternativen Darstellung der gleichen Information ergibt. Man spricht von einem Codiergewinn, wenn sich die alternative Darstellung als effizienter (kürzer) erweist, als die ursprüngliche Darstellung der Information. Grundsätzlich wird bei der Datenkompression versucht, überflüssige Information zu entfernen. Dazu werden die Daten in eine Darstellung überführt, mit der sich alle – oder zumindest die meisten – Informationen in kürzerer Form darstellen lassen. Diesen Vorgang übernimmt ein Kodierer und man bezeichnet den Vorgang als Kompression oder Komprimierung. Die Umkehrung bezeichnet man als Dekompression oder Dekomprimierung.

Fundamentalprinzipien der Datenkompression

Die Datenkompression bzw. Datenreduktion ist nur aufgrund zweier fundamentaler Prinzipien möglich. Das Erste ist die Entfernung von Redundanz (Kompression) i.e.S. und das Zweite ist die Entfernung von Irrelevanz (Reduktion) aus einer beliebigen Informationsquelle. Der Unterschied zwischen Kompression und Reduktion liegt bei näherer Betrachtung auf der Hand: Bei der Kompression (i.e.S) bleiben die Originaldaten nach der Abbildung (Kompressionsvorgang) vollständig rekonstruierbar und im Sinne einer Rückabbildung erhalten. Mathematisch formuliert spricht man von einer bijektiven Abbildung. Bei der Datenreduktion hingegen sind die Originaldaten nach dem Abbildungsvorgang nicht immer fehlerfrei rekonstruierbar. Das bedeutet, es kommt zu einem Fehler zwischen den Originaldaten und den rekonstruierbaren Daten. Eine Rückabbildungsvorschrift ist zwar vorhanden, diese ist jedoch nicht in der Lage, sämtliche Originaldaten einwandfrei wieder herzustellen.

Redundanzreduktion

Als redundant bezeichnet man umgangssprachlich Informationen oder Daten, die sich aufgrund bereits überlieferter/übertragener Informationen durch Deduktion ableiten lassen. Es ist demnach nicht notwendig diese sog. redundanten Daten gesondert, zusätzlich oder überhaupt zu übertragen. Redundanz beschreibt den Grad der Vorhersagbarkeit von Teilen einer Nachricht und ist durch die Entropie festgelegt.

Die Redundanz innerhalb einer Nachricht/Information lässt sich mathematisch exakt bestimmen. Es ist trotzdem weder mit beliebigem technischem oder mathematischem Aufwand möglich eine größere Menge an Redundanz aus einer Nachricht zu entfernen, als die Nachricht enthält. Es sei denn man verfälscht die ursprüngliche Nachricht oder nimmt bewusst Fehler in der rekonstruierten Nachricht in Kauf.

Die Vermeidung von Redundanz erfolgt mit den Methoden zur verlustfreien Datenkompression. Bei der verlustfreien Datenkompression geht es darum, die zu übertragende Nachricht durch eine kürzere aber äquivalente Nachricht zu ersetzen, sie anschließend zu übertragen und auf der Seite des Empfängers fehlerfrei zu rekonstruieren. Bei der Codierung unterscheidet man statistische, Wörterbuch-basierende und kombinierte Ansätze.

Irrelevanzreduktion

Als irrelevant bezeichnet man Informationen oder Daten, die vom Beobachter bzw. Empfänger nicht wahrgenommen werden können oder deren Genauigkeit nicht hinreichend wahrnehmbar ist. Als schlechtes Beispiel könnte man einen Rot/Grün-Blinden wählen, der bekanntlich schwer zwischen Rot und Grün unterscheiden kann. Durch die fehlende Unterscheidbarkeit beim Empfänger würde es bspw. ausreichen, wahlweise den Rot oder den Grün-Anteil zu übertragen. Das heißt man benutzt physiologische Grundlagen, Gegebenheiten und Modelle um zu entscheiden, ob eine Information eine Übertragung wert ist oder nicht. Das MP3-Format nutzt die Irrelevanzreduktion, indem sie Frequenzen ausfiltert, die normalerweise vom menschlichen Gehör nicht wahrgenommen werden können.

Bei der Irrelevanz ist es mittels technischer oder mathematischer Modelle möglich, relevante Informationen von irrelevanten Informationen zu trennen. Meist müssen dazu komplexe Modelle, Messmethoden oder empirische Werte gefunden werden, anhand derer die Entscheidung vorgenommen werden kann, ob eine Information relevant oder irrelevant ist. Dabei spielen insbesondere objektive und subjektive Kriterien eine Rolle.

Darüber hinaus ist es möglich, nicht nur nicht hinreichend wahrnehmbare Informationen zu unterschlagen, sondern bewusst auch wahrnehmbare Fehler in Kauf zu nehmen, um so die zu übertragende Information an die Art der Codierung anzupassen. Der Vorteil der Anpassung an die Art der Codierung besteht darin, dass der Codierer entscheiden kann, welche Modifikation während der Codierung zu einer besseren Kompressionsleistung führen. Der Codierer erzeugt durch die Modifikation sog. Kompressionsartefakte, die es dem Codierer möglich machen eine vorgegebene Kompressionsrate zu erreichen oder zu unterschreiten. Die Verfahren mit denen diese Art der Codierung erreicht werden kann, werden im Kapitel Verlustbehaftete Kompression behandelt.

Verlustfreie oder verlustbehaftete Datenkompression

Grundsätzlich unterscheidet man zwischen verlustfreier oder verlustbehafteter Datenkompression. Man spricht von verlustfreier Kompression (oder verlustfreier Kodierung), wenn aus den komprimierten Daten wieder alle Originaldaten gewonnen werden können. Das ist beispielsweise bei der Kompression ausführbarer Programmdateien notwendig.

Bei der verlustbehafteten Kompression können die Originaldaten nicht mehr aus den komprimierten Daten zurückgewonnen werden, das heißt ein Teil der Information ging verloren. Solche Verfahren werden häufig zur Bild- oder Videokompression und Audiodatenkompression eingesetzt.

datenkompression

Datenkompression in der Informationstheorie

Es gibt eine Vielzahl von Beispielen, anhand derer gezeigt werden kann, dass die verlustfreie oder verlustbehaftete Datenkompression sinnvoll sind. Die Datenkompression ist eng mit der Informationstheorie, wie sie von Claude Shannon im Jahr 1948 formuliert wurde, verbunden. Die Informationstheorie und die Informationstheoretischen Ansätze haben nach über 50 Jahren der Existenz derart viele Bereiche berührt, dass die moderne Informatik und Informationstechnik nicht ohne diese theoretische Abhandlung denkbar wären. Heute geht es mehr denn je, um die Speicherung und Verarbeitung digitaler Daten und es ist völlig egal in welche Richtung man blickt. Die moderne Medizin kommt heute nicht ohne bildverarbeitende Methoden aus. Nachdem die Information digital wurden, suchte man nach Möglichkeiten sie auch digital zu übertragen, digital zu speichern und digital zu verarbeiten. Erst dadurch gelang es Informationen digital und somit verlustfrei zu verarbeiten oder zu kopieren.

Nachdem die Information digital aufgezeichnet werden konnte, wollte man erfahren, wie viel Information tatsächlich in einer Nachricht steckt. Diese Frage ist sowohl von philosophischem, als auch von ingenieurstechnischem Interesse. Die ingenieurstechnischen Fragen beantwortete Claude Elwood Shannon (Vater der Informationstheorie) mit seiner berühmt gewordenen Arbeit "A Mathematical Theory of Communication". Sie wurde 1949 unter dem Titel "The Mathematical Theory of Communication" leicht erweitert und erneut veröffentlicht.

Information: der negative Kehrwert der Wahrscheinlichkeit.

Die Informationstheorie gibt durch den Informationsgehalt eine minimale Anzahl an Bits vor, die zur Kodierung eines Symbols benötigt werden. Dabei ist die Entropie ein Maß für den mittleren Informationsgehalt oder auch Informationsdichte einer Nachricht. Der Begriff in der Informationstheorie ist in Analogie zur Entropie in der Thermodynamik und Statistischen Mechanik benannt.

Je kleiner die Auftrittswahrscheinlichkeit eines Zeichens ist, desto höher ist seine Information. Andersherum ist die Information eines Zeichens gering, wenn es oft vorkommt. Eine niedrige Entropie bedeutet, dass es mehr redundante Informationen gibt und es lassen sich somit gute Kompressionsraten erzielen. Aus einer niedrigen Entropie kann man auf regelmäßige Strukturen in der Nachricht schließen. Umgekehrt gilt: ist die Entropie hoch, so sind weniger redundante Informationen in der Nachricht enthalten und sie lässt sich nur schlecht komprimieren. Die Entropie kann somit als Maß dafür gewertet werden, wie gut sich eine Datenquelle für eine Kompression eignet. Die Entropie spielt auch bei der Generierung von Zufallszahlen und der Verschlüsselung von Daten eine zentrale Rolle. Sie ist auch der Grund, warum beispielsweise verschlüsselte Daten in der Regel nicht mehr effektiv komprimiert werden können.

Nach über 50 Jahren der Informationstheorie gibt es keinen Bereich, der nicht von der Informationstheorie berührt worden ist und es gibt keinen Bereich, der sich früher oder später nicht mit der Codierung und Kompression von Daten bzw. Informationen beschäftigen muss.

Anwendung entwickeln

In diesem Artikel wird die Entropiekodierung zur verlustfreien Datenkompression vorgestellt. Die Entwicklung der Software vollzieht sich in mehreren Schritten. Zunächst werden Klassen zur Serialisierung von Daten entworfen. Anschließend wird die Huffman-Kodierung in C++ implementiert. Am Ende werden die Teilschritte in eine fertige Anwendung integriert, die die Komprimierung von beleibigen Dateien ermöglicht.

Serialisierung von Datentypen

In der Informatik bezeichnet die Serialisierung im Kontext der Datenspeicherung und Datenübertragung den Prozess der Konvertierung von Datenstrukturen oder Objekten in ein Format, das persistent gespeichert oder über ein Netzwerk übertragen werden kann um anschließend in derselben oder einer anderen Umgebung wieder „genutzt“ zu wer-den. Die Serialisierung ist eine Abbildung von Objekten auf eine sequenzielle Darstellung. Wenn die sequenziellen Bits wieder nach dem Objektserialisierungsformat gelesen werden, ist es möglich einen semantisch identischen Klon des Originalobjekts zu erzeugen.

Die Umkehrung der Serialisierung, bei der ein Datenstrom in ein Objekt konvertiert wird, heißt Deserialisierung.

Objektserialisierung

Bei der Entwicklung einer Anwendung zur Datenkomprimierung steht eine konsistente Serialisierung von Objekten im Vordergrund. So müssen nicht nur primitive Datentypen komprimiert werden, sondern auch Bilder und andere komplexe Datenquellen. Anders als beispielsweise JavaTM, unterstützt die Programmiersprache C++ direkt keine Objektserialisierung. Basierend auf dem Qt-Framework werden deshalb zunächst Streaming-Klassen entworfen. Diese Klassen ermöglichen die Serialisierung von Daten zu einem so genannten IODevice. Der binäre Datenstrom ist zu 100% unabhängig von dem laufenden Betriebssystem, sowie unabhängig von der Byte-Reihenfolge der CPU. Die Klassen stellen Methoden für die Serialisierung der grundlegenden C++-Datentypen bereit, wie char, short, int, double, etc. Die Serialisierung von komplexen Datentypen wird durch die Nutzung der primitiven Datentypen realisiert und über die friend-Funktionalität von C++ ermöglicht.

Ziel ist es ein leistungsfähiges Serialisierungmodul zu entwickeln, das zum einen mit allen wesentlichen Datentypen umgehen kann, dabei eine einfach zu bedienende API bereitstellt und bei Bedarf jederzeit erweitert werden kann. Die API, sowie der Aufbau der Datenströme orientiert sich dabei an JavaTM.

Byte-Reihenfolge

Werden Daten bitweise seriell übertragen, so ist die Bit-Reihenfolge festzulegen. Die sogenannte Byte-Reihenfolge oder auch Byte-Order bezeichnet die Speicherorganisation für einfache Zahlenwerte, in erster Linie die Ablage von ganzzahligen Werten im Arbeitsspeicher. Die Festlegung des zu verwendenden Speicherungsformats ist immer dann nötig, wenn zur Codierung der zu speichernden Zahl mehr Bits erforderlich sind, als in der kleinsten adressierbaren Einheit zur Verfügung stehen. Im Regelfall ist die kleinste adressierbare Einheit auf modernen Computerarchitekturen ein Byte bzw. acht Bit. Die Speicherung einer Zahl erfolgt nun, falls hierfür mehr als ein Byte benötigt wird, in mehreren Bytes, so dass diese in den Speicheradressen direkt aufeinander folgen.

Die heute existierenden Varianten der Byte-Reihenfolge beschränken sich fast ausschließlich auf zwei Varianten, „Big-Endian“ und „Little-Endian“, sowie eine Misch-form „Middle-Endian“ beider Varianten.

endianess

In Tabelle sind die drei wichtigen Byte-Reihenfolgen samt Adresse dargestellt. Das Format Little-Endian wurde ursprünglich bei den Intel-x86-Prozessoren verwendet. Dagegen wurde das Big-Endian-Format beispielsweise bei der Motorola beziehungs-weise Coldfire-Familie, sowie Sun-SPARC-CPUs und dem PowerPC eingesetzt. Das Betriebssystem Windows verwendet auf jeder Hardware das Format Little-Endian. Das betrifft x86, x86-64, Alpha, PowerPC, MIPS und Itanium Hardware-Architekturen. Unter Linux ergibt sich ein diversifiziertes Bild. Während Linux für die gängigen Systeme x86 und x86-64 ebenfalls Little-Endian einsetzt, wird z. B. auf einem MIPS, SPARC, PA-RISC, POWER, PowerPC, oder Xtensa auf Big-Endian zurückgegriffen. Das Betriebssystem von Apple, das Mac OS X, verwendet nur noch für den alten PowerPC das Format Big-Endian. Auch die gewöhnliche Darstellung von Dezimalzahlen ist – im Sinne der Leserichtung der meisten europäischen Sprachen von links nach rechts – Big Endian. In der Industrie, sowie auf diversen Plattformen hat sich aber zunehmend Little-Endian durchgesetzt. Sowohl Linux als auch Windows verwenden heute auf modernen x86 und x86-x64 Plattformen Little-Endian, so dass für gewöhnlich die Daten in diesem Format im Speicher abgelegt sind.

Die grundlegenden Unterschiede zwischen Little-Endian und Big-Endian sind:

  • Unter Little-Endian wird das Byte mit den niederstwertigen Bits (engl. least significant bit) an der kleinsten Speicheradresse gespeichert beziehungsweise das kleinstwertige Element zuerst genannt.
  • Unter Big-Endian wird das Byte mit den höchstwertigen Bits (engl. most signi-ficant bit) zuerst gespeichert, das heißt an der kleinsten Speicheradresse. Das bedeutet, dass Daten mit dem größtwertigen Element zuerst genannt werden.

Zahlen werden in Programmiersprachen, wie C++, in der Regel im Format Little-Endian geschrieben. Die Zahl beginnt mit den höchstwertigen Bits und endet mit den niederstwertigen Bits (Leserichtung von links nach rechts). Die interne Darstellung folgt allerdings exakt der umgekehrten Richtung. Das LSB steht am Anfang im Speicher, während das MSB den Schluss markiert.

byte-order

Vor der Übertragung von Datentypen, die mehr als ein Byte im Speicher beanspruchen, wird im Protokoll von der Klasse Endian zunächst die Byte-Reihenfolge des laufen-den Betriebssystems ermittelt. Die Klasse verfügt darüber hinaus über ein Template mit dem Namen ReverseByteOrderImpl. Mit dem Template kann die Byte-Reihenfolge von diversen Datentypen umgekehrt werden. Um die Performance zu stei-gern wurden für die ersten 8 Byte insgesamt vier Template-Spezialisierungen generiert, die über direkte Bit-Manipulationen die Byte-Reihenfolge ändern.

Die Klasse „Stream“

Grundlage für die Serialisierung aller Datentypen ist ein kontinuierlicher Datenstrom. Der Datenstrom oder auch Stream, bezeichnet kontinuierliche Abfolgen von Datensätzen, deren Ende nicht im Voraus abzusehen ist. Die einzelnen Datensätze sind dabei von beliebigem, aber festem Typ. Da fast alle Systeme heute ein Byte als minimalen Datensatz verwenden, bestehen die Abfolgen meist aus einzelnen Bytes. Datenströme werden häufig zur Interprozesskommunikation verwendet.

Der Entwurf der Stream-Klassen beginnt in der Regel bei dem Fundament. Oftmals wird auch zwischen Eingabe- und Ausgabe-Streams unterschieden. Aus diesem Grunde ist es sinnvoll eine abstrakte Basisklasse zu entwerfen, die sowohl für die Ein- als auch für die Ausgabe Methoden und Felder bereitstellt. Die Klasse Stream ist so eine Klas-se. Sie stellt insgesamt sechs virtuelle Methoden zur Verfügung. Darunter befinden sich Methoden zur Festlegung der Byte-Reihenfolge, als auch eine Methode zur Ermittlung der Größe des Datenstroms. Weiterhin werden die Enumeratoren Version und ByteOrder exponiert. Der erste Enumerator dient dazu bei Versionsübergängen Funktionalitäten unterscheiden zu können um beispielsweise eine Abwärtskompatibilität zu gewährleisten. Der zweite Enumerator legt die Byte-Reihenfolge des Datenstroms fest. Die Klasse Stream bildet die Basis für alle I/O-Unterklassen.

Der nächste Schritt besteht darin den Eingabe- und Ausgabe-Streams aufzuspalten. Dazu werden die beiden abstrakten Klassen InputStream und OutputStream entwickelt. Beide Klassen besitzen mehrfache Überladungen für unterschiedliche Datentypen und implementieren die Basisklasse Stream. Die Überladungen sind durch die Methoden read() für Eingabe-Streams und write() für Ausgabe-Streams implementiert. Weiterhin wurde für die Datentypen der operator>> bzw. operator<< überladen. Beide Klassen überladen ebenfalls die C++ String-Klassen.

/**
  * @brief Base interface class for all input streams.
  *
  * Applications that need to define a subclass of InputStream 
  * must always provide a method that returns the next byte of input.
  *
  * @author CodePlanet
  * @date 30.12.2013 
  * 
  * @version 0.1 
  * Comments added (Doxygen).
  */
class InputStream : public Stream
{
public:
    ////////////////////////////////////////////////////////////
    /// Functions to read data from the stream
    ///
    ////////////////////////////////////////////////////////////
    virtual void read(bool&               data, uint32_t bit = Bits<bool>::size       ) = 0;
    virtual void read(char&               data, uint32_t bit = Bits<char>::size       ) = 0;
    virtual void read(int8_t&             data, uint32_t bit = Bits<int8_t>::size     ) = 0;
    virtual void read(uint8_t&            data, uint32_t bit = Bits<uint8_t>::size    ) = 0;
    virtual void read(int16_t&            data, uint32_t bit = Bits<int16_t>::size    ) = 0;
    virtual void read(uint16_t&           data, uint32_t bit = Bits<uint16_t>::size   ) = 0;
    virtual void read(int32_t&            data, uint32_t bit = Bits<int32_t>::size    ) = 0;
    virtual void read(uint32_t&           data, uint32_t bit = Bits<uint32_t>::size   ) = 0;      
    virtual void read(int64_t&            data, uint32_t bit = Bits<int64_t>::size    ) = 0;
    virtual void read(uint64_t&           data, uint32_t bit = Bits<uint64_t>::size   ) = 0;       
    virtual void read(float&              data, uint32_t bit = Bits<int32_t>::size    ) = 0;
    virtual void read(double&             data, uint32_t bit = Bits<int64_t>::size    ) = 0;
    //virtual void read(const char*         data, uint32_t bit = Bits<int8_t>::size     ) = 0;
    //virtual void read(const wchar_t*      data, uint32_t bit = Bits<int16_t>::size    ) = 0;
    virtual void read(std::string&        data, uint32_t maxLength                    ) = 0;
    virtual void read(std::wstring&       data, uint32_t maxLength                    ) = 0;
    virtual void read(void*               data, uint32_t length                       ) = 0;
 
    virtual int32_t read(char* b, uint32_t off, uint32_t len) = 0;
 
    ////////////////////////////////////////////////////////////
    /// Operator >> overloads to read data from the stream
    ///
    ////////////////////////////////////////////////////////////
    virtual InputStream& operator>>(bool&               data) = 0;
    virtual InputStream& operator>>(char&               data) = 0;
    virtual InputStream& operator>>(int8_t&             data) = 0;
    virtual InputStream& operator>>(uint8_t&            data) = 0;
    virtual InputStream& operator>>(int16_t&            data) = 0;
    virtual InputStream& operator>>(uint16_t&           data) = 0;
    virtual InputStream& operator>>(int32_t&            data) = 0;
    virtual InputStream& operator>>(uint32_t&           data) = 0;
    virtual InputStream& operator>>(int64_t&            data) = 0;
    virtual InputStream& operator>>(uint64_t&           data) = 0;
    virtual InputStream& operator>>(float&              data) = 0;
    virtual InputStream& operator>>(double&             data) = 0;
    //virtual InputStream& operator>>(const char*         data) = 0;
    //virtual InputStream& operator>>(const wchar_t*      data) = 0;
    virtual InputStream& operator>>(std::string&        data) = 0;
    virtual InputStream& operator>>(std::wstring&       data) = 0;
 
    struct true_type  { enum { value = true  }; };
    struct false_type { enum { value = false }; };
 
    template <typename T>
    void do_read(T& data, uint32_t bit, const false_type&) 
    {
        read(data, bit);
    }
 
    template <typename T>
    void do_read(T& data, uint32_t bit, const true_type&) 
    {
        int32_t temp;
        read(temp, bit);
        data = static_cast<T>(temp);
    }
};

ByteArrayInputStream und ByteArrayOutputStream

Die konkreten Implementierungen werden durch die beiden Klassen ByteArrayInputStream und ByteArrayOutputStream dargestellt. Beide Klassen realisieren ihre Basisklassen und operieren auf Datenströmen der Größe ein Byte oder 8-Bit. Instanziiert werden beide Klassen mit einem Objekt vom Typ IODevice oder direkt mit einem ByteArray.

In dem nachfolgenden Listing ist ein Beispiel für die Nutzung einer der beiden Klassen zu sehen:

ByteArray arr;
ByteArrayOutputStream bos(&arr); 
bos.setByteOrder(ByteArrayOutputStream::LittleEndian); 
int a = 0x52535455; 
bos << a; 
std::string str = "hello"; 
bos << str;

Die Klasse ByteArray repräsentiert im Wesentlichen einen STL-Container mit dem Datentyp char. In der zweiten Zeile kapselt die Klasse ByteArrayOutputStream eine Instanz von ByteArray. Nachdem die Byte-Reihenfolge gesetzt wurde, können beliebige Datentypen in den Ausgabestrom serialisiert werden.

Das ByteArray ermöglicht einen wahlfreien Zugriff (engl. random access) indem die Klasse ByteArrayOutputStream das Array intern in einem so genannten Buffer schachtelt. Ein Buffer implementiert die virtuellen Methoden von einem IODevice. Prinzipiell können von der Klasse ByteArrayOutputStream alle Quellen beschrieben werden, die ein IODevice realisieren. So ist es möglich auch zu einem Socket oder einer Datei zu schreiben.

Die Serialisierung der String-Klassen aus der STL geschieht dadurch, dass in den Datenstrom zu Beginn die Anzahl der nachfolgenden Zeichen geschrieben werden. Bei der Deserialisierung kann auf diese Weise der komplette Zeichenstrom rekonstruiert werden, indem zuerst die Anzahl der Zeichen gelesen werden und anschließend die Zeichen selbst. Zu beachten ist das beide Seiten dieselbe Byte-Reihenfolge verwenden müssen, d.h. es muss im selben Format geschrieben und gelesen werden. Weiterhin muss das in exakt derselben Abfolge geschehen. Wurde zuerst ein Integer geschrieben, so muss auf der Gegenseite auch zuerst ein Integer gelesen werden. Diese logische Tatsache ergibt sich aus dem Aufbau des sequenziellen Datenstroms. Sowohl der Client, als auch der Server nutzen für die Serialisierung direkt das Protokoll, so dass keine weiteren Maßnahmen notwendig sind. Das Protokoll kapselt die Serialisierung der Datentypen in Objekten, die direkt gesendet und empfangen werden können.

Datenkompression

Nachfolgend soll die Datenkompression erläutert werden. Den Vorgang der Datenkompression übernimmt ein Kodierer oder Kompressor. Die Umkehrung bezeichnet man als Dekompression oder Dekomprimierung, welche durch den Dekodierer bzw. Dekompressor vorgenommen wird.

coder-cncoder

Zur Komprimierung von Bildern stehen unterschiedliche Techniken zur Verfügung. In der Regel nutzen Bildformate standardisierte Kompressionsalgorithmen, deren Reduktion sich an den physiologischen Wahrnehmungseigenschaften des Menschen orientieren. Neben JPEG existieren unter anderen die Formate PNG, GIF oder BMP. JPEG schlägt diverse Komprimierungs- und Kodierungsmethoden vor, darunter verlustbehaftete und verlustfreie Komprimierung. Im Gegensatz zur verlustbehafteten Kompression, geht bei der verlustfreien Kompression keine Information verloren. Die Daten werden lediglich reorganisiert, indem bestimmte Redundanzen erkannt und zusammengefasst werden. Verlustbehaftet wird die Kompression oder Kodierung genannt, wenn sich die Daten im Allgemeinen nicht fehlerfrei rekonstruieren lassen. In der Tabelle wird die gebräuchliche JPEG-Norm dargestellt.

jpeg-norm

Verlustbehaftete JPEG-Verfahren können mithilfe moderater Tiefpassfilterung zur Farbreduktion zum Beispiel durch einen Algorithmus zur DCT-Transformation das Datenvolumen um mehr als 90% reduzieren. Der Preis für die starke Datenkomprimierung ist allerdings ein realer Verlust von Daten. Zudem kommt es durch die Eigenart der auf einer Fouriertransformation basierenden Datenkompression zu einer Bildung von Arte-fakten im Bild, auch als Gibbssches Phänomen bezeichnet. Dieses Phänomen basiert darauf, dass die Funktion der Partialsumme xN (t) bei einem Rechtecksignal in der Nähe der Unstetigkeitsstelle eine Welligkeit aufweist, deren Amplitude mit größer werdenden N nicht abnimmt. Bei einer Unstetigkeit mit der Höhe Eins hat die Partialsumme einen Wert von 1.09 (d.h., ein überschwingen um 9% der Unstetigkeitsstelle) unabhängig davon, wie groß N ist.

Gibbsches Phänomen

Betrachtet man die Partialsummen der Funktionen mit Sprungstellen, zeigt sich, dass diese Summen an den Sprungstellen gegen das arithmetische Mittel der Funktionswerte rechts und links der Unstetigkeitsstellen von x0 konvergieren.

formula-1

Jede Partialsumme mit genügend großem, aber endlichen n zeigt bei Rechtecksignalen in der Umgebung ihrer Sprungstellen ein Über- und Unterschwingen um jeweils 9 % der Sprunghöhe. Die Bildung von Artefakten wird auch als „Ringing“ bezeichnet und verschwindet erst bei der unendlichen Fourierreihe. Entwickelt man eine Fourierreihe aus einer unstetigen Funktion, so ergeben sich an den Unstetigkeitsstellen typische Über- und Unterschwinger, die sich auch dann nicht verringern, wenn man versucht, die Funktion noch besser zu approximieren. Dies liegt daran, dass die Reihe an der Unstetigkeitsstelle nicht mehr gleichmäßig, sondern nur punktweise konvergiert.

Die Höhe des Überschwingers in einer Richtung lässt sich bestimmen:

formula-2

Daraus ergibt sich ein prozentueller Fehler von insgesamt 17,898 %, gerundet 18 %, der Sprunghöhe.

Für Bilder bedeutet dieser Umstand, dass es an scharfen Farbübergängen, die gleichbedeutend mit Unstetigkeitsstellen sind, zu einer sichtbaren Unschärfe bei der Datenkompression kommt. Dies wird bei entsprechender starker Kompression und Vergrößerung des Bildausschnitts besonders ersichtlich und sind als Alias-Effekte bekannt.

aliasing-artifact

Als Alias-Effekte (auch Aliasing-Effekte oder kurz Aliasing) werden im Bereich der Signalanalyse Fehler bezeichnet, die auftreten, wenn im abzutastenden Signal Frequenzanteile vorkommen, die höher als die Nyquist-Frequenz (halbe Abtastfrequenz) sind.

Um ein Bild korrekt und eindeutig wieder rekonstruieren zu können, muss deshalb eine verlustfreie Kompression verwendet werden. Die verlustfreie Kompression kann allerdings bei hohem Rauschanteil in einem Bild nur eine ungenügende Kompression erzielen. Aus diesem Grund finden verlustlose digitale Kompressionsformate wie etwa das BMP-Format fast nur in der professionellen Fotografie und Bild-Gestaltung ihre Anwendung.


Huffman-Codierung

Für die Datenkompression von Bildern soll für das Protokoll eine verlustfreie Datenkompression implementiert werden. Um keine weiteren Abhängigkeiten von Bibliotheken zu generieren, werden die Klassen für die Komprimierung autonom von anderen Komponenten erstellt. Ein sehr bekannter und oft in Bildformaten verwendeter Algorithmus zur Datenkompression ist die Huffman-Codierung, eine Form der Entropiekodierung benannt nach David A. Huffman. Abhängig von den Eigenschaften der zu komprimierenden Daten können damit Kompressionsraten von 20% bis 90% erzielt werden.

Die Huffman-Codierung basiert auf einem Greedy-Algorithmus. Dieser betrachtet die Daten als Zeichenketten und verwendet eine Tabelle mit einer Häufigkeitsverteilung der vorkommenden Zeichen, um eine optimale Möglichkeit für die Darstellung jedes Zei-chens als binäre Zeichenkette zu entwickeln.

Präfix-Code

Um eine Bilddatei zu komprimieren, können verschiedene Darstellungsformen verwendet werden. In der Regel werden binäre Zeichencodes (oder kurz Codes) verwendet, in dem jedes Zeichen durch eine eindeutige binäre Zeichenkette dargestellt wird. Bei einem Code fester Länge, werden insgesamt 3 Bits benötigt, um sechs Zeichen darstellen zu können: a = 000, b = 001, c = 010, ..., f = 101. Diese Methode benötigt insgesamt 300000 Bits, um ein Bild mit 100000 Zeichen zu codieren, deren Symbole in der nachfolgenden Tabelle dargestellt sind. Die Huffman-Codierung nutzt dabei einen Code variabler Länge. Dadurch können häufig auftretenden Zeichen kurze Codewörter zugewiesen werden und selten auftretenden Zeichen lange Codewörter. Es ist aber nicht möglich, einzelnen Zeichen einfach Bitfolgen zuzuweisen und diese auszugeben. Wird zum Beispiel das Zeichen a mit der Bitfolge „10“, das Zeichen b mit der Folge „01“ und c mit „0“ ko-diert, dann wird die Zeichenkette abc zu „10010“. Diese Folge wird allerdings auch von der Zeichenkette „aca“ erzeugt. Es ist dadurch nicht mehr eindeutig erkennbar, für welche Zeichenfolge die Bitfolge „10010“ steht. Aus diesem Grunde muss die angestrebte Codierung ein sogenannter Präfix-Code sein. Präfix-Codes sind erstrebenswert, weil sie die Decodierung deutlich vereinfachen. Da kein Codewort Präfix eines anderen ist, ist das Codewort, mit dem ein codiertes Bild beginnt, eindeutig. Dadurch lässt sich das Anfangscodewort einfach identifizieren und in das ursprüngliche Zeichen zurückübersetzen. Anschließend kann der Rest dekodiert werden.

symbol-frequency

Für den Dekodierungsprozess wird eine geeignete Darstellung des Präfix-Codes gesucht, so dass das Anfangscodewort einfach dargestellt werden kann. Dazu bietet sich ein Graph an, genauer gesagt ein binärer Baum. In dem binären Baum stehen die Blätter für die zu kodierenden Zeichen, während der Pfad von der Wurzel zum Blatt die Bitfolge, d.h. den Code, festlegt.

Huffman-Baum

Die Huffman-Codierung baut einen binären Baum, den Huffman-Baum, auf. Mit Hilfe dieses Baumes werden die Codewörter für die einzelnen Symbole erzeugt. Außerdem fungiert der Baum als visuelle Repräsentation der Symbole, ihrer Wahrscheinlichkeiten und ihrer Codes. Die Blätter des Baumes stellen stets die zu codierenden Symbole bzw. Zeichen dar. Um an ein Codewort zu gelangen, muss der Pfad von der Wurzel zu dem Symbol nachvollzogen werden. Der linke Pfad wird stets durch eine binäre „0“ darge-stellt, der rechte Pfad durch eine binäre „1“. Der Huffman-Baum ist kein binärer Suchbaum, da die Blätter nicht notwendigerweise in sortierten Reihenfolge auftreten, und die inneren Knoten keine Zeichenschlüssel enthalten.

Eine optimale Codierung wird stets durch einen vollständigen binären Baum dargestellt, bei dem jeder innere Knoten zwei Kinder hat. Aus der vorherigen Tabelle ergibt sich für eine Codierung fester Länge der in Abbildung 1 dargestellte Baum. Bei Codierung variabler Länger ergibt sich der Baum in Abbildung 2.

binary-tree-fixed-length
binary-tree-variable-length

Um die Anzahl der zur Codierung benötigten Bits zu berechnen, kann zu einem gege-benen Baum T eine Formel verwendet werden. Für jedes Zeichen c aus dem Alphabet C bezeichnet man die Häufigkeit von s in der Datei mit f(c) und die Tiefe des Blattes s im Baum mit dT (c). Die Funktion dT (c) gibt auch die Länge des Codewortes an. Die An-zahl der für die Codierung der Datei benötigten Bits ergibt sich somit zu

formula-3

was auch als Kosten des Baumes T definiert wird.

Für die Konstruktion eines optimalen Huffman-Baumes kann der Greedy-Algorithmus verwendet werden. Aus einer Menge C mit n Zeichen ist jedes Zeichen c ∈ C und tritt mit einer definierten Häufigkeit von f[c] auf. Der Algorithmus erzeugt einen der optimalen Codierung entsprechenden binären Baum T nach dem „bottom-up“ Verfahren. Beginnend mit einer Menge von |C| Blättern werden |C| - 1 „Verschmelzungsoperationen“ durchgeführt, um einen fertigen binären Huffman-Baum zu erstellen. Der Algorithmus baut auf einer Min-Prioritätswarteschlange Q auf, der die Schlüssel f verwaltet, um die Elemente zu identifizieren, die am seltensten vorkommen. Nach der Verschmelzung entsteht ein innerer Knoten, dessen Häufigkeit durch die Summe der beiden verschmolzenen Objekte gegeben ist.

Für die Tabelle soll der Huffman-Baum schrittweise erstellt werden. Dazu werden zunächst die beiden Zeichen oder Symbole entnommen, die am seltensten auftreten. Es handelt sich um das Zeichen f und e. Daraus resultiert der erste Teilbaum, der in Abbildung zu sehen ist.

huffman-tree-1

Im zweiten Schritt werden erneut die beiden Elemente in der Min-Prioritätswarteschlange Q gesucht, die am seltensten auftreten. Dabei muss beachtet werden, dass zu den gesuchten Elementen auch die neu erstellten Teilbäume gehören. Im ersten Teilbaum ist das ein Element mit der Häufigkeit 14. Da aber mit dem Zeichen b und c zwei Zeichen mit einer kleineren Häufigkeit, nämlich 12 und 13 vorzufinden sind, wird zunächst ein zweiter Teilbaum erstellt, was zu dem Resultat in der nachfolgenden Abbildung führt.

huffman-tree-2

Im dritten Schritt wird das Zeichen d mit dem zweiten Teilbaum verschmolzen.

huffman-tree-3

Der vierte Schritt verschmilzt die beiden Teilbäume zu einem neuen Baum.

huffman-tree-4

Der letzte Schritt führt abschließend zum Endergebnis und zum fertigen Huffman-Baum, wie er in der Abbildung am Anfang vom Kapitel präsentiert wurde. Insgesamt wurden sechs Zeichen in der Warteschlange bearbeitet. Das führte zu insgesamt fünf Verschmelzungsoperationen, die den endgültigen Baum mit den optimalen Präfix-Codes darstellt. Das Codewort für einen Buchstaben ist die Sequenz der Kantenmarkierungen auf dem Pfad von der Wurzel zum jeweiligen Zeichen. Abschließend wird der Pseudocode zur Generierung eines Huffman-Baums erläutert.

n ← |C|
Q ← C
for i ← 1 to n - 1
   do Allocate new node z
       left[z] ← x ← EXTRACT-MIN(Q)
       right[z] ← y ← EXTRACT-MIN(Q)
       f[z] ← f[z] + f[y]
       INSERT(Q, z)
return EXTRACT-MIN(Q)

In der Schleife wird zunächst ein Knoten erstellt. Die beiden seltensten Zeichen werden aus der Warteschlange extrahiert und zum linken und rechten Kind. Die beiden Häufig-keiten werden anschließend addiert und der Teilbaum zurück in die Warteschlange ge-schoben. Nach n - 1 Verschmelzungen bildet der eine, noch in der Warteschlange ver-bliebene Knoten die Wurzel des Codebaumes, die in Zeile 9 zurückgegeben wird.

D-Heap

Für die Realisierung des vorgestellten Huffman-Algorithmus wird eine Min-Prioritätswarteschlange benötigt. In C++ stellt die STL mit der Klasse std::priority_queue eine entsprechende Warteschlange zur Verfügung. Die STL-Variante basiert allerdings auf einer Max-Prioritätswarteschlange, so dass für den Template-Parameter Compare eine eigene Funktion implementiert werden muss. Dieser Schritt geht allerdings zu Lasten der Laufzeit, so dass es sich an dieser Stelle anbietet einen binären Min-Heap eigenständig zu implementieren.

Ein d-närer Heap ist eine Datenstruktur, die als vollständiger binärer Baum angesehen werden kann. Der Baum ist auf allen Ebenen vollständig gefüllt, außer möglicherweise auf der niedrigsten, die von links her bis zu einem bestimmten Punkt aufgefüllt ist. Der d-näre Heap kann auf effiziente Art und Weise als ein Array A, siehe Abbildung, dargestellt werden. Die Wurzel des Baums wird an der ersten Position im Array gespeichert. Bei einer Array-Indizierung beginnend mit 1 werden die beiden Nachfolger eines Knotens an der i-ten Position an der 2i-ten und 2i+1-ten Position gespeichert, entsprechend der Kekule-Nummerierung. Analog dazu sind die Nachfolger von dem Knoten mit Index i an der 2i+1-ten und 2i+2-ten Position gespeichert, wenn die Array-Indizierung mit 0 beginnt. Mit einem Array beansprucht jede Heap-Operation eine Worst-Case-Laufzeit von O(log n). Für die Gesamtlaufzeit des Huffman-Algorithmus auf einer Menge von n Zeichen ergibt das die Komplexität O(n log n).

binary-heap-array

Der d-näre Heap hat insgesamt d Kinder und wird als Template-Klasse mit dem Namen PriorityQueue implementiert. In dem nachfolgenden Abschnitt ist die PriorityQueue als Klasse vollständig abgebildet. Die Klasse arbeitet mit Zeigern, so dass effiziente und speicherschonende Operationen möglich sind. Für Vergleiche werden die Zeiger intern dereferenziert. Sobald ein Element aus der Warteschlange entnommen wird oder ein neues Element hinzukommt, muss der Heap neu sortiert werden. Dazu stehen zwei interne Methoden zur Verfügung, die rekursiv aufgerufen werden.

template<class T>
class PriorityQueue
{
public:
    PriorityQueue(int32_t d = 2);
    ~PriorityQueue();
    void push(T* x);
    void pop();
    T* top() const;
    bool empty() const;
    uint32_t size() const;
 
private:
    int32_t m_d;                           
    std::vector<T*> m_heap;                 
    void sortHeapUp(int32_t, int32_t); 
    void sortHeapDown(int32_t, int32_t);       
    typename std::vector<T*>::size_type m_lastIter;
    static const unsigned int STEPSIZE = 256;    
};
 
template<class T>
PriorityQueue<T>::PriorityQueue(int32_t d)
    : m_d(d), m_lastIter(0), m_heap(STEPSIZE)
{
    // Mininum 2 children
    if(m_d < 2) {
        m_d = 2;
    }
}
 
template<class T>
PriorityQueue<T>::~PriorityQueue()
{
}
 
template<class T>
bool PriorityQueue<T>::empty() const
{
    return (m_lastIter <= 0);
}
 
template<class T>
void PriorityQueue<T>::pop()
{
    m_heap[0] = m_heap[--m_lastIter];
    sortHeapDown(0, m_lastIter - 1);
}
 
template<class T>
T* PriorityQueue<T>::top() const
{
    return m_heap[0];
}
 
template<class T>
void PriorityQueue<T>::push(T* x)
{
    if(m_lastIter >= m_heap.size()) {
        m_heap.resize(m_lastIter + STEPSIZE);
    }
 
    m_heap[m_lastIter++] = x;   // Add x to queue
    sortHeapUp(0, m_lastIter - 1);
}
 
template<class T>
void PriorityQueue<T>::sortHeapUp(int32_t root, int32_t bottom)
{
    int32_t parent = 0;
 
    if(bottom > root) {
        parent = (bottom - 1) / m_d;
 
        if(*m_heap[parent] > *m_heap[bottom]) {
            std::swap(m_heap[parent], m_heap[bottom]);
            sortHeapUp(root, parent);
        }
    }
}
 
template<class T>
void PriorityQueue<T>::sortHeapDown(int32_t root, int32_t bottom)
{
    int32_t minchild = 0, firstchild = 0, child = 0;
 
    firstchild = root * m_d + 1;
 
    if(firstchild <= bottom) {
        minchild = firstchild;
 
        // Loop through all childs and find the minchild
        for(int i = 2; i <= m_d; ++i) {
            child = root * m_d + i;
            if(child <= bottom) {
                if(*m_heap[child] < *m_heap[minchild]) {
                    minchild = child;
                }
            }
        }
 
        if(*m_heap[root] > *m_heap[minchild]) {
            std::swap(m_heap[root], m_heap[minchild]);
            sortHeapDown(minchild, bottom);
        }
    } 
}
 
template<class T>
uint32_t PriorityQueue<T>::size() const
{
    return m_lastIter;
}

Die Klassen „Deflater“ und „Inflater“

Der Huffman-Algorithmus wird in der Klasse Huffman realisiert. Die Klasse Huffman nutzt zur Bildung eines Huffman-Baumes, eine eigene Template-Klasse mit dem Namen HuffmanTree. Diese Klasse wird mit dem Datentypen der vorkommen-den Zeichen instanziiert. Die IO-Klassen ByteArrayOutputStream und Byte-ArrayInputStream werden genutzt um direkt die Streams zu beschreiben oder zu lesen. Huffman stellt die zwei statischen Methoden encode() und decode() zur Verfügung. Diese Methoden komprimieren und dekomprimieren ein übergebenes ByteArray.

Der in Listing 5.2 vorgestellte Pseudocode wird mit einer auf einem d-nären Heap basierenden PriorityQueue in C++ realisiert. In dem Listing wird zunächst die Warteschlange mit einem Huffman-Baum parametrisiert. Anschließend wird die Frequenztabelle geschrieben, die die Häufigkeiten der auftretenden Symbole enthält. Für jedes Symbol wird dann ein Teilbaum neu allokiert und über eine Zeiger an den D-Heap übergeben. Nun wird entsprechend des Huffman-Algorithmus der vollständige Baum generiert. Die Schleife beendet, sobald die Warteschlange leer ist.

PriorityQueue<HuffmanTree<unsigned char>> q(3);
HuffmanTree<unsigned char>* tree;
 
for(int i = 0; i < 256; ++i) {
    // Write frequency table to stream
    ostream << freqTable[i];
 
    // Create single sub-trees, send freq-symbol pairs to 
    // the priority heap
    if(freqTable[i] > 0) {
        tree = new HuffmanTree<unsigned char>();
        tree->setFrequency(freqTable[i]);
        tree->setSymbol(static_cast<unsigned char>(i));
        q.push(tree);
    }
}
 
// Create the main Huffman tree from the sub-trees
HuffmanTree<unsigned char> *tree2, *tree3;
 
// Loop until all sub-trees are combined into one single tree
do {
    tree = q.top();
    q.pop();
 
    if( !q.empty()) {
        // Extract the two lowest frequency Huffman trees, combine
        // them into one tree and put the tree back into the priority queue
        tree2 = q.top();
        q.pop();
        tree3 = new HuffmanTree<unsigned char>();
        tree3->setFrequency(tree->frequency() + tree2->frequency());
        tree3->setLeftChild(tree->root());
        tree3->setRightChild(tree2->root());
        q.push(tree3);
    }
} while( !q.empty());

Der Huffman-Algorithmus liefert nicht zwangsläufig bereits nach der ersten Anwendung die optimale Kompression. In der Regel muss encode() deshalb mehrmals aufgerufen werden. Da in C++ nur byteweise geschrieben und gelesen werden kann, verfügt die Klasse Huffman über zwei interne Hilfsfunktionen, die es ermöglichen bitweise zu lesen und zu schreiben.

Die endgültige Kompression wird von den Klassen Inflater und Deflater vorgenommen. Beide Klassen abstrahieren den Kompressionsalgorithmus, so dass dieser bei Bedarf auch durch neue Algorithmen ersetzt werden kann. Die Datenkompression ist im Namensraum CodePlanet.Articles.Zip eingebettet und kann in der Anwendung über die Methoden inflate() und deflate() der jeweiligen Klassen genutzt werden.

Der nachfolgende Codeausschnitt zeigt die Verwendung der Klasse Deflator mit der Daten komprimiert werden können. Der Konstruktor kann verschiedene Strategien übernehmen, unter anderem für eine schnelle oder bestmögliche Kompression.

ByteArray input, output;
 
// Fill input array with data...
 
Deflater def(Deflater::BEST_COMPRESSION);
def.setInput(input);
def.finish();
unsigned int compressedDataLength = def.deflate(compressedOutput);

Die Klasse Deflater schreibt neben den komprimierten Daten einen kleinen Kopfbereich (engl. Header) in das ByteArray. Der Kopfbereich dient dem Dekodierer bzw. dem Inflater dazu, die Anzahl der Komprimierungsrunden und eventuell gesetzte Modi zu erkennen.

Schluss

In diesem Artikel wurde mit dem Huffman-Verfahren eine sehr wirkungsvolle Art der Datenkompression vorgestellt. Der Code stellt keinen Anspruch an eine größtmögliche Effizienz und steht auch nicht in Konkurrenz zu modernen Datenkompressionsprogrammen, wie WinRAR oder 7-Zip. Vielmehr kann er als theoretisches Beispiel oder als Grundlage für die Entwicklung eigener Programme zur Datenkompression betrachtet werden. Die fertige Anwendung kann im Forum heruntergeladen werden.

Zuletzt aktualisiert am Freitag, den 03. Januar 2014 um 01:18 Uhr
 
AUSWAHLMENÜ