Information Theory/Further Source Coding Methods

1. Information Theory
2. Quellencodierung – Datenkomprimierung
3. Further Source Coding Methods

• Previous page
• Next page

• Previous page
• Next page

Der Shannon–Fano–Algorithmus

Die Huffman–Codierung aus dem Jahr 1952 ist ein Sonderfall der Entropiecodierung. Dabei wird versucht, das Quellensymbol $q_μ$ durch ein Codesymbol $c_μ$ der Länge $L_μ$ darzustellen, wobei folgende Konstruktionsvorschrift angestrebt wird:

$$L_{\mu} \approx {\rm log}_2\hspace{0.15cm}({1}/{p_{\mu}}) \hspace{0.05cm}.$$

Da $L_μ$ im Gegensatz zu log2(1/ $p_μ$) ganzzahlig ist, gelingt dies nicht immer. Bereits drei Jahre vor David A. Huffman haben Claude E. Shannon und Robert Fano einen ähnlichen Algorithmus angegeben, nämlich:

1. Man ordne die Quellensymbole nach fallenden Auftrittswahrscheinlichkeiten (identisch mit Huffman).
2. Man teile die sortierten Zeichen in zwei möglichst gleichwahrscheinliche Gruppen.
3. Der ersten Gruppe wird das Binärsymbol 1 zugeordnet, der zweiten die 0 (oder umgekehrt).
4. Sind in einer Gruppe mehr als ein Zeichen, so ist auf diese der Algorithmus rekursiv anzuwenden.

Wir gehen wie im Einführungsbeispiel für den Huffman–Algorithmus zu Beginn von Kapitel 2.3 von $M$ = 6 Symbolen und den folgenden Wahrscheinlichkeiten aus:

$$p_{\rm A} = 0.30 \hspace{0.05cm},\hspace{0.2cm}p_{\rm B} = 0.24 \hspace{0.05cm},\hspace{0.2cm}p_{\rm C} = 0.20 \hspace{0.05cm},\hspace{0.2cm} p_{\rm D} = 0.12 \hspace{0.05cm},\hspace{0.2cm}p_{\rm E} = 0.10 \hspace{0.05cm},\hspace{0.2cm}p_{\rm F} = 0.04 \hspace{0.05cm}.$$

Dann lautet der Shannon–Fano–Algorithmus:

1. AB → 1x (Wahrscheinlichkeit 0.54), CDEF → 0x (Wahrscheinlichkeit 0.46),
2. A → 11, B ⇒ 10,
3. C → 01, (Wahrscheinlichkeit 0.20), DEF → 00x, (Wahrscheinlichkeit 0.26),
4. D → D, (Wahrscheinlichkeit 0.12), EF → 000x (Wahrscheinlichkeit 0.14),
5. E → 0001, F → 0000.

Anmerkung: Ein „x” weist wieder darauf hin, dass in nachfolgenden Codierschritten noch Bits hinzugefügt werden müssen. Es ergibt sich hier zwar eine andere Zuordnung als bei der Huffman–Codierung, aber genau die gleiche mittlere Codewortlänge:

$$L_{\rm M} = (0.30\hspace{-0.05cm}+\hspace{-0.05cm} 0.24\hspace{-0.05cm}+ \hspace{-0.05cm}0.20) \hspace{-0.05cm}\cdot\hspace{-0.05cm} 2 + 0.12\hspace{-0.05cm} \cdot \hspace{-0.05cm} 3 + (0.10\hspace{-0.05cm}+\hspace{-0.05cm}0.04) \hspace{-0.05cm}\cdot \hspace{-0.05cm}4 = 2.4\,{\rm bit/Quellensymbol}\hspace{0.05cm}.$$

