wie funktionieren packer?
Von: , Frage gestellt am Mi, 18. Okt 2000
hi,
könnte jmd. grob umschreiben wie packer funktionieren (zip)
danke
3 Antworten zu dieser Frage
-
Antwort von nach 3 Stunden 4 hilfreich
Re: wie funktionieren packer?
Hallo
Grundsätzlich muss zuerst einmal zwischen verlustfreien und verlustbehafteten Komprimierverfahren unterschieden werden.
Für Programme und Daten wie (Text, Tabellen etc.) kommen nur verlustfreie Verfahren in Frage, da ja jedes einzelne Bit erhalten werden muss.
Für Bilder und Musik kommen meist verlustbehaftete Verfahren zum Einsatz da, insbesondere ungeschulte, Augen und Ohren nicht alle Feinheiten welche die Technik unterscheiden kann auch unterscheiden können. z.B. erscheint eine hellgraue Figur auf schwarzem Grund als Weiss, also kann man die Figur gleich weiss statt grau Zeichnen.
Ein einfaches verlustfreies Verfahren besteht darin, dass mehrere aufeinanderfolgende gleiche Zeichen nicht einzeln abgelegt werden sondern nur, einmal das Zeichen und die Anzahl:
statt "AAAAAAA" wird "7A" abgelegt, das spart hier schon mal 5 Zeichen.
Beim Ziff-Lempel Verfahren, die Basis der meisten Packer, wird zuerst eine Liste aller vorkommender Zeichen und deren Anzahl erstellt und danach die Liste nach der Häufigkeit sortiert. Danach werden die Daten neu kodiert, allerdings bitweise. Das Häufigste Zeichen wird mit dem Code "1", das nächste mit "01", dann "001", 0001" usw. ersetzt. Dadurch benötigt das häufigste Zeichen statt 8 Bit nur noch 1 Bit Speicherplatz.
Allerdings muss bei diesem Verfahren die Liste zusammen mit den Daten abgelegt werden, wodurch dann bei ganz kleinen Datenmengen das Resultat mehr Platz braucht als vorher.
MfG Peter(TOO)
-
Antwort von nach einem Tag hilfreich
Re^2: wie funktionieren packer?
Zur Ergänzung:
Bei Bild, Video und Audiodateien werden in der Regel Fourier-
transformationen (zB Cosinustransformation) durchgeführt. Man erhält ein Frequenzspektrum aus dem man nun die nicht hörbaren bzw. nicht sichtbaren Frequenzen entfernt (jpg, mpeg, mp3).
Der populärste Packertyp ist wohl der "Huffman-Code", der ua.
auch bei zip-Archiven benutzt wird. Hier wird auch eine
Häufigkeitsanalyse vorgenommen und auf bestimmte Art und Weise
ein Binärbaum konstruiert, so dass die Blätter des Baumes die
Zeichen darstellen. Der (binäre) Pfad zu diesen Blättern ist
die eigendliche Kodierung. Also je häufiger das Zeichen, desto
kürzer der Pfad. Das Optimale: Die Pfadlänge nimmt mit der Anzahl der Zeichen nur logarithmisch zu.
Gruss Frank
-
-
Antwort von nach 3 Tagen 5 hilfreich
Re: wie funktionieren packer?
Hi Priscal :)))
Man unterscheidet zwischen Daten-Kompression und Daten-Reduktion. Die Kompression ist verlustfrei, die Reduktion dagegen verlustbehaftet.
Daten-Reduktion:
================
Daten-Reduktions-Methoden finden fast ausschließlich bei Bild- und Ton-Dateien eine sinnvolle Anwendung (JPG, MP3). Hierbei werden unwesentliche Informationen einfach ausgelassen. Bei JPG sind es die hohen Ortsfrequenzen, die für die Bildschärfe sorgen, und mittels einer sog. diskreten Cosinus-Transformation ausfindig und danach herausgefiltert werden können. Bei MP3 wird ausgenutzt, dass unser Gehör nach einem bestimmten Ton für kurze Zeit nicht mehr alle Töne, sondern nur noch bestimmte Töne wahrnehmen kann, so dass man die nicht-hörbaren Töne einfach herausfiltert und nicht mehr mit abspeichert. Wenn du dich dafür interessierst, kann ich dir gerne weiter Informationen zukommen lassen, hier würde das zu weit führen.
HUFFMAN-Kompression
===================
Eine viel breitere Anwendung finden jedoch die Daten-Kompressions-Methoden. Lange Zeit glaubte man, mit der sog Huffman-Codierung am Ende angekommen zu sein. Beim Huffman-Verfahren ordnet man den am häufigsten vorkommenden Bytes ein kürzeres Bitmuster zu als den seltener vorkommenden Bytes. Machen wir dazu ein Beispiel:
BILL GATES IST AMERIKANER
Wir zählen zunächst, wie oft jeder Buchstabe vorkommt (die Leerzeichen lassen wir weg):
A B E G I K L M N R S T 3 1 3 1 3 1 2 1 1 2 2 2
Jetzt suchen wir die beiden Buchstaben, die am seltensten vorkommen, etwa B und G, und ordnen ihnen die Bits 0 und 1 zu:
A B E G I K L M N R S T 3 1 3 1 3 1 2 1 1 2 2 2 ----------------------- 0 1
Jetzt fassen wir die beiden Buchstaben B und G zu einem neuen Symbol BG zusammen. Dieses hat dann die Häufigkeit 2. Wir schreiben das so:
A BG E I K L M N R S T 3 2 3 3 1 2 1 1 2 2 2 ---------------------- 01
Jetzt suchen wir wieder die beiden seltensten Zeichen und finden diesmal K und M. Diesen ordnen wir wieder die Bits 0 und 1 zu und fassen sie zu einem neuen Symbol zusammen:
A BG E I KM L N R S T 3 2 3 3 2 2 1 2 2 2 --------------------- 01 01
Jetzt wird es schon interessant. Wir suchen wieder die beiden seltensten und finden BG=2 und N=1. Jetzt haben wir das Problem, dass wir oben schon gesagt haben: B->0 und G->1. Wir müssen aber dem BG nun ein 0-Bit und dem N ein 1-Bit zuordnen. Wir schreiben das 0-Bit bei B und G einfach dadrüber und fassen BG und N zu einer neuen Einheit mit der Häufigkeit 3 zusammen:
A BGN E I KM L R S T 3 3 3 3 2 2 2 2 2 -------------------- 001 01 01
Wir suchen also immer die beiden seltensten Elemente in unserer Tabelle, ordnen ihnen die Bits 0 und 1 zu, und bauen unsere Häufigkeitstabelle um. Ich mache die nächsten Schritte mal schneller:
A BGN E I KML R S T 3 3 3 3 4 2 2 2 ------------------- 001 001 01 01
A BGN E I KML RS T 3 3 3 3 4 4 2 ------------------ 001 001 01 01 01
AT BGN E I KML RS 5 3 3 3 4 4 ----------------- 01 001 001 01 01 01
AT BGNE I KML RS 5 6 3 4 4 ---------------- 01 0001 001 01 001 01 01
AT BGNE IKML RS 5 6 7 4 --------------- 01 0001 0111 01 001 001 01 01
ATRS BGNE IKML 9 6 7 -------------- 0011 0001 0111 0101 001 001 01 01
ATRS BGNEIKML 9 13 ------------- 0011 00001111 0101 00010111 001 001 01 01
ATRSBGNEIKML ------------ 000011111111 001100001111 010100010111 001 001 01 01
So, jetzt sind wir fertig! Anstelle der 8 Bits für ein A (ASCII-Code) schreiben wir jetzt die Bitfolge 000, anstelle eines T's schreiben wir 001, usw (also von oben nach unten). Der obige Satz lautet also Huffman-codiert:
BILL = 1000011011111111
GATES = 10001000001101011
IST = 110011001
AMERIKANER = 00011101101010110111000001001101010
Das sind nur 77 Bits anstatt 22*8=176 Bits!!!
Lempel-Ziv-Kompression
======================
Die Huffman-Codierung hat einen entscheidenden Nachteil. Sie behandelt jedes Byte einzeln. Daher wird z.B. bei ZIP vor der Huffman-Compression noch eine Art Lempel-Ziv-Kompression vorgeschaltet. Hierbei werden Bytefolgen, die sich wiederholen, nur bei ihrem ersten Auftreten gespeichert. Bei jedem weiteren Auftreten, wird lediglich ein Verweis auf dieses erste Auftreten gespeichert und nicht mehr die ganze Zeichenfolge. Von diesem Prinzip gibt es zahlreiche Implementierungen. Die bekanntesten sind: LZ77, LZ78 und LZW (letztere ist patentiert und wird z.B. bei GIF-Dateien verwendet).
ZIP
===
ZIP führt 2 Schritte durch. Zunächst eine kontextsensitive Lempel-Ziv-Kompression und anschließend eine kontextfreie Huffman-Kompression.
So, jetzt bluten mir erstmal die Finger :))) Ich hoffe, ich konnte dir schon helfen. Wenn du genauere Informationen möchtest, schicke mir doch einfach 'ne Mail :)))
cu Stefan.