Wir stellen Euch 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:
~co2-001/compression_examples
. 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 | Olafs 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
Olaf
Jahn Last modified: Wed Apr 28 15:21:41 MET
DST 1999