Mit den Wahrscheinlichkeiten entsprechend dem Beispiel 1 (auf der letzten Seite) führt der Shannon–Fano–Algorithmus zur gleichen mittleren Codewortlänge wie die Huffman–Codierung. Ebenso sind bei vielen (eigentlich: den meisten) anderen Wahrscheinlichkeitsprofilen Huffman und Shannon–Fano aus informationstheoretischer Sicht äquivalent. Es gibt aber durchaus Fälle, bei denen sich beide Verfahren hinsichtlich der (mittleren) Codewortlänge unterscheiden, wie das folgende Beispiel zeigt.

Wir betrachten $M$ = 5 Symbole mit folgenden Wahrscheinlichkeiten:

$$p_{\rm A} = 0.38 \hspace{0.05cm}, \hspace{0.2cm}p_{\rm B}= 0.18 \hspace{0.05cm}, \hspace{0.2cm}p_{\rm C}= 0.16 \hspace{0.05cm},\hspace{0.2cm} p_{\rm D}= 0.15 \hspace{0.05cm}, \hspace{0.2cm}p_{\rm E}= 0.13$$

$$\Rightarrow\hspace{0.3cm} H = 2.19\,{\rm bit/Quellensymbol} \hspace{0.05cm}. $$

Die Grafik zeigt die jeweiligen Codebäume für Shannon–Fano (links) bzw. Huffman (rechts). Die Ergebnisse lassen sich wie folgt zusammenfassen:

• Der Shannon–Fano–Algorithmus führt zum Code A → 11, B → 10, C → 01, D → 001, E → 000 und damit zur mittleren Codewortlänge

$$L_{\rm M} = (0.38 + 0.18 + 0.16) \cdot 2 + (0.15 + 0.13) \cdot 3 = 2.28\,\,{\rm bit/Quellensymbol}\hspace{0.05cm}.$$

• Mit dem Huffman–Algorithmus erhält man A → 1, B → 001, C → 010, D → 001 sowie E → 000 und eine etwas kleinere mittlere Codewortlänge:

$$L_{\rm M} = 0.38 \cdot 1 + (1-0.38) \cdot 3 = 2.24\,\,{\rm bit/Quellensymbol}\hspace{0.05cm}. $$

• Es gibt keinen Satz von Wahrscheinlichkeiten, bei denen Shannon–Fano ein besseres Ergebnis liefert als der Huffman–Algorithmus, der den bestmöglichen Entropiecodierer bereitstellt.
• Die Grafik zeigt zudem, dass die Algorithmen im Baumdiagramm in unterschiedlichen Richtungen vorgehen, nämlich einmal von der Wurzel zu den Einzelsymbolen (Shannon–Fano), zum anderen von den Einzelsymbolen zur Wurzel (Huffman).

Arithmetische Codierung

Eine weitere Form der Entropiecodierung ist die arithmetische Codierung. Auch bei dieser müssen die Symbolwahrscheinlichkeiten $p_μ$ bekannt sein. Für den Index gelte weiter $μ$ = 1, ... , $M$. Hier nun ein kurzer Abriss über die Vorgehensweise:

• Im Gegensatz zur Huffman– und Shannon–Fano–Codierung wird bei arithmetischer Codierung eine Symbolfolge der Länge N gemeinsam codiert. Wir schreiben abkürzend $Q = 〈q_1, q_2, ... , q_N〉$.
• Jeder solchen Symbolfolge $Q_i$ wird ein reelles Zahlenintervall $I_i$ zugewiesen, das durch den Beginn $B_i$ und die Intervallbreite $Δ_i$ gekennzeichnet ist.
• Der „Code” für die gesamte Folge $Q_i$ ist die Binärdarstellung eines reellen Zahlenwertes aus diesem Intervall: $r_i ∈ I_i = [B_i, B_i + Δ_i)$. Diese Notation besagt, dass zwar $B_i$ zum Intervall $I_i$ gehört (eckige Klammer), aber $B_i + Δ_i$ gerade nicht mehr (runde Klammer).
• Es gilt stets 0 ≤ $r_i$ < 1. Sinnvollerweise wählt man $r_i$ aus dem Intervall $I_i$ derart, dass der Wert mit möglichst wenigen Bits darstellbar ist. Es gibt aber eine Mindestbitanzahl, die von der Intervallbreite $Δ_i$ abhängt.

