gilt:
.(Die Entropie ist eine untere Schranke des mittleren Codieraufwandes!)
mit 
.(Eine Huffman-Codierung hat diese Eigenschaft.)
(6. Vorlesung, letzte Änderung: 23.11.2005)
Bei dem Beispiel aus der letzten Vorlesung ist es natürlich kein Zufall, dass die Entropie mit dem mittleren Codieraufwand der Huffman-Codierung zusammenfällt. Allgemein gilt folgender Satz von Shannon.
Satz:
Sei X ein Alphabet und P ein Wahrscheinlichkeitsmaß für die Buchstaben des Alphabets X.
gilt:. mit .Beispiel (Huffman-Codierung zu Werten aus Tabelle 4)
Tabelle 5 (Berechnung von mittlerem Codieraufwand und Entropie zu obigem Beispiel)
i xi pi C(xi) length(C(xi)) pi*length(C(xi)) ld(pi) pi*ld(pi)
---------------------------------------------------------------------------------
1 e 0,1305 000 3 0,3915 -2,9379 -0,3834
2 t 0,0902 00L 3 0,2706 -3,4707 -0,3131
3 o 0,0821 00L0 4 0,3284 -3,6065 -0,2961
4 a 0,0781 L0L0 4 0,3124 -3,6785 -0,2873
5 n 0,0728 0LL0 4 0,2912 -3,7799 -0,2752
6 i 0,0677 0L00 4 0,2708 -3,8847 -0,2630
7 r 0,0664 LL00 4 0,2656 -3,9127 -0,2598
8 s 0,0646 00LL 4 0,2584 -3,9523 -0,2553
9 h 0,0585 0LLL 4 0,2340 -4,0954 -0,2396
10 d 0,0411 0LLL0 5 0,2055 -4,6047 -0,1893
11 l 0,0360 LLLL0 5 0,1800 -4,7959 -0,1727
12 c 0,0293 0L0LL 5 0,1465 -5,0930 -0,1492
13 f 0,0288 0LLLL 5 0,1440 -5,1178 -0,1474
14 u 0,0277 LLLLL 5 0,1385 -5,1740 -0,1433
15 m 0,0262 00L0L 5 0,1310 -5,2543 -0,1377
16 p 0,0215 0LL0L 5 0,1075 -5,5395 -0,1191
17 y 0,0151 0LL0LL 6 0,0906 -6,0493 -0,0913
18 w 0,0149 LLL0LL 6 0,0894 -6,0685 -0,0904
19 g 0,0139 0L0L0L 6 0,0834 -6,1688 -0,0857
20 b 0,0128 LL0L0L 6 0,0768 -6,2877 -0,0805
21 v 0,0100 0LLL0L 6 0,0600 -6,6439 -0,0664
22 k 0,0042 00LLLL0L 8 0,0336 -7,8954 -0,0332
23 x 0,0030 L0LLLL0L 8 0,0240 -8,3808 -0,0251
24 j 0,0023 0LLLLL0L 8 0,0184 -8,7642 -0,0202
25 q 0,0014 0LLLLLL0L 9 0,0126 -9,4804 -0,0133
26 z 0,0009 LLLLLLL0L 9 0,0081 -10,1178 -0,0091
---------------------------------------------------------------------------------
Summe 1,0000 4,1728 4,1466
Codieraufwand Entropie
Hier ist der mittlere Codieraufwand (= 4,17) etwas größer als die Entropie (= 4,15).
Die Huffman-Codierung liefert immer eine anfangsstückfreie Menge von Codewörtern. Dies sichert die eindeutige Decodierbarkeit einer solchen Codierung. Ein codierter Text wird von links beginnend betrachtet. Das Anfangsstück vom codierten Text, das ein Codewort ist, liefert das ertse Zeichen bei der Decodierung. Da die Codewörter anfangsstückfrei sind, ist dies eindeutig bestimmt. Danach macht man mit dem Rest des codierten Textes analog weiter. Die Huffman-Codierung führt bei normalen Texten der deutschen bzw. englichen Sprache bestenfalls zu einer Halbierung des Speicherbedarfs. Wenn wir Dateien noch effizienter komprimieren (packen) wollen, dann müssen wir eine weitere Bedingung, die wir an die betrachteten Codierungen gestellt haben, aufgeben. Dies wird die Homomorphieeigenschaft sein.
LZW-Kompression wird z.B. verwendet bei UNIX-compress.und beim gif-Grafikformat. Wir machen uns den Algorithmus am bestem anhand eines Beispiels klar.
Beispiel:
Der Text p = abaabacdabaacdabaacd sei gegebengegeben.
Es
gilt length(p) = 20
Damit werden bei der Benutzung des erweiterten ASCII-Codes 20*8 Bit = 160 Bit Speicherplatz benötigt.Lempel, Zif und Welsch haben sich nun folgenden Algorithmus einfallen lassen, um diese Datei zu packen. Es wird bei jedem Codierungsschritt ein Codewort der Länge 9 benutzt. Neben den 256 Codewörtern, die durch den erweiterten ASCII-Code schon belegt sind kommen dann noch weitere, noch nicht belegte 256 Codewörter hinzu. Deren Bedeutung wird im Prozess der Codierung in Abhängikeit des konkreten Textes durch den Algorithmus festgelegt.
Ausgabe |
Eintrag in Codetabelle |
Dargestellt ist im jeweiligen Schritt insgesant: |
Schritt- |
||
Zeichen |
Code |
Zeichen |
Code |
||
a |
97 |
|
|
a |
1 |
b |
98 |
ab |
256 |
ab |
2 |
a |
97 |
ba |
257 |
aba |
3 |
ab |
256 |
aa |
258 |
abaab |
4 |
a |
97 |
aba |
259 |
abaaba |
5 |
c |
99 |
ac |
260 |
abaabac |
6 |
d |
100 |
cd |
261 |
abaabacd |
7 |
aba |
259 |
da |
262 |
abaabacdaba |
8 |
ac |
260 |
abaa |
263 |
abaabacdabaac |
9 |
da |
262 |
acd |
264 |
abaabacdabaacda |
10 |
ba |
257 |
dab |
265 |
abaabacdabaacdaba |
11 |
acd |
264 |
baa |
266 |
abaabacdabaacdabaacd |
12 |
Bei jedem Schritt entsteht ein 9-Bit-Code.
Die Länge würde also durch
die 12 Schritte 12*9 Bit = 108 Bit betragen.
Der Speicherbedarf ist also auf 67,5% reduziert worden.
Der codierte Text in dezimaler Schreibweise:
97 98 97 256 97 99 100 259 260 262 257 264
(Das Beispiel ist an Reichenberg/Pomberger 1997, S. 173, angelehnt.)
Mit der LZW-Codierung lassen sich Kompressionen bis auf 10% realisieren.
Bei normalen Texten allerding nur bis auf ca. 25%.
Definition: Redundanz einer Blockcodierung
Sei X ein Alphabet
und 
eine Blockcodierung mit der einheitlichen Codewortlänge n. Dann nennen wir
Redundanz der Blockcodierung C.
Wenn die Anzahl der Codewörter mit der Anzahl der zu codeirenden Buchstaben übereinstimmt, ist der Quotient 1 und der Logarithmus von 1 ist 0. Es liegt keine Redundanz der Codierung vor.
Beispiel: Erweiterte ASCII-Codierung mit Prüfbit
Wir betrachten die Codierung 
.
Dies ist eine 9 Bit Blockcodierung. In den ersten 8 Bit steht die ASCII-Codierung
des Zeichens und das neute Bit wird so belegt, dass die Gesamtzahl der Einsen
eine gerade Anzahl wird.
Z.B. 
Da die Anzahl der Einsen bereits im ASCII-Code von A eine gerade Anzahl
ergibt, wird das Prüfbit auf 0 gesetzt. 512 (=29) Codewörter
stehen zur Verfügung, 256 werden nur benötigt. Dies ergibt eine Redundanz von:
Definition: Redundanz eines Textes
Sei T ein Text, X das
in T benutzte Alphabet und P das Wahrscheinlichkeitsmaß für
die Buchstaben aus X in dem Text T. Dann nennen wir 
die Redundanz des Textes T.
ist die maximal mögliche Entropie bei |X| Zeichen. Man kann daher
die Formel auch so aufschreiben:
.
Beispiel
Wir betrachten unsere Daten bzgl. der Buchstaben
in englischen Texten (siehe Tabelle 4) und die Berechnung der Entropie im vorigen
Abschnitt. Damit können wir die Redundanz englicher Texte berechnen:
Die Redundanz, die in natürlichen Sprachen steckt, spürt man, wenn man Wörter versucht zu erfassen, bei denen ein oder zwei Zeichen nicht mitgedruckt bzw. nicht lesbar sind. Oft lassen sich die fehlenden Zeichen wegen der Redundanz erahnen.
Redundanzen haben positive und negative Eigenschaften. Betrachten wir noch einmal die erweiterte ASCII-Codierung mit Prüfbit aus dem obigen Beispiel. Die negative Eigenschaft ist der höhere Speicherbedarf - neun Bits gegenüber 8 Bits. Wo steckt nun der Nutzen der Redundanz? Wenn bei einer Übertragung eines solchen Codewortes über einen Kanal ein Bit verändert wird (Null wird zu Eins bzw. Eins wird zu Null), dann merkt der Empfänger des Codewortes dies, da das Prüfbit dann nicht mehr stimmt. Wenn eine Änderung auftritt, wird aus einer geraden Anzahl von Einsen eine ungerade Anzahl! Wenn allerdings genau zwei Änderungen beim Transport auftreten, bemerkt man es am Prüfbit nicht, da dies wieder stimmt.
Hamming hat aus dieser Überlegung heraus ein Distanzmaß für Zeichenreihen definiert.
Definition (Hamming-Distanz)
Seien p und q zwei Wörter aus 
. Dann heißt
Anzahl der Stellen, in denen p und q nicht übereinstimmen
Hamming-Distanz
von p und q.
Beispiele:
h(HAUS;MAUL)=2
h(Regenwasser;Donauwasser)=5
Definition (Hamming-Distanz einer Blockcodierung 
)
= die minimale Hamming-Distanz zwischen zwei verschiedenen Codewörtern von
C
nennen wir Hammingdistanz der Blockcodeirung C.
Beispiel
Die erweiterte ASCII-Codierung mit Prüfbit hat eine
Hamming-Distanz von 2.