Computerorientierte Mathematik

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 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:

Beispiele

An einer Reihe von Beispielen könnt Ihr testen, wie gut Eurer Kompression ist. All Beispiele befinden sich unter ~co2-002/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 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.

top

zuletzt bearbeitet: Mon Aug 6 2001, zuletzt erstellt: Wed Sep 29 2004

Andreas Fest <fest@math.tu-berlin.de>