COMA II: 2. Programmieraufgabe

Computerorientierte Mathematik II (SS05)
- 2. Programmieraufgabe -

Übersicht

Abgabetermin
Beispiele

Abgabetermin

Diese Aufgabe ist bis Montag, 09. Mai 2005 vorzuführen.

Beispiele

An einer Reihe von Beispielen könnt Ihr testen, wie gut eure Kompression ist. All Beispiele befinden sich hier: examples.zip.

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.

zuletzt bearbeitet: Sat April 10 2004, zuletzt erstellt: Sat April 10 2004

Martin Oellrich <oellrich@math.tu-berlin.de>