Quelltext der Seite Huffman-Kodierung

Die '''Huffman-Kodierung''' ist eine Form der [[Entropiekodierung]], die 1952 von [[David A. Huffman]] entwickelt und in der Abhandlung ''{{lang|en|A Method for the Construction of Minimum-Redundancy Codes}}'' publiziert wurde.<ref name="orig_paper" /> Sie ordnet einer festen Anzahl an Quellsymbolen jeweils Codewörter mit variabler Länge zu. In der Informationstechnik ist sie ein [[Präfixcode]], der üblicherweise für verlustfreie Kompression benutzt wird. Wie bei anderen Entropiekodierungen werden häufiger vorkommende Zeichen mit weniger [[Bit|Bits]] repräsentiert als seltener vorkommende Zeichen.

== Grundlagen ==
[[Datei:Huffman tree 2.svg|mini|330x330px|klasse=skin-invert-image|Der Huffman-Baum für den Beispielsatz "''this is an example of a huffman tree''"]]
Um Daten möglichst [[Redundanz (Informationstheorie)|redundanzfrei]] darzustellen, müssen die [[Symbol (Nachrichtentechnik)|Quellsymbole]] mit [[Code]]wörtern unterschiedlicher [[Wortlänge]]n 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äfix-Code|präfixfrei]]'' sein, d. h., kein Codewort darf der Beginn eines anderen sein.

