Huffman Codes¶
Beispiel für einen verlustfreien Komprimierungsalgorithmus.
Codes¶
Binäre Codes mit fester Länge (Fixed-Length Binary Codes)¶
Ein Alphabet $\Sigma$ ist eine endliche nicht-leere Menge von Symbolen.
In einem binären Code wird für jedes Symbol eine unterschiedliche Binärfolge geschrieben.
Beispiel: Bei einem Alphabet von $64$-Symbolen bietet es sich bei einem binären Code mit fester Länge an, eine Länge von $6$ zu wählen, da $2^6=64$.
Bemerkung: ACSII-Codes funktionieren im Prinzip so.
Ist es möglich dies besser zu machen?¶
statt
| Symbol | Codierung |
|---|---|
| $A$ | 00 |
| $B$ | 01 |
| $C$ | 10 |
| $D$ | 11 |
z.B.
| Symbol | Codierung |
|---|---|
| $A$ | 0 |
| $B$ | 01 |
| $C$ | 10 |
| $D$ | 1 |
Präfix-freie Codes¶
Für jedes Paar von Symbolen $A, B \in \Sigma$ ist die Kodierung von $A$ kein Präfix von $B$ und umgekehrt.
So erhält man eine eindeutige (unambigious) Codierung.
Beispiel:
| Symbol | Codierung |
|---|---|
| $A$ | 0 |
| $B$ | 10 |
| $C$ | 110 |
| $D$ | 111 |
Beachten Sie:
Präfix-freie Codes können effizienter sein, wenn die Symbole mit unterschiedlichen Häufigkeiten auftreten.
Beispiel mit Häufigkeiten:
| Symbol | Codierung | Häufigkeit |
|---|---|---|
| $A$ | 0 | 60% |
| $B$ | 10 | 25% |
| $C$ | 110 | 10% |
| $D$ | 111 | 5% |
Quiz: Erwartungswert für die durchschnittliche Anzahl von Symbolen¶
Wie hoch ist die durchschnittliche Anzahl von Symbolen für den obigen Präfix-freien Codes bei den gegebenen Häufigkeiten?
Problem: Optimale Prefix-freie Codes¶
Input: Eine nicht-negative Häufigkeit $p_a$ für jedes Symbol $a$ eines Alphabets $\Sigma$ der Größe $n\geq 2$.
Output: Ein Präfix-freier Binärcode mit der minimalen möglichen durchschnittlichen Codelänge $$ \sum_{a\in \Sigma} p_a \cdot \text{(Anzahl der Bits von }a) $$
mit der Häufigkeit (oder Wahrscheinlichkeit) $p_a$ für das Auftreten von $a$.
Codes als Bäume¶
Codes können als binäre Bäume repräsentiert werden. Die linke Kante wird mit 0 gekennzeichnet und die rechte mit 1 (oder umgekeht).
Die Symbole werden Knoten zugeordnet.
Der Code für ein Symbol wird dann dem (eindeutigen) Pfad aus den Kanten ausgehend von der Wurzel zum entsprechenden Knoten abgelesen.
Präposition 14.1. Kodierungslänge und Knotentiefe¶
Für jeden binären Code entspricht die Kodierungslänge in Bits einem Symbol $a \in \Sigma$ der Tiefe des Knotens in dem korrespondierenden Baum.
Präfix-freie Codes und Bäume¶
Präfix-freie Codes entsprechen Bäumen, bei denen nur die Blätter (Leafs) des Baums Symbolen zugeordnet sind.
Ein $\Sigma$-Baum ($\Sigma$-Tree) ist ein binärer Baum, bei dem die Blätter mit einer eins-zu-eins Korrespondenz den Symbolen des Alphabets $\Sigma$ zugeordnet sind.
Die durchschnittliche Tiefe $L(T, {\bf p})$ des $\Sigma$-Baums $T$ mit Symbolhäufigkeiten ${\bf p} = \{p_a\}_{a\in \Sigma}$ ist dabei
$$ L(T, {\bf p}) = \sum_{a\in \Sigma} p_a \cdot \left( \text{Tiefe des Blattes gekennzeichnet mit } a \text{ in } T \right) $$
Das Problem der optimalen Prefix-freie Codes kann umformuliert werden:
Problem: Optimale Prefix-freie Codes¶
Input: Eine nicht-negative Häufigkeit $p_a$ für jedes Symbol $a$ eines Alphabets $\Sigma$ der Größe $n\geq 2$.
Output: Ein $\Sigma$-Baum mit der minimal möglichen durchschnittlichen Baumtiefe.
Huffmans Greedy Algorithmus¶
Aufbau eines Baums durch suzessives Verbinden¶
- Jedes Symbol $a \in \Sigma$ ist zu Beginn ein eigener Baum, d.h. zu Beginn gibt es $n$-Bäume
- Durch Verbinden zweier Bäume über einen neuen root-Knoten verringert sich in jedem Schritt die Anzahl der Bäume um 1.
- Führe dieses Verbinden solange durch bis nur noch ein Baum (der $\Sigma$-Baum) übrig bleibt.
Quiz¶
Wie oft müssen wir das Verbinden (merge) durchführen?
Offene Frage: Welche Bäume sollen in jedem Teilschritt verbunden werden, um die durchschnittliche Codelänge zu minimieren.
Huffmans Greedy Kriterium¶
Verbinde die Bäume $T_i$ und $T_j$ mit dem niedrigst-möglichen Wachstum der durchschnittlichen Tiefe.
$$ \sum_{a \in T_i} p_a + \sum_{a \in T_j} p_a $$
Hufman¶
Input: : Eine nicht-negative Häufigkeit $p_a$ für jedes Symbol $a$ eines Alphabets $\Sigma$ der Größe $n\geq 2$.
Output: A $\Sigma$-Tree with the minimal possible leaf-depth representing a prefix-free binary code with the minimal possible average encoding length.
// initialization
for each $a \in \Sigma$ do
$T_a :=$ tree containing one node, labeled "$a$"
$P(T_a) := p_a$
$\mathcal F := \{T_a\}_{a \in \Sigma}$// invariant$\forall T \in \mathcal F, P(T)=\sum_{a\in T} p_a$
// main loop
while $\mathcal F$ contains at least two trees do
$T_1 := \arg\!\min_{T \in \mathcal F} P(T)$
$T_2 := \arg\!\min_{T \in \mathcal F, T \neq T_1} P(T)$
remove $T_1$ and $T_2$ from $\mathcal F$
// roots of$T_1$and$T_2$become left, right children of a new internal node
$T_3 :=$ merge of $T_1$ and $T_2$
$P(T_3) := P(T_1) + P(T_2)$\\ maintains invariant
add $T_3$ to $\mathcal F$
return the unique tree in $\mathcal F$
Beispiele¶
| Symbol | Häufigkeit |
|---|---|
| $A$ | 60% |
| $B$ | 25% |
| $C$ | 10% |
| $D$ | 5% |
- Merge von $D$ und $C$ zu $(DC)$
- Merge von $DC$ und $B$ zu $((DC)B)$
- Merge von $((DC)B)$ und $A$ zu $(((DC)B)A)$
| Symbol | Häufigkeit |
|---|---|
| $A$ | 3 |
| $B$ | 2 |
| $C$ | 6 |
| $D$ | 8 |
| $E$ | 2 |
| $F$ | 6 |
Laufzeit¶
- straitforward Implementierung: $O(n^2)$
- $n-1$ Merges in Main-Loop
- und geschachteltes Minima finden $O(n)$ (exhaustive search)
- bei Verwenden eines Heaps $O(n \log n)$
- oder mit Sortieren (in der Regel $O(n\log n)$) und zwei Queues: $O(n)$, siehe https://en.wikipedia.org/wiki/Huffman_coding. Bei einem vorsortierten Alphabet: $O(n)$
Beweis: siehe z.B. Tim Roughgarden: Algorithms Illuminated, Part 3, Chapter 14.4.