Dresden Algorithmics Channel: Modul 31

Eine Informationsquelle $\epsfbox{modul31_1.ps}$ $\displaystyle {a_i\in A\atop p_i}$ ; i = 1(1)n

gibt in den Zeitpunkten t $\in$ $\mathbb{N}$ ₀
jeweils genau ein Zeichen a_i aus einem endlichen Zeichenvorrat A aus.
Diese Ausgabe erfolgt stochastisch (zufälliges Ereignis). Dabei kann für jedes Zeichen a_i $\in$ A die Ausgabewahrscheinlichkeit p_i (als Grenzfall der relativen Häufigkeit) angegeben werden und es ist $\sum\limits_{i=1}^{n}$ p_i = 1 (stationäres vollständiges System zufälliger Ereignisse).

Die so charakterisierte Quelle wird formal durch die Matrix (endliches Schema) $\left(\vphantom{ \begin{array}{c} a_i\\ p_i \end{array}}\right.$ $\begin{array}{c} a_i\\ p_i \end{array}$ $\begin{array}{l} n\\ i=1 \end{array}$ beschrieben.
Gesucht ist ein optimaler Binärkode für die Zeichen der Quelle $\left(\vphantom{ \begin{array}{c} a_i\\ p_i \end{array}}\right.$ $\begin{array}{c} a_i\\ p_i \end{array}$ $\begin{array}{l} n\\ i=1 \end{array}$ mit den Eigenschaften

Jedem Quellenzeichen a_i ist eineindeutig ein binäres Kodewort w_i der Länge m_i zugeordnet.
Kein Kodewort ist dabei Anfangsteil eines anderen längeren Kodewortes (Präfixeigenschaft, dadurch ist die eindeutige und unverzögerte Dekodierbarkeit ohne Verwendung eines Trennzeichens gewährleistet).
Die mittlere Kodewortlänge pro Quellenzeichen $\overline{m}$ = $\sum\limits_{i=1}^{n}$ p_im_i (statistisches Mittel) besitzt dabei den kleinstmöglichen Wert, das impliziert $\displaystyle {(\forall i)(\forall j)\atop i\neq j}$ p_i $\ge$ p_j $\rightarrow$ m_i $\le$ m_j (häufige/seltene Quellenzeichen haben kurze/lange Kodewörter).
Auf diese Weise wird die kürzeste Binärdarstellung der von der Quelle $\left(\vphantom{ \begin{array}{c} a_i\\ p_i \end{array}}\right.$ $\begin{array}{c} a_i\\ p_i \end{array}$ $\begin{array}{l} n\\ i=1 \end{array}$ in Form einer Quellenzeichenfolge $\in$ A^* ausgegebenen Information realisiert ( $\longrightarrow$ möglichst schnelle sequentielle Informationsübertragung über einen Binärkanal bzw. speicherplatzsparendste Binärspeicherung der Information; Datenkompression [2,3,4,5,6]).

Beispiel:

i	1	2	3	4	5	6	7
a_i	a₁	a₂	a₃	a₄	a₅	a₆	a₇
p_i	0.1	0.3	0.05	0.1	0.2	0.05	0.2
w_i	110	10	11110	1110	00	11111	01

Quellenzeichenfolge	a₂a₂a₅a₆							$\longrightarrow$
Binärzeichenfolge	10	$\downarrow$	10	$\downarrow$	00	$\downarrow$	11111	$\downarrow$
		a₂		a₂		a₅		a₆
Verfälschte Binärzeichenfolge	10	$\downarrow$	1 10	$\downarrow$	01	$\downarrow$	1111	$\downarrow$
		a₂		a₁		a₇		?

Im allgemeinen existieren zu den Zeichen einer Quelle $\left(\vphantom{ \begin{array}{c} a_i\\ p_i \end{array}}\right.$ $\begin{array}{c} a_i\\ p_i \end{array}$ $\begin{array}{l} n\\ i=1 \end{array}$ mehrere voneinander verschiedene optimale Binärkodes, die aber alle die gleiche mittlere Kodewortlänge $\overline{m}$ besitzen und in diesem Sinne äquivalent sind.
Wir betrachten zunächst eine anschauliche textlich-graphische Variante des Huffman-Algorithmus zur optimalen Binärkodierung gemäß (A1), die in jedem Falle genau eine Lösung liefert.
Die Erzeugung der Kodewörter erfolgt hier durch schrittweisen Aufbau des zugehörigen ,,Kodebaumes`` (binäres bewertetes Quellenbüschel) aus binären ,,Gabeln`` von den Blattknoten ausgehend in Richtung Wurzelknoten (bottom-up) mittels Algorithmus (A1) unter Benutzung des nachstehenden Arbeitsschemas Bild 1,
Beispiel: Quelle $\left(\vphantom{ \begin{array}{ccccccc} a_1&a_2&a_3&a_4&a_5&a_6&a_7\\ 0.1&0.3&0.05&0.1&0.2&0.05&0.2 \end{array}}\right.$ $\begin{array}{ccccccc} a_1&a_2&a_3&a_4&a_5&a_6&a_7\\ 0.1&0.3&0.05&0.1&0.2&0.05&0.2 \end{array}$ $\left.\vphantom{ \begin{array}{ccccccc} a_1&a_2&a_3&a_4&a_5&a_6&a_7\\ 0.1&0.3&0.05&0.1&0.2&0.05&0.2 \end{array}}\right)$ .

$\epsfbox{modul31_2.ps}$
Bild 1: Huffman-Algorithmus, Arbeitsschema der textlich-graphischen Variante

$\epsfbox{modul31_4.ps}$
Algorithmus (A1): Huffman-Algorithmus, textlich-graphische Variante

Kommentare zu (A1):

1.

Jeder gemäß (A1) konstruierte Kodebaum mit n Blattknoten

besitzt genau n - 1 Nichtblattknoten (,,Gabelknoten``)
und ist damit mittels (A1) in n - 1 Schritten konstruierbar.
( $\forall$ i) m_i $\le$ n - 1 .

2.

Die in (A1) in der Initialisierung für die Kopfzeile des Arbeitsschemas geforderte Ordnung der Quellenelemente ist nicht notwendiger Bestandteil des Huffman-Algorithmus, sie wird neben der so zu gewährleistenden Eindeutigkeit der Kodebaumkonstruktion zum Zwecke der besseren Übersichtlichkeit des Kodebaumes eingeführt.

3.

Das gleiche gilt für das im Schleifenkörper von (A1) geforderte rechtsbündige Zusammenfassen.

4.

$\textstyle \parbox{9.5cm}{Im Schleifenk\uml {o}rper von (A1) kann die Kodezeichenbewertung der Gabel auch anders vereinbart werden:}$ $\epsfbox{modul31_3a.ps}$
sie muß aber in jedem Falle innerhalb einer Kodebaumerzeugung in der vereinbarten Form durchgeführt werden.

Während bei der vorstehend betrachteten textlich-graphischen Variante des Huffman-Algorithmus Kodierung (a_i $\rightarrow$ w_i) und Dekodierung (w_i $\rightarrow$ a_i) unter Benutzung der im zugehörigen Arbeitsschema der Kodebaumkonstruktion (Bild 1) enthaltenen Kodetabelle (Zuordnung Quellenzeichen - Kodewörter) erfolgen, wird für die rechnerorientierte Variante des Huffman-Algorithmus zweckmäßigerweise (geringerer Aufwand, keine Kodetabellenabspeicherung) eine dynamische Kodierung (Einzelkodeworterzeugung) und Dekodierung realisiert.
Dementsprechend ist diese Variante des Huffman-Algorithmus in drei Teil-Algorithmen aufzuspalten:

1.: Kodebaumkonstruktion
Konstruktion einer möglichst einfachen rechnergerechten Speicherform des Kodebaumes als Grundlage für eine einfache dynamische Kodierung und Dekodierung, hier: Speicherung des Kodebaumes in Form von zwei eindimensionalen (n - 1)-komponentigen Feldern b0 und b1.
2.: Kodierung (a_i $\rightarrow$ w_i) bei gegebenen Feldern b0 und b1.
3.: Dekodierung (w_i $\rightarrow$ a_i) bei gegebenen Feldern b0 und b1.

Zu 1. Kodebaumkonstruktion

Grundidee
$\epsfbox{modul31_6.ps}$
Algorithmus (A2): Huffman-Algorithmus, rechnerorientierte Variante, Grundidee

$\epsfbox{modul31_7.ps}$
Bild 2: Huffman-Algorithmus, Arbeitsschema zu (A2), Beispiel wie Bild 1

Kommentare zu (A2) und Bild 2:

1.
Die n Blattknoten des Kodebaumes werden mit der Nummer des zugehörigen Quellenelementes belegt.
2.
Im Prozeß der Kodebaumerzeugung werden die Zwischenknoten (Gabelknoten) ebenfalls nummeriert und zwar erhält der neue Zwischenknoten die Nummer seines 0-seitigen Vorgängers.
3.
In jedem Gabelerzeugungsschritt j werden 0-seitige und 1-seitige Vorgängerknoten als Feldelemente b0[j] und b1[j] gespeichert, 0-seitiger Vorgänger ist zugleich aktueller Zwischenknoten.
4.
Der Kodebaum läßt sich dann aus den Feldern b0 und b1 (minimale Speicherform) eindeutig rekonstruieren, damit sind auch Kodierung und Dekodierung auf der Grundlage von b0 und b1 eindeutig möglich (Bild 3).

$\epsfbox{modul31_8.ps}$
Bild 3: Rekonstruktion des Kodebaumes und der Kodetabelle aus b0 und b1
Rechnerorientierter Algorithmus zur Erzeugung der Felder b0 und b1

$\epsfbox{modul31_9.ps}$
Algorithmus (A3): Huffmann-Algorithmus, rechnerorientierte Variante

Zu 2. Kodierung

Gegeben:	Quellenzeichen a_k, n, Felder b0 und b1
Gesucht:	Kodewort w_k
Lösung:	(A4)

$\epsfbox{modul31_10.ps}$
Algorithmus (A4): Huffmann-Algorithmus, dynamische Kodierung

Kommentare zu (A4):

1.: In den Feldern b0 und b1 wird mit i = 1 beginnend Blattknoten k gesucht.
2.: Anschließend Aufbau des Kodewortes w_k von Blattknoten k $\longrightarrow$ Wurzelknoten.
3.: Nachfolgerzwischenknoten ist b0[i], von ihm aus wird die Suche fortgesetzt.

Beispiel: k = 3 , n = 7

i b0[i] b1[i] x y

3 $\varepsilon$

1 3 6 0

2 3 4 00

3 7 1

4 3 5 000

5 2 7

6 2 3 2 w₃ =1000

Zu 3. Dekodierung

Gegeben: w $\in$ {0, 1}^*, n, Felder b0 und b1

Gesucht: Ist w $\in$ {w₁, w₂,..., w_n}? Wenn ja: a_k

Lösung: (A5)

$\epsfbox{modul31_11.ps}$
Algorithmus (A5): Huffmann-Algorithmus, dynamische Dekodierung

Kommentare zu (A5):

1.: Dekodieren $\widehat{=}$ linksseitiges ,,Abtragen``von w vom Wurzelknoten b0[n - 1] zum Blattknoten k.
2.: left(y, 1) - linksseitig erstes Zeichen von y
3.: Das linksseitig erste Zeichen von y wird entfernt (entkettet).

Beispiel: w = 011 , n = 7

i b0[i] b1[i] x y

2 011

6 2 3 2 11

5 2 7 7 1

4 3 5

3 7 1 1 $\varepsilon$

2 3 4

1 3 6 k = 1

$\longrightarrow$ w ist Kodewort für a_k = a₁

Aufgabe 1
Vergleichen Sie die vorliegende rechnerorientierte Variante des Huffman-Algorithmus mit anderen Lösungen, z.B. in [7, 8, 9, 10, 11].

Foto: R. Dietzel

[ 1] D.A. Huffman. A Method for the Construction of Minimum-Redundancy Codes.
Proceedings of the IRE 40(1952)9, 1098-1101
[ 2] J. Storer. Data Compression: Methods and Theory.
Rockville 1988
[ 3] T. Bell, J. Cleary, I. Witten. Text Compression.
Englewood Cliffs 1990
[ 4] M. Nelson, J.-L. Gailly. The Data Compression Book.
New York 1995
[ 5] K. Sayood. Introduction to Data Compression.
San Francisco 1996
[ 6] D. Salomon. Data Compression: The Complete Reference.
New York 1997
[ 7] D.E. Knuth. The Art of Computer Programming. Vol.I: Fundamental Algorithms.
Reading, 1997, 1998
[ 8] T.H. Cormen, C.E. Leiserson, R.L. Rivest. Introduction to Algorithms.
Cambridge, London, New York, Toronto 1994
[ 9] R. Sedgewick, P. Flajolet. An Introduction to the Analysis of Algorithms.
Reading 1996
[10] D.S. Hirschberg, D.A. Lelewer. Efficient Decoding of Prefix Codes.
Communications of the ACM 33(1990)4, 449-459
[11] J.S. Vitter. Dynamic Huffman Coding.
ACM Trans. Math. Softw. 15(1989)2, 158-167

Die Module

i	b0[i]	b1[i]	x	y
			3	$\varepsilon$
1	3	6		0
2	3	4		00
3	7	1
4	3	5		000
5	2	7
6	2	3	2	w₃ =1000

Gegeben:	w $\in$ {0, 1}^*, n, Felder b0 und b1
Gesucht:	Ist w $\in$ {w₁, w₂,..., w_n}? Wenn ja: a_k
Lösung:	(A5)

[ 1]	D.A. Huffman. A Method for the Construction of Minimum-Redundancy Codes. Proceedings of the IRE 40(1952)9, 1098-1101
[ 2]	J. Storer. Data Compression: Methods and Theory. Rockville 1988
[ 3]	T. Bell, J. Cleary, I. Witten. Text Compression. Englewood Cliffs 1990
[ 4]	M. Nelson, J.-L. Gailly. The Data Compression Book. New York 1995
[ 5]	K. Sayood. Introduction to Data Compression. San Francisco 1996
[ 6]	D. Salomon. Data Compression: The Complete Reference. New York 1997
[ 7]	D.E. Knuth. The Art of Computer Programming. Vol.I: Fundamental Algorithms. Reading, 1997, 1998
[ 8]	T.H. Cormen, C.E. Leiserson, R.L. Rivest. Introduction to Algorithms. Cambridge, London, New York, Toronto 1994
[ 9]	R. Sedgewick, P. Flajolet. An Introduction to the Analysis of Algorithms. Reading 1996
[10]	D.S. Hirschberg, D.A. Lelewer. Efficient Decoding of Prefix Codes. Communications of the ACM 33(1990)4, 449-459
[11]	J.S. Vitter. Dynamic Huffman Coding. ACM Trans. Math. Softw. 15(1989)2, 158-167

Modul 31

Zur rechentechnischen Realisierung der optimalen Binärkodierung der Zeichen einer Quelle mit dem Huffman-Algorithmus

Aufgabe 1