nicht angemeldet
Komprimierverfahren
Hallo Forumsgemeinde:
Ich hätte da einmal eine Frage:
Wie funktioniert das Verfahren der Datenkomprimierung genau (.zip,.rar,.tar....). Ich weis zwar ca. wie das abläuft aber eben nicht genau.
Bin für jeden Antwort Dankbar:
Martin Sch.
-
Halihallo Martin
Ich hätte da einmal eine Frage:
Wie funktioniert das Verfahren der Datenkomprimierung genau (.zip,.rar,.tar....). Ich weis zwar ca. wie das abläuft aber eben nicht genau.
Es basieren alle auf eine Verknüpfung eines Lempel-Ziv und Hoffmann-Algorithmus. Der Hoffman-Algorithmus weist jedem ASCII-Zeichen einen möglichst kurzen Code zu. Alle ASCII-Zeichen haben eine konstante Länge von 8bit, warum soll aber ein Zeichen, welches nur einaml vorkommt genauso gross sein, wie ein Zeichen, welches oft vorkommt? - Das ist Platzverbrauch. Es geht beim Hoffman darum ein Zeichen möglichst klein abbzubilden, d. h. ein Zeichen, welches am meisten vorkommt, wird möglichst klein Codiert, ein Zeichen, welches fast nie vokommt wird gross Codiert.
Lempel-Ziv: Hier gibt's mehrere Typen. Dictionary-Methode: Oft vorkommende Zeichenfolgen werden in einem Dictionary aufgezeichnet. Alle Zeichenfolgen, welche einen Eintrag im Dictionary haben, werden nicht durch die Zeichenfolge selber, sondern durch einen Pointer auf den entsprechenden Eintrag im Dictionary ersetzt (der Pointer ist viel kleiner, als die Zeichenfolge selber => Kompression). Eine andere Methode ist es, wenn eine Zeichenfolge das zweite mal vorkommt, diese durch einen Pointer (Position und Länge) zu ersetzen, welcher die erste äquivalente Zeichenfolge referenziert.Philipp grüsst Philipp.
das zweite 'Philipp' ist redundant, da es durch einen Pointer (16,7) ersetzt werden kann (also 16 Zeichen zurück und dann 7 Zeichen).
Viele Grüsse
Philipp
-
Hallo Philipp
Es basieren alle auf eine Verknüpfung eines Lempel-Ziv und Hoffmann-Algorithmus.
Heißt der gute Mann nicht Huffman?
Gruß, Jan
-
Halihallo Jan
Es basieren alle auf eine Verknüpfung eines Lempel-Ziv und Hoffmann-Algorithmus.
Heißt der gute Mann nicht Huffman?
Ja ;)
zu Martin:
Ich sagte _alle_, das ist natürlich falsch. Zwar gilt dies für (fast) alle zip, rar, ... Archive, jedoch sind die vorgestellten Algorithmus völlig unvollständig. Es gibt tausende von Algorithmen, jeder hat einen gewissen "Anwendungsbereich", wo er optimale Kompression erreicht. Kleine Auszüge:
GIF => eigentlich nix anderes als Lempel-Ziv
JPEG => Diskrete Cosinus Transformation
dann gibt's da noch WaveLet-Kompression, RLE (Run Length Encoding), Fraktale Bildkompression, MP-Kompression (Sound), ...War die Beschreibung im ersten Posting ausrechend, oder möchtest du noch etwas mehr ins Detail gehen?
Viele Grüsse
Philipp
-
Hallo!
!Danke!
Jetzt versteh ich die Komprimierung zum ersten mal wirklich!
Martin
-
Moin!
Ich sagte _alle_, das ist natürlich falsch. Zwar gilt dies für (fast) alle zip, rar, ... Archive, jedoch sind die vorgestellten Algorithmus völlig unvollständig. Es gibt tausende von Algorithmen, jeder hat einen gewissen "Anwendungsbereich", wo er optimale Kompression erreicht. Kleine Auszüge:
GIF => eigentlich nix anderes als Lempel-Ziv
JPEG => Diskrete Cosinus TransformationSorry, wenn ich dich korrigieren muß, aber das wirklich komprimierende an JPEG ist nicht die DCT, sondern RLE.
Mit DCT werden (im Fall von JPEG 8x8 Pixel große) Bildblöcke von der Pixeldarstellung in Ortsfrequenzen gewandelt und als Frequenzspektrum betrachtet. Wie hat man sich Ortsfrequenzen vorzustellen? Was eine Frequenz ist, sollte klar sein: Eine Schwingung. Wenn man nun ein Bild hat, dann hat eine einzelne Pixelzeile hintereinander folgend jeweils eine unterschiedliche Helligkeit. Malt man sich den Helligkeitsverlauf als Kurve auf ein Blatt Papier, sieht man die Ortsfrequenz. :)
Mit der DCT wird der zweidimensionale Pixelblock in einen zweidimensionalen Ortsfrequenskomponentenblock überführt. Außerdem werden gewisse hohe Frequenzen je nach Kompressionsgrad mehr oder weniger unterdrückt, indem man die Frequenzanteile durch einen gewissen Faktor größer 1 dividiert (bei der Dekodierung wird mit diesem Faktor multipliziert, um es rückgängig zu machen). Durch die Division entstehen vor allem bei den hohen Frequenzanteilen viele Werte kleiner als 1 bzw. fast 0 - die werden dann auf 0 gerundet. Und da sich viele Nullen wunderbar mit RLE komprimieren lassen, ist JPEG so schön klein.
Ok, der Verlust bei JPEG besteht in der Rundung, die Komprimierung aber ist die verlustfreie RLE. Der schlaue Trick bei JPEG ist eben, durch geschickte Transformation aus einem schwer komprimierbaren Bild möglichst ein leicht komprimierbares zu machen. Mit der DCT gelingt das, weil auch bei sehr verschiedenen Pixeln in einem Block nicht immer alle Frequenzen ausgenutzt werden oder nur sehr geringen Einfluß haben.
- Sven Rautenberg
--
Diese Signatur gilt nur am Freitag.
-
-
-
HAllo Philipp!
Danke für diese Erklärung, jetzt sind einige Unklarheiten geklärt.
Martin
Kennst du vieleicht einen Link oder so:
Denn ich würde es gerne ganz genau wissen wie das Bit für Bit abläuft.
-
Hi Martin,
Danke für diese Erklärung, jetzt sind einige Unklarheiten geklärt.
Denn ich würde es gerne ganz genau wissen wie das Bit für Bit abläuft.z.B. http://wwwbrauer.in.tum.de/seminare/web/WS0001/vortrag06.html
oder auch http://www.educeth.ch/informatik/interaktiv/kompression/huffman.htmlhab ich selber nicht gelesen, sieht aber aufschlussreich aus.
viele Grüße
Achim Schrepfer -
Halihallo Martin
Kennst du vieleicht einen Link oder so:
Ich war auf der Suche nach meiner alten Maturaarbeit (wenn man das "Gymnasium" abschliessen wollte, brauchte man das bei uns). Ich wählte das Thema "Datenkompression". Leider wurde ich nicht mehr fündig. Aber Links brauche ich hier nicht zu Posten, gib einfach Lempel-Ziv, Huffmann oder "LZ Compression" in google ein und du wirst etwa 5 Mt. mit
^^^ ;)
Lesen beschäftigt sein.Denn ich würde es gerne ganz genau wissen wie das Bit für Bit abläuft.
Der Eingabestrom läuft immer noch Byteweise, die Ausgabe jedoch nicht mehr, nur so kurz angemerkt.
Viele Grüsse
Philipp
-
Moin!
Kennst du vieleicht einen Link oder so:
Denn ich würde es gerne ganz genau wissen wie das Bit für Bit abläuft.
Datenkompression läuft üblicherweise durch Reduzierung der Redundanz ab.
Ein Beispiel:
Du hast die vier Symbole A, B, C und D. Diese vier Symbole kann man binär recht simpel so darstellen:
A = 00
B = 01
C = 10
D = 11Mit dieser Methode kann man dann beliebige Symbolabfolgen speichern.
Wenn nun aber das Symbol A wesentlich häufiger vorkommt, als die anderen Symbole, dann ist es Verschwendung, ganze zwei Bit für dieses Symbol aufzuwenden.
Angenommen, die Symbolhäufigkeit der Symbole liegt so verteilt:
A = 50%
B = 25%
C = 20%
D = 5%Dann läßt sich eine Kodierung finden, die letztendlich kürzer ist:
A = 0
B = 10
C = 110
D = 111Vergleich: Wenn du die Symbolfolge DCCCCBBBBBAAAAAAAAAA (das sind 20 Symbole mit exakt der angegebenen Häufigkeit) hast, wird gemäß der 2-Bit-Codierung die entstehende Bitfolge 40 Bit lang sein.
Mit der angepaßten Codierung sparst du:
10x A = 10 Bit
5x B = 10 Bit
5x C+D = 15 Bit
Summe = 35 Bit = 5 Bit oder 12,5% Datenmenge weniger.Du darfst das ganze gerne mal für 256 ASCII-Zeichen durchprobieren.
Das ist nur ein Beispiel (und dürfte IIRC unter "Quellencodierung" laufen). Weitere Möglichkeiten bestehen natürlich, wenn man die Regelmäßigkeit der Zeichenabfolge berücksichtigt.
Im Beispielstring kommen die Buchstabenfolge A hintereinander relativ häufig vor. Wenn man das ausnutzen könnte...
Das Zeichen D ist am seltensten. Deshalb wird es zum Sonderzeichen erklärt, um eine Komprimierungssequenz einzuleiten. Wenn ein D vorkommt, folgt als nächstes Zeichen das komprimierte Zeichen, und als nächstes Zeichen die Anzahl der komprimierten Zeichen - dazu wird dann der Binärcode des Zeichens genommen (siehe erste Codiertabelle). Auf diese Weise kann man Null bis drei Zeichen zusammenfassen. Null Zeichen macht keinen Sinn, also sollte noch 1 addiert werden, um von 1 bis 4 Zeichen zusammenzufassen.
Aus
DCCCCBBBBBAAAAAAAAAA
wird
DDADCDDBDDBADADDADDAB
1xD4xC4xB1xB4xA4xA2xAIrgendwie nicht so erfolgreich - die Zeichenfolge wird länger. Das liegt daran, dass maximal vier Zeichen leider nur in drei Zeichen komprimiert werden können.
Eine andere Strategie: Hinter jedem echten Zeichen kommt die Anzahl seiner Wiederholungen (a = 1x, d= 4x, die Kleinbuchstaben nur zur Unterscheidung)
DaCdBdBaAdAdAb
statt
DCCCCBBBBBAAAAAAAAAA
Immerhin 6 Zeichen gespart, weil so viele Zeichen mindestens doppelt vorkommen.Du siehst: Je nach Datenmaterial kann bzw. muß man eine unterschiedliche Strategie benutzen und unter Umständen die Art der Codierung anpassen, um optimale Ergebnisse zu erhalten.
Unter Linux weit verbreitet ist z.B. gzip, was im Grunde nichts anderes als der bekannte ZIP-Mechanismus ist. Außerdem gibt es bzip2, welches wesentlich bessere Komprimierungsraten erzielt. Der Grund ist, dass bzip2 einfach einen anderen Ansatz zur Komprimierung gewählt hat (in irgendeiner c't war der Algorithmus mal beschrieben: Die Datenbytes werden in ein Array geschrieben, jeder Eintrag mit einem anderen Startoffset. Dieses Array wird dann sortiert und irgendwie komprimiert. Die spannende Frage: Wenn 1 Megabyte an Daten zu komprimieren ist, müssen alle Offsets dieses 1-Megabyte-Strings in einem Array sortiert werden. 1 Megabyte Daten mal 1 Megabyte an Offsets ist aber 1 Terabyte an Daten - das läßt sich ohne Tricks unmöglich sortieren), der offensichtlich erfolgreicher allgemeine Daten komprimiert. Von den ganzen Spezialverfahren für verlustbehaftete Komprimierung (MP3, Ogg Vorbis, RealAudio, ...) mal ganz zu schweigen.
- Sven Rautenberg
--
Diese Signatur gilt nur am Freitag.
-
-