Inhalt

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.
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.)
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] .
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 |
Name | Originallänge | untersch. Bytes | unsere Huffman-Implementation |
compress | zip |
gzip | bzip2 |
bad1 | 201911 | 256 |
198718 | 240797 | 169388 | 169308 | 169257 |
bad2 | 27819 | 256 |
29324 | 40355 | 27868 | 27788 | 28245 |
bad3 | 11 | 2 |
19 | 10 | 106 | 26 | 38 |
bad4 | 16667 | 256 |
18210 | 24548 | 16767 | 16692 | 17132 |
bad5 | 4664 | 188 |
4739 | 3074 | 2592 | 2512 | 2607 |
good1 | 16591 | 81 |
9963 | 7851 | 6093 | 6013 | 5587 |
good2 | 41942 | 95 |
26689 | 20347 | 15212 | 15132 | 13735 |
good3 | 75306 | 84 |
46297 | 44955 | 39928 | 39848 | 35971 |
good4 | 471520 | 92 |
220336 | 85939 | 20267 | 20187 | 17907 |
good5 | 9274 | 18 |
4063 | 4120 | 3424 | 3344 | 3274 |
mediocre1 | 256 | 10 |
174 | 79 | 115 | 35 | 57 |
mediocre2 | 9038 | 86 |
6499 | 4379 | 2467 | 2387 | 2630 |
mediocre3 | 3469 | 78 |
2600 | 2194 | 1886 | 1806 | 1852 |
mediocre4 | 4677 | 78 |
3504 | 3365 | 2580 | 2500 | 2671 |
mediocre5 | 22941 | 70 |
17763 | 21643 | 17539 | 17459 | 17580 |
verybad1 | 256 | 256 |
1797 | 291 | 356 | 281 | 425 |
verygood1 | 1721784 | 65 |
459974 | 211971 | 179643 | 179563 | 91894 |
verygood2 | 1001 | 1 |
137 | 54 | 111 | 31 | 45 |
verygood3 | 1001 | 2 |
143 | 74 | 112 | 32 | 43 |
veryverybad1 | 1 | 1 |
12 | 5 | 101 | 23 | 37 |
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.
|