Was ist das Konzept der Zip-Komprimierung? Ich kann das Konzept des Entfernens von leerem Speicherplatz usw. verstehen, aber vermutlich muss etwas hinzugefügt werden, um zu sagen, wie viel / wo dieser freie Speicherplatz während der Dekompression wieder hinzugefügt werden muss?
Was ist der grundlegende Prozess zum Komprimieren eines Bytestroms?
Ein guter Ausgangspunkt wäre das Huffman Komprimierungsschema. Die Grundidee hinter Huffman ist, dass in einer Datei einige Bytes häufiger vorkommen als andere (in einer Klartextdatei werden viele Bytes überhaupt nicht angezeigt). Geben Sie acht Bits für die Kodierung jedes Bytes ein, warum verwenden Sie nicht eine kürzere Bitsequenz, um die gebräuchlichsten Zeichen zu kodieren, und eine längere Sequenz, um die weniger gebräuchlichen Zeichen zu kodieren (diese Sequenzen werden durch Erstellen eines Huffman-Baums bestimmt).
Wenn Sie diese Bäume zum Codieren / Decodieren von Dateien basierend auf der Zeichenhäufigkeit verwenden, stellen Sie sich vor, dass Sie dann mit der Worthäufigkeit arbeiten - anstatt "sie" als Folge von 4 Zeichen zu codieren, warum nicht? aufgrund seiner Häufigkeit ein einzelnes Zeichen sein, so dass es im Huffman-Baum ein eigenes Blatt erhalten kann. Dies ist mehr oder weniger die Grundlage von ZIP und anderer verlustfreier Komprimierung - sie suchen nach gemeinsamen "Wörtern" (Bytefolgen) in einer Datei (einschließlich Sequenzen von nur 1 Byte, wenn dies genug ist) und verwenden einen Baum, um sie zu codieren. Die ZIP-Datei muss dann nur die Bauminformationen enthalten (eine Kopie jeder Sequenz und die Anzahl, wie oft sie erscheint), damit der Baum rekonstruiert werden kann und der Rest der Datei entschlüsselt werden kann.
Nachverfolgung:
Um die ursprüngliche Frage besser zu beantworten, besteht die Idee hinter der verlustfreien Komprimierung nicht so sehr darin, leeren Speicherplatz zu entfernen, sondern redundent Informationen zu entfernen.
Wenn Sie eine Datenbank zum Speichern von Musiktexten erstellt haben, würden Sie feststellen, dass viel Platz zum Speichern des mehrfach wiederholten Chorus verwendet wurde. Anstatt diesen ganzen Raum zu verwenden, könntest du einfach das Wort CHORUS vor die erste Instanz der Chorus-Zeilen setzen und dann jedes Mal, wenn der Refrain wiederholt werden soll, CHORUS als Platzhalter verwenden (eigentlich ist das die Idee) hinter LZW-Komprimierung - in LZW würde jede Zeile des Liedes eine Nummer davor haben.Wenn eine Zeile später im Lied wiederholt wird, anstatt die ganze Zeile auszugeben, wird nur die Nummer angezeigt.
Das Grundkonzept besteht darin, dass anstelle der Verwendung von acht Bits zur Darstellung jedes Bytes kürzere Darstellungen für häufiger auftretende Bytes oder Sequenzen von Bytes verwendet werden.
Wenn Ihre Datei beispielsweise nur aus dem 16-mal wiederholten Byte 0x41 ( A ) besteht, dann wird sie anstelle der 8-Bit-Sequenz 01000001 auf die 1-Bit-Sequenz 0 gekürzt. Dann kann die Datei durch 0000000000000000 (16 0 s) dargestellt werden. Also kann die Datei des Bytes 0x41 , die 16-mal wiederholt wurde, durch die Datei dargestellt werden, die aus dem Byte 0x00 besteht, das zweimal wiederholt wird.
Was wir hier haben, ist, dass für diese Datei ( 0x41 16-mal wiederholt) die Bits 01000001 keine zusätzlichen Informationen über das Bit 0 übermitteln. In diesem Fall werfen wir die überflüssigen Bits weg, um eine kürzere Darstellung zu erhalten.
Das ist die Kernidee hinter der Komprimierung.
Betrachten Sie als weiteres Beispiel das Acht-Byte-Muster
%Vor%und jetzt wiederhole es 2048 mal. Eine Möglichkeit, dem obigen Ansatz zu folgen, besteht darin, Bytes mit drei Bits darzustellen.
%Vor% Nun können wir das obige Byte-Muster durch 00000101 00111001 01110111 (dies ist das Drei-Byte-Muster 0x05 0x39 0x77 ) wiederholen, das 2048 mal wiederholt wurde.
Aber ein noch besserer Ansatz besteht darin, das Byte-Muster darzustellen
%Vor% durch das einzelne Bit 0 . Dann können wir das obige Bytemuster durch 0 , das 2048 mal wiederholt wird, darstellen, was das Byte 0x00 wird, das 256 Mal wiederholt wird. Jetzt müssen wir nur das Wörterbuch speichern
und das Byte-Muster 0x00 wurden 256 Mal wiederholt und wir komprimierten die Datei von 16.384 Bytes (modulo das Wörterbuch) 256 Bytes.
Kurz gesagt, funktioniert die Komprimierung. Die ganze Sache besteht darin, kurze, effiziente Darstellungen der Bytes und Bytefolgen in einer gegebenen Datei zu finden. Das ist die einfache Idee, aber die Details (die Repräsentation zu finden) können ziemlich herausfordernd sein.
Siehe zum Beispiel:
Das Konzept zwischen Komprimierung ist grundsätzlich statistisch. Wenn Sie eine Reihe von Bytes haben, hängt die Wahrscheinlichkeit, dass das Byte N in der Praxis X ist, von der Wertverteilung der vorherigen Bytes 0..N-1 ab. Ohne Komprimierung ordnen Sie jedem möglichen Wert X 8 Bit zu. Bei der Komprimierung hängt die Menge der für jeden Wert X zugewiesenen Bytes von der geschätzten Wahrscheinlichkeit p (N, X) ab.
Beispielsweise kann ein Komprimierungsalgorithmus bei einer Sequenz "aaaa" einen hohen Wert für p (5, a) und niedrigere Werte für p (5, b) zuweisen. Wenn p (X) hoch ist, ist die Bitfolge, die X zugewiesen ist, kurz, wenn p (X) niedrig ist, wird eine lange Bitfolge verwendet. Wenn auf diese Weise p (N, X) eine gute Schätzung ist, dann ist die durchschnittliche Bitfolge kürzer als 8 Bits.
Tags und Links compression