Die Grundidee ist, einen ''k''-nären Wurzelbaum (ein [[Baum (Graphentheorie)|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 ({{enS|''[[bottom-up]]''}}) erstellt.

Dieser [[Baum (Datenstruktur)|Baum]] kann mit einem [[Heap (Datenstruktur)|Heap]] und einer [[Vorrangwarteschlange]] implementiert werden.<ref>David Wagner, University of California, Berkeley: [https://people.eecs.berkeley.edu/~daw/teaching/cs170-s03/Notes/lecture16.pdf Data Compression via Huffman Coding]</ref><ref>Northeastern University: [https://www.ccs.neu.edu/home/vkp/2510-sp11/Labs/Lab11/lab11.pdf Priority Queue; Heapsort; Huffman Code]</ref>

Im Unterschied zum [[Morsecode]] benötigt man bei einer Huffman-Codierung keine Trennzeichen. Eine Trennung der Codewörter ist nicht notwendig, da die Codierung präfixfrei ist. Dadurch ist kein Codewort Anfang eines anderen Codewortes.

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.

== Geschichte ==
Im Jahre 1951 hatten [[David A. Huffman]] und seine Klassenkameraden am [[Massachusetts Institute of Technology|MIT]] im Kurs Informationstheorie die Wahl zwischen einer Seminararbeit und einer Abschlussprüfung. Die [[Seminararbeit]], betreut von Professor [[Robert Fano|Robert M. Fano]], sollte die Findung des effizientesten binären Codes thematisieren. Huffman, der nicht in der Lage war, die Effizienz eines Codes zu beweisen, war nur knapp vor dem Entschluss, aufzugeben und sich für die Abschlussprüfung vorzubereiten, als er auf die Idee stieß, einen frequenzsortierten [[Binärbaum]] zu verwenden, und somit in kürzester Zeit jene Methode als effizienteste beweisen konnte.

Auf diese Weise übertraf Huffman seinen Professor Fano, der gemeinsam mit dem Begründer der [[Informationstheorie]] [[Claude Shannon]] einen ähnlichen Code entwickelte. Indem Huffman den Baum von unten nach oben anstatt von oben nach unten erstellte, vermied er die größte Schwachstelle der suboptimalen [[Shannon-Fano-Kodierung]].<ref>[http://www.huffmancoding.com/my-uncle/scientific-american Profil: David A. Huffman]</ref>

== Algorithmus ==
[[Datei:Huffman coding visualisation.svg|mini|360x360px|klasse=skin-invert-image|Veranschaulichung einer Huffman-Kodierung. Das Quellalphabet ist <math>X := \{ \_, A, B, C, D, E \}</math> und das Codealphabet ist <math>C := \{ 0, 1 \}</math>. Schritt 1 zeigt den Originaltext. Die Schritte 2 bis 6 erzeugen den [[Baum (Graphentheorie)|Baum]]. Der fertige Baum in Schritt 6 wird durchlaufen, um das Codebuch zu erzeugen. Schritt 7 zeigt das Codebuch und Schritt 8 den codierten Text.]]
'''Definitionen'''
* '''<math>X</math>''' ist das Quellalphabet – der Zeichenvorrat, aus dem die Quellsymbole bestehen
* '''<math>p_x</math>''' ist die [[A-priori-Wahrscheinlichkeit]] und relative Häufigkeit des Symbols '''<math>x</math>''' 
* '''<math>C</math>''' ist das Codealphabet – der Zeichenvorrat, aus dem die Codewörter bestehen
* '''<math>m</math>''' ist die [[Mächtigkeit (Mathematik)|Mächtigkeit]] <math>\vert C \vert</math> des Codealphabetes '''<math>C</math>''' – die Anzahl der verschiedenen Zeichen

'''Erzeugen des Baumes'''
* 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.
* Erstelle für jedes Quellsymbol einen einzelnen [[Knoten (Graphentheorie)|Knoten]] (die einfachste Form eines Baumes) und notiere im Knoten die Häufigkeit.
* Wiederhole die folgenden Schritte so lange, bis nur noch ein einziger [[Baum (Graphentheorie)|Baum]] übrig ist:
** Wähle '''<math>m</math>''' (Teil-)Bäume mit den '''<math>m</math>''' geringsten Häufigkeiten in deren Wurzel (diese Wahl ist im Allgemeinen nicht eindeutig).
** Fasse diese '''<math>m</math>''' Bäume zu einem neuen (Teil-)Baum zusammen.
** Notiere die Summe der Häufigkeiten in der Wurzel.

'''Konstruktion des [[Codebuch|Codebuchs]]'''
* Ordne jedem Kind eines Knotens eindeutig ein Zeichen aus dem Codealphabet zu.
* Lies für jedes Quellsymbol (Blatt im [[Baum (Graphentheorie)|Baum]]) das Codewort aus:
** Beginne an der Wurzel des Baums.
** Die Codezeichen auf den [[Kante (Graphentheorie)|Kanten]] des [[Pfad (Graphentheorie)|Pfades]] von oben nach unten ergeben das zugehörige Codewort.

'''Kodierung'''
* Lies ein Quellsymbol ein.
* Ermittle das zugehörige Codewort aus dem Codebuch.
* Gib das Codewort aus.

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

* Über die gewichtete Summe der Codewortlängen:

::<math>\overline l = \sum_{x \in X} p_x l_x</math>  Die Summe aus der Anzahl der Schritte im Baum multipliziert mit der Häufigkeit eines Symbols.

* Indem man die Auftrittswahrscheinlichkeiten an allen ''Zwischen''knoten des Huffman-Baums summiert.
* Bei ausschließlich gleicher Häufigkeit  der zu codierenden Elemente ist die mittlere Länge
:: <math> l = \log_2 \ m</math> mit <math>m \in N</math> als Anzahl der zu codierenden Elemente.

=== Beispiele ===
[[Datei:Huffman tree 1.svg|mini|hochkant=1.5|klasse=skin-invert-image|Ein Huffman-Baum. Die Wurzel des Baumes befindet sich rechts, die Blätter links.]]
Das Quellalphabet sei <math>X := \{ a, b, c, d \}</math>. Als Codealphabet wählen wir den [[Binärcode]] <math>C := \{ 0, 1 \}</math> und <math>m = \vert C \vert = 2</math>. Der Text <math>aababcabcd</math> soll komprimiert werden.

Zuerst werden die [[Relative Häufigkeit|relativen Häufigkeiten]] bestimmt:

:<math>\begin{align}
p_a &= 0{,}4 \\
p_b &= 0{,}3 \\
p_c &= 0{,}2 \\
p_d &= 0{,}1
\end{align}</math>

Es wird ein Huffman-Baum konstruiert und anschließend die Codewörter an den Kanten eingetragen (siehe Bild rechts).

Daraus ergibt sich folgendes Codebuch:

:<math>\begin{align}
a &\rightarrow 1 \\
b &\rightarrow 01 \\
c &\rightarrow 001 \\
d &\rightarrow 000
\end{align}</math>

Mit diesem Codebuch wird der ursprüngliche Text kodiert:

{|
|-
| '''Originaltext''' || a || a || b  || a || b  || c   || a || b  || c   || d
|-
| '''Kodierter Text''' || 1 || 1 || 01 || 1 || 01 || 001 || 1 || 01 || 001 || 000
|}
Diese Huffman-Kodierung kodiert jedes Symbol mit durchschnittlich <math>\overline l = 0{,}4 \cdot 1 + 0{,}3 \cdot 2 + 0{,}2 \cdot 3 + 0{,}1 \cdot3 = 0{,}4 + 0{,}6 + 0{,}6 + 0{,}3 = 1{,}9</math> Bit. Das ist die mittlere Codewortlänge. Bei einer naiven [[Kodierung]] würde jedes der 4 Symbole mit <math>\log_2(4) = 2</math> Bit kodiert.

Die [[Entropie (Informationstheorie)|Entropie]] liegt bei

:<math>\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)) \\
     &\approx 1{,}846
\end{align}</math>

Bit je Symbol. Dadurch, dass der [[Informationsgehalt]] je Quellsymbol keine [[ganze Zahl]] ist, verbleibt bei der Kodierung eine Rest-Redundanz.

[[Datei:Huffman_tree_2.svg|rechts|rahmenlos|330x330px|klasse=skin-invert-image]]
Für den Beispielsatz "''this is an example of a huffman tree''" ist das Quellalphabet <math>X := \{\_,a,e,f,h,i,l,m,n,o,p,r,s,t,u,x\}</math> gegeben, wobei _ in diesem Fall für das [[Leerzeichen]] steht. Aus den absoluten Häufigkeiten der Quellsymbole, die in den Blättern des rechts dargestellten Huffman-Baums stehen, ergibt sich folgendes Codebuch:
{|
|'''absolute Häufigkeit'''
|'''Zuordnung'''
|-
| '''<math>\begin{align}
\_: 7 \\
a: 4 \\
e: 4 \\
f: 3 \\
h: 2 \\
i: 2 \\
l: 1 \\
m: 2 \\
n: 2 \\
o: 1 \\
p: 1 \\
r: 1 \\
s: 2 \\
t: 2 \\
u: 1 \\
x: 1 \\
\end{align}</math>'''
|'''<math>\begin{align}
\_ &\rightarrow 111 \\
a &\rightarrow 010 \\
e &\rightarrow 000 \\
f &\rightarrow 1101 \\
h &\rightarrow 1010 \\
i &\rightarrow 1000 \\
l &\rightarrow 11001 \\
m &\rightarrow 0111 \\
n &\rightarrow 0010 \\
o &\rightarrow 00110 \\
p &\rightarrow 10011 \\
r &\rightarrow 11000 \\
s &\rightarrow 1011 \\
t &\rightarrow 0110 \\
u &\rightarrow 00111 \\
x &\rightarrow 10010 \\
\end{align}</math>'''
|}
Mit diesem Codebuch wird der Beispielsatz kodiert:
{|
|-
| '''Originaltext''' || t || h || i  || s || _  || i   || s || _  || a   || n
|_
|e
|x
|a
|m
|p
|l
|e
|_
|o
|f
|_
|a
|_
|h
|u
|f
|f
|m
|a
|n
|_
|t
|r
|e
|e
|-
| '''Kodierter Text''' || 0110 || 1010 || 1000 || 1011 || 111 || 1000 || 1011 || 111 || 010 || 0010
|111
|000
|10010
|010
|0111
|10011
|11001
|000
|111
|00110
|1101
|111
|010
|111
|1010
|00111
|1101
|1101
|0111
|010
|0010
|111
|0110
|11000
|000
|000
|}
Diese Huffman-Kodierung kodiert jedes Symbol des Beispielsatzes (insgesamt 36 Zeichen) mit durchschnittlich

<math>\overline l = \tfrac{1}{36} \cdot (7 \cdot 3 + 4 \cdot 3 + 4 \cdot 3 + 3 \cdot 4 + 2 \cdot 4 + 2 \cdot 4 + 1 \cdot 5 + 2 \cdot 4 + 2 \cdot 4 + 1 \cdot 5 + 1 \cdot 5 + 1 \cdot 5 + 2 \cdot 4 + 2 \cdot 4 + 1 \cdot 5 + 1 \cdot 5) = \tfrac{1}{36} \cdot 135 = 3{,}75</math>

Bit. Das ist die mittlere Codewortlänge. Bei einer naiven [[Kodierung]] würde jedes der 16 Symbole mit <math>\log_2(16) = 4</math> Bit kodiert.

== Dekodierung ==
Zur Dekodierung eines Huffman-kodierten Datenstroms ist beim klassischen Verfahren das im Kodierer erstellte Codebuch notwendig. Grundsätzlich wird dabei umgekehrt als im Kodierungsschritt vorgegangen. Der Huffman-Baum wird im Dekodierer wieder aufgebaut und mit jedem eingehenden [[Bit]] – ausgehend von der Wurzel – der entsprechende [[Pfad (Graphentheorie)|Pfad]] im [[Baum (Graphentheorie)|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 ===
[[Datei:Huffman_tree_1.svg|rechts|rahmenlos|klasse=skin-invert-image]]
Der Dekodierer hat das Codebuch

:<math>\begin{align}
a &\rightarrow 1 \\
b &\rightarrow 01 \\
c &\rightarrow 001 \\
d &\rightarrow 000
\end{align}</math>

und die empfangene Nachricht 1101101001101001000.

Jetzt wird für jedes empfangene Bit ausgehend von der Wurzel der Pfad im Baum abgelaufen, bis ein Blatt erreicht wurde (siehe Abbildung). Sobald ein Blatt erreicht wurde, speichert der Dekodierer das Symbol des Blattes und beginnt wieder bei der Wurzel, bis das nächste Blatt erreicht wird. Daraus ergibt sich der dekodierte Text:

{|
|-
| '''Kodierter Text'''|| 1 || 1 || 01 || 1 || 01 || 001 || 1 || 01 || 001 || 000
|-
| '''Dekodierter Text'''|| a || a || b  || a || b  || c   || a || b  || c   || d
|}

== Pseudocode ==
Die folgenden Beispiele in [[Pseudocode]] zeigen [[Funktion (Programmierung)|Funktionen]] für die Generierung der Huffman-Kodierung.

=== Erzeugen des Baumes ===
Diese [[Funktion (Programmierung)|Funktion]] erzeugt einen Huffman Tree als [[Min-Heap]] und gibt einen [[Zeiger (Informatik)|Zeiger]] auf den Wurzelknoten zurück. Die [[Knoten (Graphentheorie)|Knoten]] des Min-Heap werden in einer [[Vorrangwarteschlange]] gespeichert.

 /**
  * left // linker Kindknoten
  * right // rechter Kindknoten
  * top // Elternknoten
  * minHeap // Vorrangwarteschlange für den Min-Heap
  */
  '''function''' createHuffmanTree(symbolList, frequencyList, symbolsCount)
  {
    // Fügt die Knoten mit Symbol und Häufigkeit in die Vorrangwarteschlange ein
    '''foreach''' (symbol in symbolList)
    {
        Knoten mit Symbol und Häufigkeit in minHeap einfügen
    }
    // Der HuffmanTree wird schrittweise erzeugt, bis sich alle Knoten einem Baum befinden und nur noch der Wurzelknoten in der Vorrangwarteschlange ist
    '''while''' (die Anzahl der Knoten in minHeap ist nicht 1) // Solange die Anzahl der Knoten in der Vorrangwarteschlange nicht 1 ist
    {
        // Entfernt die zwei Knoten mit der kleinsten Häufigkeit aus der Vorrangwarteschlange
        left := minHeap.top()
        minHeap.pop()
        right := minHeap.top()
        minHeap.pop()
        Erzeuge einen neuen inneren Knoten top mit der Summe der Häufigkeiten der zwei Knoten left->frequency und right->frequency
        // Fügt die zwei Knoten mit der kleinsten Häufigkeit als linken und rechten Kindknoten des neuen inneren Knoten in den Baum ein
        top->left := left
        top->right := right
        minHeap.push(top) // Fügt den neuen Knoten in die Vorrangwarteschlange ein
    }
    return minHeap.top() // Gibt einen Zeiger auf den Wurzelknoten zurück
  }

=== Erzeugen des Codebuchs ===
Diese [[Rekursive Programmierung|rekursive]] [[Funktion (Programmierung)|Funktion]] erzeugt das [[Codebuch]] für die Huffman-Kodierung, indem sie jedem Symbol des Quellalphabet ein [[Binärcode|binäres]] Codewort als [[Zeichenkette]] zuordnet.
 /**
  * dictionary // [[Zuordnungstabelle]] für das Codebuch
  */
  // Diese rekursive Funktion erzeugt das Codebuch für die Huffman-Kodierung und speichert es in der Variable dictionary
  '''function''' createDictionary(node, codeword, dictionary)
  {
    '''if''' (der Knoten ist node ist leer)
    {
        '''return'''; // [[Abbruchbedingung]], wenn kein linker oder rechter Teilbaum vorhanden ist
    }
    '''if''' (node->symbol is kein innerer Knoten, also ein Blatt) // Wenn der Knoten kein innerer Knoten, also ein Blatt ist
    {
        dictionary.insert(node->symbol, codeword); // Fügt die Kombination aus Symbol und Codewort dem Codebuch hinzu
        '''return'''; // Verlässt die Funktion
    }
    createDictionary(node->left, concat(codeword, "0"), dictionary) // Rekusiver Aufruf für den linken Teilbaum, das Codesymbol 0 für die linke Kante wird angefügt
    createDictionary(node->right, concat(codeword, "1"), dictionary) // Rekusiver Aufruf für den rechten Teilbaum, das Codesymbol 1 für die rechte Kante wird angefügt
  }

== Optimalität ==
Für mittlere Codewortlänge <math>\overline l</math> eines Huffman-Codes gilt<ref name="Strutz">Strutz: Bilddatenkompression, SpringerVieweg, 2009</ref>

: <math>\Eta(X) \leq \overline l \leq \Eta(X) + 1</math>

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

<math>\overline l = \Eta(X)</math> gilt genau dann, wenn alle [[Wahrscheinlichkeit|Wahrscheinlichkeiten]] [[Zweierpotenz|Zweierpotenzen]] sind (<math>2^{-m_x}, \; m_x \in \mathbb{N}^+</math>). In dem Fall sagt man, die Huffman-Kodierung sei ''optimal bezüglich der [[Entropie (Informationstheorie)|Entropie]]''.

Fasst man <math>n</math> Quellsymbole zu einem großen Symbol <math>y</math> zusammen, so gilt für die mittleren Codesymbollängen <math>\overline l_y</math>

: <math>\Eta_n(X) \leq \overline l_y \leq \Eta_n(X) + \frac{1}{n}</math>,

das heißt, mit zunehmender Anzahl <math>n</math> gemeinsam kodierter Quellsymbole geht die mittlere Codewortlänge asymptotisch gegen die [[Entropie (Informationstheorie)|Entropie]] – die Huffman-Kodierung ist ''asymptotisch optimal''.

Diese Optimalität der Huffman-Kodierung lässt sich mit [[Vollständige Induktion|vollständiger Induktion]] beweisen.<ref>University of California, Berkeley: [https://inst.eecs.berkeley.edu/~cs170/fa20/assets/notes/huffman.pdf Proof of Optimality of Huffman Coding]</ref><ref>University of Toronto: [https://www.cs.utoronto.ca/~brudno/csc373w09/huffman.pdf Proof of Optimality of Huffman Codes]</ref>

== Laufzeit ==
Sei <math>n</math> die Anzahl der Zeichen des Originaltexts und <math>d</math> die Anzahl der verschiedenen Zeichen (meist deutlich weniger als Zeichen im Text). Die erste Anweisung, die die Häufigkeiten der Zeichen zählt, hat die asymptotische Laufzeit <math>O(n)</math>, da sie jedes Zeichen im Text beachten muss. Die [[for-Schleife]] iteriert über die verschiedenen Zeichen im Quellalphabet. Diese Schleife iteriert lediglich <math>O(d)</math> Mal und nicht <math>O(n)</math> Mal. Die [[while-Schleife]] beginnt mit einer [[Vorrangwarteschlange]], die <math>d</math> Elemente enthält, und reduziert diese in jeder Iteration um ein Element. Sie iteriert also <math>O(d)</math> Mal. In jeder Iteration ruft sie zweimal die [[Funktion (Informatik)|Funktion]] ''pop'' und einmal die Funktion ''push'' auf, jeweils mit einer asymptotischen Laufzeit von <math>O(\log(d))</math> bei Verwendung eines [[Heap (Datenstruktur)|Heaps]]. Alle anderen [[Operation (Informatik)|Operationen]] innerhalb der while-Schleife sind in konstanter [[Laufzeit (Informatik)|Laufzeit]] implementierbar. Die Laufzeit der while-Schleife ist also <math>O(d \cdot \log(d))</math>. Damit ist die Gesamtlaufzeit für die Huffman-Kodierung <math>O(n + d \cdot \log(d))</math>.<ref>Justus Piater, Universität Innsbruck: [https://iis.uibk.ac.at/public/piater/courses/IIS/703010/notes/greedy/greedy.pdf Huffman Coding: Algorithmus und Analyse]</ref>

== Adaptive Huffman-Kodierung ==

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 ==
* [[Arithmetisches Kodieren]]
* [[Bereichskodierung]]
* [[Shannon-Fano-Kodierung]]
* [[Tunstall-Kodierung]]
* [[Asymmetric Numeral Systems]]
* [[Context-Adaptive Binary Arithmetic Coding]]

== Literatur ==
* Thomas M. Cover, Joy A. Thomas: ''Elements of Information Theory''

== Weblinks ==
* Freie Universität Berlin, Institut für Informatik: [https://www.inf.fu-berlin.de/lehre/WS11/infa/prefixcode.pdf Präfixcodes und der Huffman–Algorithmus]
* Freie Universität Berlin, Institut für Informatik: [https://www.inf.fu-berlin.de/lehre/WS12/ALP1/lectures/V16_ALPI_Huffman-Kodierung_2013.pdf Huffman-Kodierung]
* SwissEduc: [https://www.swisseduc.ch/informatik/daten/huffmann_kompression/docs/huffman.pdf Huffman-Code]
* LNTwww: [https://www.lntwww.de/Applets:Huffman-_und_Shannon-Fano-Codierung Huffman- und Shannon-Fano-Codierung]
* [https://www.javatpoint.com/huffman-coding-java Huffman Coding Java] (Codebeispiel in Java)
* Paul E. Black, National Institute of Standards and Technology: ''[http://xlinux.nist.gov/dads//HTML/huffmanCoding.html Huffman Coding]'', Dictionary of Algorithms and Data Structures.
* [https://huffman.ooz.ie/ Huffman Tree Generator] (Web Application)

== Einzelnachweise ==
<references>
<ref name="orig_paper">{{cite journal |author=D. A. Huffman |date=1952-09 |title=A method for the construction of minimum-redundancy codes |journal=Proceedings of the I.R.E. |pages=1098–1101 |url=http://compression.ru/download/articles/huff/huffman_1952_minimum-redundancy-codes.pdf |format=PDF |language=en}}
</ref>
</references>

[[Kategorie:Kompressionsalgorithmus]]
[[Kategorie:Kodierungstheorie]]