doppelte Datenkomprimierung
Mark Ise
ich wei� nicht, ob ich hier richtig bin, und wo ich sonst fragen soll.
Wenn man Daten mit einem Komprimierungsprogramm zuerst mit schwacher
Einstellung komprimiert, und danach nochmal mit starker Einstellung,
wieso wird das Archiv dann wesentlich gr��er, als wenn man die Dateien
gleich mit starker Komprimierung komprimiert?
Als Beispiel habe ich einen Ordner mit Word-Dokumenten komprimiert.
Ich habe es immer mit Standardeinstellungen mit 7z und Winrar komprimiert.
Unkomprimiert sind ist das Verzeichnis 10 MB gro�.
Winrar erstellt eine Archiv mit 3,6 MB Gr��e.
Das Archiv von 7z ist 2,8 MB gro�.
Wenn ich das Winrar-Archiv nochmal mit 7z packe, wird es 3,8 MB gro�.
Das RAR-Archiv sollte eine enorme Redundanz beinhalten.
Warum kann 7z die nicht nutzen?
--
Mark
David Wührer
> Wenn man Daten mit einem Komprimierungsprogramm zuerst mit schwacher
> Einstellung komprimiert, und danach nochmal mit starker Einstellung,
> wieso wird das Archiv dann wesentlich größer, als wenn man die Dateien
> gleich mit starker Komprimierung komprimiert?
Komprimierte Daten sehen immer wie weißes Rauschen aus.
Grund: Daten werden als Signal betrachtet, das sich wiederholende Muster
aufweist. Diese Muster werden zusammengefasst und durch andere Symbole
ersetzt. (Einfaches Beispiel: Wenn ein Zeichen sich mehrmals wiederholt,
genügt es zu sagen, welches Zeichen sich wie oft wiederholt. Wenn das
regelmäßig vorkommt, kann man das natürlich auch zusammenfassen. (Das ist
nicht, was 7z macht.))
Bei WinRAR kannst du einstellen, wie groß die Blöcke sind, die es
bearbeitet. Je größer die Blöcke, desto effizienter packt es, braucht dafür
aber deutlich mehr Speicher und Zeit. Aber auch bei kleinen Blöcken sieht
das Signal danach wie Rauschen aus.
Und einen zufälligen oder zufällig wirkenden Datenstrom kann man nicht
komprimieren, ohne Daten zu verlieren.
Ein Packer packt zudem Meta-Informationen dazu. Wenn ein Packer feststellt,
dass er die Daten nicht kleiner machen kann, sollte er sie lassen, wie sie
sind, aber die Meta-Daten muss er trotzdem hinzufügen (zum Beispiel den
Dateinamen und das Datum der ursprünglichen Datei). 200Kb kommt mir aber
trotzdem viel vor. Ich vermute, dass 7z die Daten ersetzt, ohne darauf zu
achten, ob sie dadurch mehr werden.
Christian
>
> Das RAR-Archiv sollte eine enorme Redundanz beinhalten.
> Warum kann 7z die nicht nutzen?
>
Nur weil ein Kompressions alg eine Eingabe nicht so gut Komprimiert wie
ein anderer, bedeutet das nicht das seine Ausgabe nicht (sehr) zuf�llig ist.
und Kompression von einem sehr zuf�lligen Datenstrom wird auf zus�tzlich
ben�tigter Platz hinauslaufen.
Gru�
Christian
Roland Damm
Christian schrub:
> Mark Ise schrieb:
>>
>> Das RAR-Archiv sollte eine enorme Redundanz beinhalten.
>> Warum kann 7z die nicht nutzen?
>>
>
> Nur weil ein Kompressions alg eine Eingabe nicht so gut
> Komprimiert wie ein anderer, bedeutet das nicht das seine
> Ausgabe nicht (sehr) zufällig ist.
>
> und Kompression von einem sehr zufälligen Datenstrom wird auf
> zusätzlich benötigter Platz hinauslaufen.
Währe die Frage, ob es eine berechenbare Untergrenze für die
Größe der Komprimierten Datei gibt. Und ob es einen Algorithmus
gibt, der diese Grenze erreichen kann. Der müsste ja dann auch
mäßig komprimierte Dateien weiter bis zu dieser Grenze
komprimieren können (natürlich zuzüglich Overhead).
Es könnte eben nur leider sein, dass so ein idealer Komprimierer
unpraktisch langsam währe....
CU Rollo
Christian
Natürlich könnte man einen Komprimierer basteln der komprimierte Dateien
erst mal mit Bekannten algs Dekomprimiert... und dann erst komprimiert...
Interessantererweise haben haben die Komprimierer noch eine andere
Anforderung... Von den meisten ist gefordert das sie als Stream arbeiten
.. also nicht random access auf die Datei haben und dann entscheiden wie
sie komprimieren (Online - Algorithmus vs Offline Algorithmus dürfte das
treffen) was eine perfekte komprimierung verhindern dürfte..
Gruß
Christian
Thomas Rauch
> Das RAR-Archiv sollte eine enorme Redundanz beinhalten.
> Warum kann 7z die nicht nutzen?
Redundant im Sinne von "Wiederherstellungsinformationen" im Rar-Archiv?
Dann ist es ja klar dass hier Informationen mehrfach vorhanden sind -
also tats�chlich Informationen hinzu kommen. Die k�nnen nat�rlich nicht
einfach wegkomprimiert werden.
--
Gru�, Thomas
Roland Damm
Christian schrub:
> Interessantererweise haben haben die Komprimierer noch eine
> andere Anforderung... Von den meisten ist gefordert das sie als
> Stream arbeiten .. also nicht random access auf die Datei haben
> und dann entscheiden wie sie komprimieren (Online - Algorithmus
> vs Offline Algorithmus dürfte das
> treffen)
Jeder Stream hat seinen Buffer, das würde ich nicht als
entscheidendes Argument sehen.
> was eine perfekte komprimierung verhindern dürfte..
Die endliche Größe des Buffers dürfte das verhindern.
CU Rollo
Sweetpitti
> Hallo,
>
> ich weiß nicht, ob ich hier richtig bin, und wo ich sonst fragen soll.
>
> Wenn man Daten mit einem Komprimierungsprogramm zuerst mit schwacher
> Einstellung komprimiert, und danach nochmal mit starker Einstellung,
> gleich mit starker Komprimierung komprimiert?
>
> Als Beispiel habe ich einen Ordner mit Word-Dokumenten komprimiert.
>
> Ich habe es immer mit Standardeinstellungen mit 7z und Winrar komprimiert.
>
>
> Winrar erstellt eine Archiv mit 3,6 MB Größe.
> Das Archiv von 7z ist 2,8 MB groß.
>
> Wenn ich das Winrar-Archiv nochmal mit 7z packe, wird es 3,8 MB groß.
>
> Das RAR-Archiv sollte eine enorme Redundanz beinhalten.
> Warum kann 7z die nicht nutzen?
>
> --
> Mark
Hi Mark,
der Grund dafür ist recht einfach und banal.
Die Datei muss immer größer werden, da sich Information nicht
unendlich stark komprimieren lässt (das besagt schon die
Informationstheorie) und Programme ja auch noch ihre Header-
Informationen hinzufügen. Denn jedes Zeichen eines Zeichensatzes
(z.B.: ASCII, ISO-8859-1) taucht in einer Nachricht (z.B. Datei,
Audiosignal usw.) mit einer entsprechenden Wahrscheinlichkeit auf. So
ist beispielsweise der Buchstabe x viel seltener in einem Buch
anzutreffen, als der Buchstabe e.
Das ist nun der Punkt wo die Informationstheorie ins Spiel kommt, denn
diese besagt: je seltener ein Zeichen vorkommt, um so wichtiger ist
dessen Informationsgehalt.
Der Informationsgehalt eines Zeichens hat was mit seiner
Auftrittswahrscheinlichkeit zu tun.
Dazu ein Beispiel:
Wir nehmen an: Wir haben eine Nachricht aus 1000 Zeichen eines
Zeichensatzes. Der Zeichensatz ∑ = {0,1} besteht nur aus den Symbolen
0 und 1 - d.h. die Nachricht ist ein binärer Datenstrom.
Ferner haben wir ermittelt, wie groß die Auftrittswahrscheinlichkeit
(p) der einzelnen Symbole 0 (p0 = 0,9) und 1 (p1=0,1) ist.
Mit diesem Wissen, können wir den Informationsgehalt (H) der beiden
Zeichen und letztendlich der Nachricht berechnen.
H = ln(p0) / ln(2) * -p0 + ln(p1) / ln(2) * -p1 = .
46899559358928122123
Was haben wir nun hier berechnet? Den mittleren Informationsgehalt
eines Zeichens und können nun die optimale Länge der Nachricht (L),
durch Multiplikation des "mittleren Informationsgehalts eines
Zeichens" (H) mit der Anzahl an Zeichen in der Nachricht, berechnen.
L = H * n, mit n = 1000 (Anzahl an Zeichen in der Nachricht) und H = .
46899559358928122123 (mittlerer Informationsgehalt eines Zeichens in
Bit).
L = H * n = 468.99559358928122123
Nun, es fällt natürlich an dieser Stelle auf, das die Nachricht
optimal durch 469 anstatt durch 1000 Zeichen kodiert werden könnte.
Nur hat die Sache einen Haken, denn ein Programm zur Dekodierung der
Nachricht brauch noch Kenntnis der Auftrittswahrscheinlichkeit der
einzelnen Zeichen innerhalb der Nachricht... ;-)
Daher hat dein beschriebenes Problem den folgenden Grund:
1. Es erfolgte bei der ersten Kodierung eine Änderung der
Auftrittswahrscheinlichkeiten (pi), da bereits eine Kompression
durchgeführt wurde.
2. Die neuen Auftrittswahrscheinlichkeiten der einzelnen Zeichen,
konnte mit dem entsprechenden Algorithmus nicht besser komprimiert
werden und es mussten weitere Informationen zur Datei hinzugefügt
werden, um deren korrekte Dekodierung gewährleisten zu können.