Der Algorithmus zur Bestimmung der Intervallparameter $B_i$ und $Δ_i$ wird auf der nächsten Seite an einem Beispiel erläutert, ebenso eine Decodiermöglichkeit. Zunächst folgt ein kurzes Beispiel zur Auswahl der reellen Zahl $r_i$ in Hinblick auf minimale Bitanzahl. Genauere Informationen hierzu finden Sie zum Beispiel in und bei der Beschreibung zur Aufgabe A1.12.

Für folgende Parameter des arithmetischen Codieralgorithmus ergeben sich folgende reelle Ergebnisse $r_i$ und folgende Codes, die zum zugehörigen Intervall $I_i$ gehören:

• $B_i = 0.25, Δ_i = 0.10 ⇒ I_i = [0.25, 0.35):$

$$r_i = 0 \cdot 2^{-1} + 1 \cdot 2^{-2} = 0.25 \hspace{0.3cm}\Rightarrow\hspace{0.3cm} {\rm Code} \hspace{0.15cm} \boldsymbol[[:Template:\rm 01]] \in I_i \hspace{0.05cm},$$

• $B_i = 0.65, Δ_i = 0.10 ⇒ I_i = [0.65, 0.75);$ zu beachten: 0.75 gehört nicht zum Intervall:

$$r_i = 1 \cdot 2^{-1} + 0 \cdot 2^{-2} + 1 \cdot 2^{-3} + 1 \cdot 2^{-4} = 0.6875 \hspace{0.3cm}\Rightarrow\hspace{0.3cm} {\rm Code} \hspace{0.15cm} \boldsymbol[[:Template:\rm 1011]] \in I_i\hspace{0.05cm}. $$

Um den sequentiellen Ablauf zu organisieren, wählt man allerdings die Bitanzahl konstant zu

$$N_{\rm Bit} = \left\lceil {\rm log}_2 \hspace{0.15cm} ({1}/{\it \Delta_i})\right\rceil+1\hspace{0.05cm}. $$

Mit der Intervallbreite $Δ_i$ = 0.10 ergibt sich $N_{\rm Bit}$ = 5. Die tatsächlichen arithmetischen Codes wären also 01000 bzw. 10110.

Die Aussagen der letzten Seite sollen nun an einem weiteren Beispiel verdeutlicht werden. Im Folgenden sei der Symbolumfang $M$ = 3. Um Verwechslungen zu vermeiden, nennen wir die Symbole X, Y und Z:

• Übertragen werden soll die Zeichenfolge XXYXZ ⇒ Folgenlänge $N$ = 5.
• Auszugehen ist von den Wahrscheinlichkeiten $p_X$ = 0.6, $p_Y$ = 0.2, $p_Z$ = 0.2.

Die Grafik zeigt den Algorithmus zur Bestimmung der Intervallgrenzen.

• Man teilt zunächst den gesamten Wahrscheinlichkeitsbereich (zwischen 0 und 1) gemäß den Symbolwahrscheinlichkeiten $p_X$, $p_Y$ und $p_Z$ in drei Bereiche mit den Grenzen $B_0$, $C_0$, $D_0$ und $E_0$.
• Das erste Symbol ist X. Deshalb wird im nächsten Schritt der Wahrscheinlichkeitsbereich von $B_1$ = $B_0$ = 0 bis $E_1$ = $C_0$ = 0.6 wiederum im Verhältnis 0.6 : 0.2 : 0.2 aufgeteilt.
• Nach dem zweiten Symbol X liegen die Bereichsgrenzen bei $B_2$ = 0, $C_2$ = 0.216, $D_2$ = 0.288 und $E_2$ = 0.36. Da nun das Symbol Y ansteht, erfolgt die Unterteilung des Bereiches 0.216 ... 0.288.
• Nach dem fünften Symbol Z liegt das Intervall $I_i$ für die betrachtete Symbolfolge $Q_i$ = XXYXZ fest. Es muss nun eine reelle Zahl $r_i$ gefunden werden, für die gilt: 0.25056 ≤ $r_i$ < 0.2592.
• Die einzige reelle Zahl im Intervall $I_i$ = [0.25056, 0.2592), die man mit 7 Bit darstellen kann, ist $r_i = 1 · 2^{–2} + 1 · 2^{–7} = 0.2578125$. Damit liegt die Coderausgabe fest: 0100001.

