CoMa

Computerorientierte Mathematik

TU logo

Inhalt
.

Institut
 .  Vorlesungen
 .  .  CoMa
 .  .  .  ehemalige Zyklen
 .  .  .  .  CoMaII SS02
 .  .  .  .  .  Literatur
 .  .  .  .  .  Programmierregeln
 .  .  .  .  .  Mailarchiv
 .  .  .  .  .  Programm 1&2
 .  .  .  .  . Programm 3
 .  .  .  .  .  Programm 7

back zurück

Computerorientierte Mathematik II (WS00/01)
- 3. Programmieraufgabe -

Version Stand 15. Mai 2002. Änderungen gegenüber älteren Versionen sind rot gekennzeichnet.


Übersicht

Achtung! Eine ausdruckbare Version dieser Seite findet ihr hier.

Abgabetermin

Diese Aufgabe ist bis Montag, 27.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.

Diese beiden Klassen sind Teil eines neuen Packages. [ccc.tar.gz] [ccc.zip]

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:

  • PriorityQueue.java Ihr braucht nur die Heap-relevanten Teile mit Leben füllen, das ccc-Interface ist schon implementiert, inclusive einem Iterator als innere Klasse. Beginnt mit dieser Klasse, ihr könnt sie mit der ContainerApplication oder ihrer main-Methode testen!
  • WeightedTree.java Diese Klasse hat einige (unnütze) Methoden verloren. 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. Ihr müsstet jedoch noch increment() und decrement() implementieren!!
  • BTRootPathIterator.java Von einem Blatt aus will man den Pfad zur Wurzel des Baumes verfolgen. Benutzt dazu doch diesen Iterator! Wenn man hoch wandert (increment, bitte implementieren!) merkt man sich am besten die Richtungen - links - rechts - rechts - links - ... - in einem Stack (hier schummeln wir und nehmen den Java-Stack). Falls man mal zurückwandern (decremen, na wer soll das wohl schreiben?) 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!

    Die Beiden Iteratoren kann man auch sehr gut in der ContainerApplication mit dem ccc.bintree.RandomTree testen!

    Die Klassen WeightedTree, BTLeafIterator und BTRootPathIterator benötigen genauere Kenntnis über das "Innenleben" des BinTree, insbesondere über Baumknoten. Deshalb müssen diese Klassen zu einem Teil des Packages ccc.bintree erklärt werden. Um dies zu erreichen, speichert ihr die entsprechenden Dateien in einem eigenen Unterverzeichnis eures Programm-Verzeichnis, z.B. in ~/programs/program3/bintree/ und übersetzt dann die drei Dateien (und nur diese) in dem Verzeichnis mit folgendem Aufruf:

    javac -d ~/classes ~/programs/program3/bintree/*.java

    Alle anderen Dateien übersetzt ihr wie gewohnt.
  • CodeTable.java
  • Compressor.java
  • Decompressor.java
Alle zum Download: [.tar.gz] [.zip] .

Beispiele

An einer Reihe von Beispielen könnt Ihr testen, wie gut Eurer Kompression ist. All Beispiele befinden sich unter ~co2-002/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: Thu May 16 2002, zuletzt erstellt: Tue Sep 8 2009
Andreas Fest <fest@math.tu-berlin.de>
Validate HTML