Inhalt
 zurück
|
|
Computerorientierte
Mathematik II
(SS04)
-
1. Programmieraufgabe -
Übersicht
Achtung! Eine ausdruckbare Version dieser Seite findet ihr
hier.
Diese Aufgabe ist bis Donnerstag, 06. Mai 2004
vorzuführen.
An einer Reihe von Beispielen könnt Ihr testen, wie gut eure Kompression ist.
Alle Beispiele befinden sich unter
compression_examples
[examples.zip] .
Ihr müsst 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, dass 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 |
29326 | 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 |
3506 | 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
Kompression eingestellt.
Tip: Ihr könnt Euch den Inhalt einer Datei Byte Weise
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