Robert Sedgewick: Algorithmen

[ Inhaltsverzeichnis ] [ vorhergehende Seite ] [ nächste Seite ] [ Stichwort ]


22. Datenkomprimierung



Übungen

  1. Implementieren Sie Komprimierungs- und Expandierungsprozeduren für die Methode der Lauflängenkodierung für ein im Text beschriebenes feststehendes Alphabet, unter Benutzung von Q als Escape-Zeichen.
  2. Könnte in einer Datei, die mittels der in diesem Kapitel beschriebenen Methode komprimiert worden ist, irgendwo »QQ« auftreten? Könnte »QQQ« auftreten?
  3. Implementieren Sie Komprimierungs- und Expandierungsprozeduren für die im vorliegenden Kapitel beschriebene Methode der Kodierung binärer Dateien.
  4. Der in diesem Kapitel dargestellte Buchstabe »q« kann als eine Folge von mit Hilfe von fünf Bits dargestellten Zeichen verarbeitet werden. Erörtern Sie Für und Wider dieser Vorgehensweise, wenn eine auf Zeichen beruhende Methode der Lauflängenkodierung angewandt werden soll.
  5. Beschreiben Sie den Konstruktionsprozeß, wenn die in diesem Kapitel verwendete Methode benutzt wird, um den Baum für die Huffman-Kodierung für die Zeichenfolge »ABRACADABRA« zu erzeugen. Wie viele Bits erfordert die kodierte Zeichenfolge?
  6. Wie lautet der Huffman-Code für eine binäre Datei? Geben Sie ein Beispiel an, aus dem die maximale Anzahl von Bits ersichtlich ist, die in einem Huffman-Code für eine N Zeichen umfassende ternäre (dreiwertige) Datei verwendet werden könnte.
  7. Angenommen, die Häufigkeiten des Auftretens aller zu verschlüsselnden Zeichen sind unterschiedlich. Ist dann der Baum für die Huffman-Kodierung eindeutig?
  8. Die Huffman-Kodierung könnte auf einfache Weise dahingehend erweitert werden, das eine Kodierung mit aus zwei Bits bestehenden Zeichen erfolgt (unter Benutzung von 4-Weg-Bäumen). Was wäre der Hauptvorteil und was der Hauptnachteil einer solchen Vorgehensweise?
  9. Was würde sich ergeben, wenn man eine mit dem Huffman-Code kodierte Zeichenfolge in mit Hilfe von fünf Bits dargestellte Zeichen zerlegen und dann diese Zeichenfolge einer Huffman-Kodierung unterziehen würde?
  10. Implementieren Sie eine Prozedur für das Dekodieren einer mit dem Huffman-Code kodierten Zeichenfolge, wenn die Felder code und len gegeben sind.


[ Inhaltsverzeichnis ] [ vorhergehende Seite ] [ nächste Seite ] [ Stichwort ]