Multimedia-Systeme: Übungsblatt 1

Aufgabe 1

Kodieren Sie die Zeichenkette PANSADETTA mit dem Huffman-Algorithmus. Sortieren Sie für den Baum die Buchstaben zuerst aufsteigend nach ihrer Wahrscheinlichkeit! Ihre Kodierung sollte jeweils mit 0 beginnen. Geben Sie auch die Einsparung in Prozent an verglichen mit einer 8 Bit Kodierung der Zeichen.

1. Die folgende Tabelle gibt dazu die Wahrscheinlichkeiten für einige Zeichen an.

   Buchstabe	Wahrscheinlichkeit
   E	0.2
   A	0.17
   T	0.11
   N	0.18
   P	0.03
   S	0.19
   D	0.12

   Kodierung: - 0000 0100 1110 0100 0111 0001 0001 010 010 0001 0001 0111 0100 1110 0100 0000 0100 0110 0110 0110 1111 0000 0101 110 110 0101 0000 1111 0110 0110 0110 0100
   Einsparung [%]: - 52,75% 37.75% 61,25% 47,25%
   
   
2. Erstellen Sie nun eine eigene Tabelle ausgehend von den Auftrittswahrscheinlichkeiten in der gegebenen Zeichenkette.
   Kodierung: - 0011 1000 0101 1011 1001 0110 111 0111 1010 0001 1011 1000 0110 111 0111 1010 0001 1010 1010 0110 101 1111 1011 0101 1011 1000 0110 110
   Einsparung [%]: - 66,25% 75.00% 58,00% 80,75%
   
   

Aufgabe 2

Eine Zeichenkette bestehe aus den Buchstaben a, b und c. Welche Zeichenkette wurde komprimiert, wenn die Ziv-Lempel-Kodierung 1 2 3 4 7 3 heißt?

Kodierung: - bacababca abcababac cbaacbbac aacababbc

Aufgabe 3

Betrachten Sie Zeichenketten, die aus dem Alphabet {a, b, c} gebildet werden können. Geben Sie eine Zeichenkette aus 20 Buchstaben aus diesem Alphabet an, für die der Algorithmus von Ziv-Lempel die höchste Kompression erreicht. Beginnen Sie diese mit "a".

Zeichenkette: - abcabcabcabcabcabcab aaaaaaaaaaaaaaaaaaaa

Wie hoch ist die Einsparung, wenn die vom Algorithmus ausgegebenen Zahlen als Bytes gespeichert werden?

Einsparung [%]: - 30% 70% 90% 10%

Wie ist im Vergleich dazu die Leistung der Huffman-Kodierung, wenn alle Buchstaben identische Wahrscheinlichkeiten haben?

Einsparung [%]: - 92,75% 50% 87,5% 81,25%

Abgabedaten:

Universität:
Mannheim
Heidelberg
Freiburg
Karlsruhe
andere