Huffman-Kodierung

aus Wikipedia, der freien Enzyklopädie
Wechseln zu: Navigation, Suche

Die Huffman-Kodierung ist eine Form der Entropiekodierung, die 1952 von David A. Huffman entwickelt wurde.[1] Sie ordnet einer festen Anzahl an Quellsymbolen jeweils Codewörter mit variabler Länge zu.

Grundlagen[Bearbeiten]

Um Daten möglichst redundanzfrei darzustellen, müssen die Quellsymbole mit Codewörtern unterschiedlicher Wortlängen kodiert werden. Die Länge der Codewörter entspricht dabei idealerweise ihrem Informationsgehalt. Um einen Code auch wieder eindeutig dekodieren zu können, muss er die Kraftsche Ungleichung erfüllen und zusätzlich noch präfixfrei sein, d. h. kein Codewort darf der Beginn eines anderen sein.

Die Grundidee ist, einen k-nären Wurzelbaum (ein Baum mit jeweils k Kindern je Knoten) für die Darstellung des Codes zu verwenden. In diesem sog. Huffman-Baum stehen die Blätter für die zu kodierenden Zeichen, während der Pfad von der Wurzel zum Blatt das Codesymbol bestimmt. Im Gegensatz zur Shannon-Fano-Kodierung wird der Baum dabei von den Blättern zur Wurzel (englisch bottom-up) erstellt.

Der bei der Huffman-Kodierung gewonnene Baum liefert garantiert eine optimale und präfixfreie Kodierung. D. h. es existiert kein symbolbezogenes Kodierverfahren, das einen kürzeren Code generieren könnte, wenn die Auftrittswahrscheinlichkeiten der Symbole bekannt sind.

Algorithmus[Bearbeiten]

Definitionen

  • X ist das Quellsymbolalphabet – der Zeichenvorrat, aus dem die Quellsymbole bestehen
  • px ist die A-priori-Wahrscheinlichkeit des Symbols x (die relative Häufigkeit)
  • C ist das Codealphabet – der Zeichenvorat, aus dem die Codewörter bestehen
  • m ist die Mächtigkeit \vert C \vert des Codealphabetes C – die Anzahl der verschiedenen Zeichen

Aufbau des Baumes

  1. Ermittle für jedes Quellsymbol die relative Häufigkeit, d. h. zähle wie oft jedes Zeichen vorkommt und teile durch die Anzahl aller Zeichen.
  2. Erstelle für jedes Quellsymbol einen einzelnen Knoten (die einfachste Form eines Baumes) und notiere im/am Knoten die Häufigkeit.
  3. Wiederhole die folgenden Schritte so lange, bis nur noch ein Baum übrig ist:
    1. Wähle die m Teilbäume, mit der geringsten Häufigkeit in der Wurzel.
    2. Fasse diese Bäume zu einem neuen (Teil-)Baum zusammen.
    3. Notiere die Summe der Häufigkeiten in der Wurzel.

Konstruktion des Codebuchs

  1. Ordne jedem Kind eines Knotens eindeutig ein Zeichen aus dem Codealphabet zu.
  2. Lies für jedes Quellsymbol (Blatt im Baum) das Codewort aus:
    1. Beginne an der Wurzel des Baums.
    2. Die Codezeichen auf den Kanten des Pfades (in dieser Reihenfolge) ergeben das zugehörige Codewort.

Kodierung

  1. Lies ein Quellsymbol ein.
  2. Ermittle das zugehörige Codewort aus dem Codebuch.
  3. Gib das Codewort aus.

Mittlere Wortlänge[Bearbeiten]

Die mittlere Länge eines Codeworts kann auf drei Arten berechnet werden.

  • Über die gewichtete Summe der Codewortlängen:
\overline l = \sum_{x \in X} p_x l_x
  • Indem man die Auftrittswahrscheinlichkeiten an allen Zwischenknoten des Huffman-Baums summiert.
  • Bei ausschließlich gleicher Häufigkeit der zu codierenden Elemente ist die mittlere Länge
 l = \log_2 \ m mit m \in N als Anzahl der zu codierenden Elemente.

Beispiel[Bearbeiten]

Huffman-Baum zu dem Beispiel. (Die Wurzel des Baumes befindet sich rechts, die Blätter links.)

Das Quellalphabet enthält die Zeichen: X = \{ a, b, c, d \} Als Codealphabet wählen wir den Binärcode: C = \{ 0, 1 \} und m = \vert C \vert = 2. Der Text a ab abc abcd soll (ohne die Leerzeichen) komprimiert werden.

Bestimme die relativen Häufigkeiten:

pa = 0,4 ; pb = 0,3 ; pc = 0,2 ; pd = 0,1

Konstruiere Huffman-Baum und trage anschließend die Codewörter an den Kanten ein. (Siehe Bild rechts)

Codewörterbuch:

