Beispiel für einen verlustfreien Komprimierungsalgorithmus.
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.
statt
| Symbol | Codierung |
|---|---|
| $A$ | 00 |
| $B$ | 01 |
| $C$ | 10 |
| $D$ | 11 |
z.B.
| Symbol | Codierung |
|---|---|
| $A$ | 0 |
| $B$ | 01 |
| $C$ | 10 |
| $D$ | 1 |
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 eindeutig (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% |
Wie hoch ist die durchschnittliche Anzahl von Symbolen für den obigen Präfix-freien Codes bei den gegebenen Häufigkeiten?
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) $$
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.
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 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:
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.
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.
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$
| Symbol | Häufigkeit |
|---|---|
| $A$ | 60% |
| $B$ | 25% |
| $C$ | 10% |
| $D$ | 5% |
| Symbol | Häufigkeit |
|---|---|
| $A$ | 3 |
| $B$ | 2 |
| $C$ | 6 |
| $D$ | 8 |
| $E$ | 2 |
| $F$ | 6 |
Beweis: siehe z.B. Tim Roughgarden: Algorithms Illuminated, Part 3, Chapter 14.4.