Universität Mannheim
Lehrstuhl für Praktische Informatik IV
Prof. Dr. W. Effelsberg
Silvia Pfeiffer
Dr. Stefan Fischer

Multimedia-Systeme: Übungsblatt 1

Übung: 8.5.98

Die Aufgaben, die auf dieser Seite ausgefüllt werden können, werden auch über das Web ausgewertet. Dazu muß die Matrikelnummer eingegeben werden und das Ganze abgeschickt werden. Voraussetzung ist allerdings, daß der Studierende auch für die elektronische Auswertung angemeldet ist.

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:
    Einsparung [%]:
  2. Erstellen Sie nun eine eigene Tabelle ausgehend von den Auftrittswahrscheinlichkeiten in der gegebenen Zeichenkette.
    Kodierung:
    Einsparung [%]:

Aufgabe 2

Beweisen Sie die Aussage: Kein Baum mit den gleiche Häufigkeiten bei den äußeren Knoten hat eine kleinere gewichtete äußere Pfadlänge als der Huffman-Baum.

Aufgabe 3

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:

Aufgabe 4

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:
Wie hoch ist die Einsparung, wenn die vom Algorithmus ausgegebenen Zahlen als Bytes gespeichert werden?
Einsparung [%]:
Wie ist im Vergleich dazu die Leistung der Huffman-Kodierung, wenn alle Buchstaben identische Wahrscheinlichkeiten haben?
Einsparung [%]:

Abgabedaten:

Matrikelnummer: Password:

Universität:
Mannheim
Heidelberg
Freiburg
Karlsruhe
andere

Keine Abgabe mehr!

{ pfeiffer, stefis}@pi4.informatik.uni-mannheim.de
Last modified: Fri May 8 16:08:35 MET DST 1998