Für diese $N$ = 5 Symbole werden also 7 Bit benötigt, genau so viele wie bei Huffman–Codierung mit der Zuordnung X → 1, Y → 00, Z → 01. Die arithmetische Codierung ist allerdings dann dem Huffman–Code überlegen, wenn die tatsächlich bei Huffman verwendete Bitanzahl noch mehr von der optimalen Verteilung abweicht, zum Beispiel, wenn ein Zeichen extrem häufig vorkommt. Oft wird aber die Intervallmitte – im Beispiel 0.25488 – binär dargestellt: 0.01000010011 .... Die Bitanzahl erhält man daraus mit $Δ_5$ = 0.2592 - 0.25056 = 0.00864 wie folgt:

$$N_{\rm Bit} = \left\lceil {\rm log}_2 \hspace{0.15cm} \frac{1}{0.00864} \right\rceil + 1\hspace{0.15cm} = \left\lceil {\rm log}_2 \hspace{0.15cm} 115.7 \right\rceil + 1 = 8 \hspace{0.05cm}.$$

Damit lautet der arithmetische Code für dieses Beispiel mit $N$ = 5 Eingangszeichen: 01000010. Der Decodiervorgang lässt sich ebenfalls anhand der obigen Grafik erklären. Die ankommende Bitsequenz 0100001 wird zu $r$ = 0.2578125 gewandelt. Dieser liegt im ersten und zweiten Schritt jeweils im ersten Bereich ⇒ Symbol X, im dritten Schritt in zweiten Bereich ⇒ Symbol Y, usw. Weitere Informationen zu diesem Thema finden Sie in WIKIPEDIA sowie in .

Lauflängencodierung – Run–Length Coding

Wir betrachten eine Binärquelle $(M = 2)$ mit dem Symbolvorrat {A, B}, wobei ein Symbol sehr viel häufiger auftritt als das andere. Beispielsweise sei $p_A$ sehr viel größer als $p_B$.

Eine Entropiecodierung macht hier nur dann Sinn, wenn man diese auf k–Tupel anwendet. Eine zweite Möglichkeit bietet die Lauflängencodierung (englisch: Run–Length Coding, RLC), die das seltenere Zeichen B als Trennzeichen betrachtet und die Längen $L_i$ der einzelnen Substrings als Ergebnis liefert.

Die Grafik zeigt eine beispielhafte Binärfolge mit den Wahrscheinlichkeiten $p_A$ = 0.9 und $p_B$ = 0.1, woraus sich die Quellenentropie $H$ = 0.469 bit/Quellensymbol ergibt. Die Beispielfolge der Länge $N$ = 100 beinhaltet genau zehnmal das Symbol B und neunzigmal das Symbol A, das heißt, die relativen Häufigkeiten stimmen exakt mit den Wahrscheinlichkeiten überein.

Man erkennt an diesem Beispiel:

