Inhalt
zurück
|
|
Computerorientierte
Mathematik II
(SS03)
-
3. Programmieraufgabe -
Übersicht
Achtung! Eine ausdruckbare Version dieser Seite findet ihr
hier.
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.)
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.
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 |
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.
|