a 1
b 01
c 001
d 000

Kodiere den ursprünglichen Text:

a a b a b c a b c d
1 1 01 1 01 001 1 01 001 000

Mittlere Codewortlänge:

  • Bei einer naiven Kodierung würde jedes Zeichen mit \log_2 4 = 2 \, \text{Bit je Symbol} kodiert.
  • Diese Huffman-Kodierung kodiert jedes Zeichen mit
\overline l = 1{,}0 + 0{,}6 + 0{,}3 = 1{,}9 \, \text{Bit je Symbol}
  • Die Entropie liegt bei
\begin{align}
        H(X) & = -( 0{,}4 \cdot \log_2 0{,}4 + 0{,}3 \cdot \log_2 0{,}3 + 0{,}2 \cdot \log_2 0{,}2 + 0{,}1 \cdot \log_2 0{,}1 ) \\
             & = 0{,}529 + 0{,}521 + 0{,}464 + 0{,}332 \\
             & = 1{,}85 \, \text{Bit je Symbol}
     \end{align}

Dadurch, dass der Informationsgehalt je Quellsymbol keine Ganzzahl ist, verbleibt bei der Kodierung eine Rest-Redundanz.

Dekodierung[Bearbeiten]

Zur Dekodierung eines Huffman-kodierten Datenstroms ist (beim klassischen Verfahren) die im Kodierer erstellte Codetabelle notwendig. Grundsätzlich wird dabei umgekehrt wie im Kodierungsschritt vorgegangen. Der Huffman-Baum wird im Dekodierer wieder aufgebaut und mit jedem eingehenden Bit – ausgehend von der Wurzel – der entsprechende Pfad im Baum abgelaufen, bis man an einem Blatt ankommt. Dieses Blatt ist dann das gesuchte Quellsymbol und man beginnt mit der Dekodierung des nächsten Symbols wieder an der Wurzel.

Beispiel[Bearbeiten]

Der Dekodierer hat das Codewörterbuch:

a 1
b 01
c 001
d 000

und eine empfangene Nachricht: 1101101001101001000.

Jetzt wird für jedes empfangene Bit ausgehend von der Wurzel der Pfad im Baum (siehe oben) abgelaufen, bis ein Blatt erreicht wurde. Sobald ein Blatt erreicht wurde, zeichnet der Dekodierer das Symbol des Blattes auf und beginnt wieder bei der Wurzel, bis das nächste Blatt erreicht wird.

Teil-Pfad: 1 1 01 1 01 001 1 01 001 000
Entsprechendes Blatt: a a b a b c a b c d

Optimalität[Bearbeiten]

Für mittlere Codewortlänge \overline l eines Huffman-Codes gilt:

\Eta(X) \leq \overline l \leq \Eta(X) + 1

Das bedeutet, im Mittel benötigt jedes Codesymbol mindestens so viele Stellen, wie sein Informationsgehalt. Höchstens jedoch eine mehr.

Die Huffman-Kodierung ist optimal bzgl. der Entropie g. d. w. alle Auftrittswahrscheinlichkeiten 2^{-m_x}, \; m_x \in \mathbb{N}^+ sind.

Fasst man n Quellsymbole zu einem Hypersymbol y zusammen, so gilt für die mittleren Codesymbollängen ly:

\Eta_n(X) \leq l_y \leq \Eta_n(X) + \frac{1}{n}

D. h. mit zunehmender Anzahl an gemeinsam kodierten Quellsymbolen geht die mittlere Codewortlänge asymptotisch gegen die Entropie – die Kodierung ist asymptotisch optimal.

Adaptive Huffman-Kodierung[Bearbeiten]

Die adaptive Huffman-Kodierung aktualisiert laufend den Baum. Der anfängliche Baum wird erzeugt, indem eine vorgegebene Wahrscheinlichkeitsverteilung für alle Quellsymbole angenommen wird (bei völliger Unkenntnis der Quelle eine Gleichverteilung). Mit jedem neuen Quellsymbol wird dieser aktualisiert, wodurch sich ggf. auch die Codesymbole ändern. Dieser Aktualisierungsschritt kann im Dekodierer nachvollzogen werden, so dass eine Übertragung des Codebuchs nicht nötig ist.

Mit dieser Methode kann ein Datenstrom on-the-fly kodiert werden. Er ist jedoch erheblich anfälliger für Übertragungsfehler, da ein einziger Fehler zu einer – ab der Fehlerstelle – komplett falschen Dekodierung führt.

Siehe auch[Bearbeiten]

Literatur[Bearbeiten]

  • Thomas M. Cover, Joy A. Thomas: Elements of Information Theory

Weblinks[Bearbeiten]

Einzelnachweise[Bearbeiten]

  1. D. A. Huffman: A method for the construction of minimum-redundancy codes. (PDF) In: Proceedings of the I.R.E.. September 1952, S. 1098-1101.