• Die Binärfolge hat die Länge $N$ = 100. Die Lauflängencodierung dieser Folge ergibt in Dezimalschreibweise die Folge 6, 14, 26, 11, 4, 10, 3, 9, 1, 16.
• Stellt man die Längen $L_1$, ... , $L_{10}$ mit jeweils 5 Bit dar, so benötigt man 5 · 10 = 50 Bit. Die Datenkomprimierung ist nicht viel schlechter als der theoretische Grenzwert, der sich durch die Quellenentropie $H$ ergibt ($H · N$ ≈ 47 Bit).
• Die direkte Anwendung einer Entropiecodierung – zum Beispiel nach Huffman – hätte hier keine Datenkomprimierung zur Folge; man benötigt weiterhin 100 Bit. Auch bei der Bildung von Dreiertupeln würde man mit Huffman noch mehr Bit benötigen als durch RLC, nämlich 54 Bit.

Das Beispiel zeigt aber auch zwei Probleme der Lauflängencodierung:

• Die Längen $L_i$ der Substrings sind nicht begrenzt. Hier muss man besondere Maßnahmen treffen, wenn eine Länge $L_i$ größer ist als $2^5 = 32$ (falls $N_{Bit}$ = 5), zum Beispiel die Variante Run–Length Limited Coding (RLLC). Siehe auch und Aufgabe A2.13.
• Endet die Folge nicht mit einem B – was bei kleiner Wahrscheinlichkeit $p_B$ eher der Normalfall ist, so muss auch für das Dateiende eine Sonderbehandlung vorgesehen werden.

Burrows–Wheeler–Transformation

Zum Abschluss dieses Quellencodier–Kapitels behandeln wir noch kurz den 1994 von Michael Burrows und David J. Wheeler veröffentlichten Algorithmus ,

• der zwar alleine keinerlei Komprimierungspotenzial besitzt,
• aber die Komprimierungsfähigkeit anderer Verfahren stark verbessert.

Die Burrows–Wheeler–Transformation bewerkstelligt eine blockweise Sortierung von Daten, die in der folgenden Grafik am Beispiel des Textes ANNAS_ANANAS der Länge $N$ = 12 verdeutlicht werden:

• Zunächst wird aus dem String der Länge $N$ eine $N×N$–Matrix erzeugt, wobei sich jede Zeile aus der Vorgängerzeile durch zyklische Linksverschiebung ergibt.
• Danach wird die BWT–Matrix lexikografisch sortiert. Das Ergebnis der Transformation ist die letzte Spalte ⇒ L–Spalte. Im Beispiel ergibt sich der String _NSNNAANAAAS.
• Des Weiteren muss auch der Primärindex I weitergegeben werden. Dieser gibt die Zeile der sortierten BWT–Matrix an, die den Originaltext enthält (in der Grafik rot markiert).

Zur Bestimmung von L–Spalte und Primärindex $I$ sind natürlich keine Matrixoperationen erforderlich. Vielmehr findet man das BWT–Ergebnis mit Zeigertechnik sehr schnell. Außerdem ist zum BWT–Verfahren noch anzumerken:

• Ohne Zusatzmaßnahme ⇒ eine nachgeschaltete „echte Kompression” – führt die BWT zu keiner Datenkomprimierung: Vielmehr ergibt sich sogar eine geringfügige Erhöhung der Datenmenge, da außer den $N$ Zeichen nun auch der Primärindex $I$ übermittelt werden muss.
• Bei längeren Texten ist dieser Effekt aber vernachlässigbar. Geht man von 8 Bit–ASCII–Zeichen (jeweils ein Byte) und der Blocklänge $N$ = 256 aus, so erhöht sich die Byte–Anzahl pro Block nur von 256 auf 257, also lediglich um 0.4%.

Wir verweisen auf die ausführlichen Beschreibungen zur BWT in .

Abschließend soll noch dargestellt werden, wie der Ursprungstext aus der L–Spalte der BWT–Matrix rekonstruiert werden kann. Dazu benötigt man noch den Primärindex $I$, sowie die erste Spalte der BWT–Matrix. Diese F–Spalte (von „First”) muss nicht übertragen werden, sondern ergibt sich aus der L–Spalte sehr einfach durch lexikografische Sortierung.

