CoMa

Computerorientierte Mathematik

TU logo

Inhalt
.

Institut
 .  Vorlesungen
 .  .  CoMa
 .  .  .  ehemalige Zyklen
 .  .  .  .  CoMaII SS03
 .  .  .  .  .  Literatur
 .  .  .  .  .  Programmierregeln
 .  .  .  .  .  Mailarchiv
 .  .  .  .  . Programm 3
 .  .  .  .  .  Programm 6

back zurück

Computerorientierte Mathematik II (SS03)
- 3. Programmieraufgabe -


Übersicht

Achtung! Eine ausdruckbare Version dieser Seite findet ihr hier.

Abgabetermin

Diese Aufgabe ist bis Montag, 26.Mai 2002 vorzuführen.


Hier findet Ihr ein paar Dinge, die Ihr vielleicht hilfreich für Euer Programm finden werdet. Einerseits stellen wir Euch zwei komplette Klassen und ein paar Programmfragmente, andererseits haben wir ein paar Beispiele gesammelt. Alles, was Ihr hier findet, ist ein Service für Euch, Ihr müßt es nicht verwenden (obwohl es sehr ratsam ist, an den Beispielen auch Euer Programm zu testen.)

Programmteile

Wir stellen Euch (wiedrum in einem package comaio) Klassen BitInputFile und BitOutputFile zum Lesen und Schreiben von Dateien, die Bitfelder enthalten. Es sei Euch dringend geraten, diese Klassen zu verwenden, einfach deshalb, weil wir Euch noch nichts über Bitarithmetik (die Ihr sonst bräuchtet) erzählt haben.

Ansonsten gibt es noch ein paar unvollständige Klassen, die Ihr als Anhaltspunkt dafür nehmen könnt, was in solch eine Klasse rein könnte bzw. sollte:

  • WeightedTree.java Dies ist die Klasse für die Huffman-Bäume. Die Baum-Knoten können neben einem Datenelement auch das Gewicht des Teilbaums speichern. Es sind (fast) nur noch die geeigneten Konstruktoren zu implementieren.
  • BTLeafIteratorWrapper.java Im Huffman Baum stehen nur in Blättern Daten. Dieser IteratorWrapper nimmt einen BinTreeIterator und hält ihn nur an den Blättern an. Den habt ihr in der zweiten Programmieraufgabe geschrieben.
  • BTRootPathIterator.java Von einem Blatt aus will man den Pfad zur Wurzel des Baumes verfolgen. Benutzt dazu doch diesen Iterator aus der zweiten Programmieraufgabe! Wenn man hoch wandert merkt man sich die Richtungen - links - rechts - rechts - links - ... - in einem Stack. Falls man mal zurückwandern will, weiss man so, wohin es gehen soll. Vielleicht fügt ihr noch eine Methode hinzu, um sich den Stack geben zu lassen (ge-cloned()!!!). Dann habt ihr schon die Codierung eines Blattes!
  • CodeTable.java Dieser könnte ein Array von Listen enthalten, in denen die Kodierungen der Zeichen zum schnellen Zugriff zwischengespeichert werden.
  • Compressor.java Das ist das eigentliche Kompressionsprogramm.
  • Decompressor.java Das Gegenstück zum Kompressionsprogramm: ein Dekompressor.

Beispiele

An einer Reihe von Beispielen könnt Ihr testen, wie gut eure Kompression ist. All Beispiele befinden sich unter ~co2-001/compression_examples [.tar.gz] [.zip] . Ihr müßt sie nicht zu Euch kopieren, sondern könnt einfach direkt auf sie zugreifen.

In der folgenden Tabelle findet Ihr eine Übersicht über die Beispiele mit Länge der Originaldatei, der Länge erreicht durch eine eigene Implementation des Huffman-Verfahrens und zum Vergleich die Länge, die ein paar bekannte Komprimierungsprogramme erzielen (die nicht (nur) auf Huffman-Codes basieren).

Anmerkung: Es ist normal, daß die Längen, die Ihr erreicht, leicht von der hier angegebenen (Spalte 4) abweichen. Das liegt dann an unterschiedlicher Weise, in der Ihr Information über Euren Code abspeichert. Die Länge der eigentlichen komprimierten Daten (also ohne die Codeinformation in der Datei) sollte gleich sein, da der Huffman-Code bei Euch und uns ja einen optimaler präfixfreier Code ist.

Wir haben den Beispielen Namen gegeben, die anzeigen, wie gut sie sich komprimieren lassen. In der Tat gibt es Dateien, die in komprimierter Form sogar länger sind als unkomprimiert (Warum?).

Länge (in Bytes) erreicht durch
NameOriginallängeuntersch. Bytesunsere Huffman-Implementation compresszip gzipbzip2
bad1201911256 198718240797169388169308169257
bad227819256 2932440355278682778828245
bad3112 19101062638
bad416667256 1821024548167671669217132
bad54664188 47393074259225122607
good11659181 99637851609360135587
good24194295 2668920347152121513213735
good37530684 4629744955399283984835971
good447152092 22033685939202672018717907
good5927418 40634120342433443274
mediocre125610 174791153557
mediocre2903886 64994379246723872630
mediocre3346978 26002194188618061852
mediocre4467778 35043365258025002671
mediocre52294170 1776321643175391745917580
verybad1256256 1797291356281425
verygood1172178465 45997421197117964317956391894
verygood210011 137541113145
verygood310012 143741123243
veryverybad111 1251012337

Die zum Vergleich herangezogenen Komprimierungsprogramme wurden jeweils zum "Komprimieren" gezwungen, auch wenn sie es eigentlich nicht wollten, weil die Datei länger wird. Wo die Wahl bestand, wurde beste Komprimierung eingestellt.

Tip: Ihr könnt Euch den Inhalt einer Datei byteweise ansehen mit

od -vt u1 Dateiname.

Die erste Spalte ist dabei nur ein Zähler für die Bytes, die anderen Spalten sind die Werte der Bytes im Dezimalsystem.

top top
zuletzt bearbeitet: Tue May 13 2003, zuletzt erstellt: Tue Sep 8 2009
Andreas Fest <fest@math.tu-berlin.de>
Validate HTML