[[File: P_ID2476__Inf_T_2_4_S3b_neu.png|Beispiel zur BWT (Rücktransformation)]]

Die Grafik zeigt die Vorgehensweise für das betrachtete Beispiel:

• Man beginnt in der Zeile mit dem Primärindex $I$. Als erstes Zeichen wird das rot markierte A in der F–Spalte ausgegeben. Dieser Schritt ist in der Grafik mit einer gelben (1) gekennzeichnet.
• Dieses A ist das dritte A–Zeichen in der F–Spalte. Man sucht nun das dritte A in der L–Spalte, findet dieses in der mit (2) markierten Zeile und gibt das zugehörige N der F–Spalte aus.
• Das letzte N der L–Spalte findet man in der mit (3) gekennzeichneten Zeile. Ausgegeben wird das Zeichen der F–Spalte in der gleichen Zeile, also wieder ein N:

Nach $N$ = 12 Decodierschritten ist die Rekonstruktion abgeschlossen. Dieses Beispiel hat gezeigt, dass die BWT nichts anderes ist als ein Sortieralgorithmus für Texte. Das Besondere daran ist, dass die Sortierung eindeutig umkehrbar ist. Diese Eigenschaft und zusätzlich seine innere Struktur sind die Grundlage dafür, dass man das BWT–Ergebnis mittels bekannter und effizienter Verfahren wie Huffman (eine Form der Entropiecodierung) und RLC (Run–Length Coding) komprimieren kann.

Anwendungsszenario für BWT

Als Beispiel für die Einbettung der Burrows–Wheeler–Transformation (BWT) in eine Kette von Quellencodierverfahren wählen wir eine in vorgeschlagene Struktur:

Wir verwenden dabei das gleiche Textbeispiel ANNAS_ANANAS wie auf der letzten Seite. Die entsprechenden Strings nach den einzelnen Blöcken sind in der Grafik ebenfalls angegeben.

• Das Ergebnis der BWT lautet: _NSNNAANAAAS. An der Textlänge $N$ = 12 hat die BWT nichts verändert, doch gibt es jetzt vier Zeichen, die identisch mit ihren Vorgängerzeichen sind (in der Grafik rot hervorgehoben). Im Originaltext war dies nur einmal der Fall.
• Im nächsten Block MTF (Move–To–Front) wird aus jedem Eingangszeichen aus der Menge {A, N, S, _} ein Index $I$ ∈ {0, 1, 2, 3}. Es handelt sich hierbei aber nicht um ein einfaches Mapping, sondern um einen Algorithmus, der in Aufgabe Z1.14 angegeben ist.
• Für unser Beispiel lautet die MTF–Ausgangsfolge 323303011002, ebenfalls mit der Länge $N$ = 12. Die vier Nullen in der MTF–Folge (in der Grafik ebenfalls mit roter Schrift) geben an, dass an diesen Stellen das BWT–Zeichen jeweils gleich ist wie sein Vorgänger.
• Bei großen ASCII–Dateien kann die Häufigkeit der 0 durchaus >50% betragen, während die anderen 255 Indizes nur selten auftreten. Zur Komprimierung einer solchen Textstruktur eignet sich eine Lauflängencodierung (englisch: Run–Length Coding, RLC) hervorragend.
• Der Block RLC0 in obiger Codierungskette bezeichnet eine spezielle Lauflängencodierung für Nullen. Die graue Schattierung der Nullen soll andeuten, dass hier eine lange Nullsequenz durch eine spezifische Bitfolge (kürzer als die Nullsequenz) maskiert wurde.
• Der Entropiecodierer ( EC, z.B. Huffman ) sorgt für eine weitere Komprimierung. BWT und MTF haben in der Codierungskette nur die Aufgabe, durch eine Zeichenvorverarbeitung die Effizienz von RLC0 und EC zu steigern. Die Ausgangsdatei ist wieder binär.

Quellenverzeichnis

</references>