IT-Academy Logo
Sign Up Login Help
Home - Programmieren - Codierungen - Datenkompression



Datenkompression

Datenkompression - Definition, Anwendungsgebiete, Algorithmen kurz vorgestellt


Autor: Rolf Viehmann (Rolfhub)
Datum: 29-01-2002, 10:34:23
Referenzen: keine
Schwierigkeit: Anfänger
Ansichten: 6001x
Rating: 8 (2x bewertet)

Hinweis:

Für den hier dargestellte Inhalt ist nicht der Betreiber der Plattform, sondern der jeweilige Autor verantwortlich.
Falls Sie Missbrauch vermuten, bitten wir Sie, uns unter missbrauch@it-academy.cc zu kontaktieren.

[Druckansicht] [Als E-Mail senden] [Kommentar verfassen]



0. Bemerkung

Dieses Dokument erklärt zuerst die Grundlagen zum Thema Kompression, was für viele recht langweilig sein könnte, da man das halt schon kennt, ich werde aber auch einige Kompressionsverfahren etwas näher beleuchten, was dann schon eher interessant werden könnte.

1. Definition

"Komprimieren" bedeutet so viel wie "verdichten", eng zusammenpacken. Und genau das macht ein Kompressionsalgorithmus, er speichert die gegebenen Daten mit möglichst wenigen Bytes ab.

2. Anwendungsgebiete

Komprimierte Daten müssen vor deren Verwendung wieder dekomprimiert werden, was natürlich Zeit kostet, wenn also auf den Inhalt einer Datei schnell zugegriffen werden muss, dann sollte keine Kompression benutzt werden, ansonsten bietet sich Kompression in vielen Lebenslagen an, insbesondere, wenn größere Dateien gespeichert oder über langsame Verbindungen (Internet!) übertragen werden sollen.
Zusatzhinweis: In diesem Dokument ist oft von Archivdateien die Rede, es gibt jedoch noch eine weitere Anwendung für gepackte Daten: Streaming. Hierbei wird der Datenstrom in einzelne Blöcke zerlegt, die einzeln gepackt und übertragen werden können, und der Reihe nach vom Empfänger entpackt und wieder zusammengesetzt werden. Dies wird beim digitalen Fernsehen genutzt, sowie bei Modemverbindungen und beim Internetradio.

3. Ablauf

1. Das Packprogramm liest eine Datei ein und speichert diese in einem Archiv ab. Dieses Archiv scheint willkürliche Bytes zu enthalten, die keine Ordnung erkennen lassen, das Programm ist jedoch in der Lage, aus diesen Daten wieder die Originalzeichenfolge (Originaldatei) zu erzeugen.
2. Diese Archivdatei kann jetzt wesentlich platzsparender gespeichert werden oder schneller übertragen werden, als dies mit der Originaldatei möglich wäre. Dabei ist zu beachten, dass die Archivdatei bei der Übertragung nicht verändert werden darf, sonst wird diese nutzlos, im FTP - Programm muss also unbedingt der Transfermodus "Binary" eingestellt werden (Kommandozeilen - FTP: Befehl "bin").
3. Bei Bedarf kann die Originaldatei jederzeit entpackt werden, was in der Regel wesentlich schneller geht, als das Packen.
4. Beim Entpacken wird die mitgespeicherte Prüfsumme überprüft, um sicherzustellen, dass die entpackte Datei mit der Ursprünglichen identisch ist. Meist ist diese Prüfsumme eine sogenannte "CRC" - Checksumme, was für "Cyclic Redundancy Code" steht. Somit kann eine fehlerhafte Übertragung der Daten oder eine defekte Diskette schnell entdeckt werden.
Viele Archivformate wie z.B. .zip / .rar / .ace / .tgz (= .tar.gz) sind in der Lage, mehrere Dateien, die irgendwie zusammengehören, in nur einer Archivdatei abzulegen, sogar mit der Verzeichnisstruktur (falls gewünscht), so dass nur eine Datei übertragen werden kann, und keine Datei vergessen wird.

4. Limits

Nicht alle Dateien lassen sich gleich gut packen, bei manchen Dateien kann das Größenverhältnis beeindruckende Werte erreichen, bei anderen kann die Kompression fast nutzlos sein, wobei sich generell größere Dateien besser packen lassen, als kleine.
Verschlüsselte Daten lassen sich nur sehr schlecht packen, man sollte die Daten also erst packen, und das Archiv anschließend verschlüsseln.
Schon gepackte Daten lassen sich ebenfalls nur sehr schlecht noch einmal packen.

5. Verlustfrei vs. Verlustbehaftet

Einige Formate, wie z.B. Textdateien oder ausführbare Dateien müssen selbstverständlich genau reproduziert werden, bei Bildern, Videos und Sounds ist dies jedoch nicht immer nötig, hier werden die Daten oftmals verlustbehaftet komprimiert, was folgendermaßen abläuft:
0. Die Daten werden evtl. in ein anderes Darstellungssystem gewandelt, was eine intelligente Auswahl der zu entfernenden Daten ermöglicht
1. Die Daten werden reduziert, es werden also Informationen entfernt, wobei die Informationen entfernt werden, die vom Menschen mit seinen nicht perfekten Sinnen ohnehin nicht wahrgenommen werden.
2. Die Daten sind jetzt besser von einem (verlustfreien) Kompressionsalgorithmus zu packen, als das ohne die Reduktion der Fall gewesen wäre.
3. Die Daten können jederzeit wieder entpackt werden, wobei die Reduktion natürlich nicht rückgängig gemacht werden kann, daher kann evtl. ein Qualitätsverlust wahrgenommen werden, in diesem Falle sollte die Kompressionsrate (und somit die Reduktion) auf einen sinnvolleren Wert eingestellt werden.
4. Vor der Darstellung müssen die Daten wieder in ihr ursprüngliches Format gewandelt werden.
Die "Hohe Kunst" beim Entwickeln eines Algorithmus zur Datenreduktion ist das Entwickeln eines Modells, das die menschlichen Sinne möglichst gut beschreibt, so dass der Computer die am wenigsten wahrnehmbaren Anteile des Signals herausrechnen kann, dies wird auch in Zukunft noch ein spannendes Forschungsfeld bleiben.

6. Verfahren

Im Wesentlichen werden zwei Methoden unterschieden, Daten zu komprimieren:
- Dictionary-Based-Algorithmen
- Statistical-Encoder
Beide Methoden arbeiten grundverschieden, jedoch kann man nicht behaupten, eines der zwei Verfahren wäre das bessere, dies hängt von den zu komprimierenden Daten ab.

6.1 Dictionary-Based-Algorithmen

Dieses Verfahren macht sich die Tatsache zunutze, dass in vielen Dateien zahlreiche Zeichenketten immer wieder auftauchen, diese werden dann in einem Dictionary (Wörterbuch) gespeichert, und es wird nur noch eine Referenz an den Eintrag in den Ausgabestrom geschrieben.
Dieses Verfahren wird beispielsweise bei .GIF - Dateien (LZ77, LZ78) verwendet, sowie bei Modemverbindungen.
Je nachdem, wie der Algorithmus genau realisiert wurde, gibt es zwei Methoden, um zu verhindern, dass die Kompressionsrate zu sehr sinkt, wenn sich die Zusammensetzung des Eingangsdatenstroms zu sehr ändert:
- Wenn das aktuelle Wörterbuch als ungeeignet erscheint, wird es über Bord geworfen, und ein neues wird aufgebaut.
- Die Einträge, die schon länger nicht mehr benutzt wurden, werden durch neue ersetzt.

6.2 Statistical-Encoder (Huffman - Code)

Dieses Verfahren macht sich die Tatsache zu Nutze, dass manche Zeichen häufiger auftreten, als andere. Die Idee ist folgende:
Normalerweise wird in einer Textdatei o.ä. (viele Formate sind intern Textdateien) jedes Zeichen durch ein Byte (in seltenen Fällen auch durch zwei Byte - "Unicode") dargestellt. Ein Statistical-Encoder weist jedoch jedem Zeichen eine Bitfolge zu, die unterschiedlich lang ist. Die Zeichen, die besonders häufig auftauchen, bekommen die kürzesten Bitfolgen zugewiesen, die längeren Bitfolgen werden entsprechend den seltenen Zeichen zugewiesen, was insgesamt gesehen kräftig Platz sparen kann. Wenn jedoch alle Zeichen ungefähr gleich häufig auftreten, kann ein solches Verfahren nichts bewirken.
Wenn man die Kompressionsrate weiter erhöhen will, so kann man die Wahrscheinlichkeit des Auftretens eines Zeichens in Abhängigkeit vom vorhergehenden Zeichen betrachten, was natürlich komplizierter und rechenintensiver ist. Wenn man nur ein vorhergehendes Zeichen betrachtet, so spricht man von einem "Order-1-Modell", bei Betrachtung von zwei vorhergehenden Zeichen entsprechend von einem "Order-2-Modell" usw.
Auch hier wird nicht unbedingt mit einer festen Wahrscheinlichkeit gearbeitet, sondern das Modell wird mit jedem Zeichen, das komprimiert wird, aktualisiert.

7. Anhang

Häufig genutzte Dateiformate, die Kompression benutzen:
.bmp - Bilddatei, kann verlustfrei gepackt sein, wenn diese 4 Bit oder 8 Bit - Farben benutzt (16 oder 256 Farben).
.exe - Ausführbare Datei, die ein selbstentpackendes Archiv sein kann (evtl. mit integriertem Installationsprogramm).
.gif - Bilddatei, max. 256 Farben, verlustfrei gepackt
.jpeg / .jpg / .jpe - Bilddatei, 256 Graustufen oder 16,8 Mio. Farben, verlustbehaftet gepackt
.mp1 / .mp2 / .mp3 - Musik, verschiedene Datenraten sind je nach Layer (1, 2, 3) möglich, verlustbehaftet gepackt
.mpeg / .mpg - Video, verlustbehaftet gepackt
.png - Bilddatei, verlustfrei gepackt
.vqf - Musik, verlustbehaftet gepackt
.zip / .rar / .ace / .tgz (= .tar.gz) - Allzweck-Archiv-Dateien, verlustfrei gepackt


onestone
Administrator
Beitrag vom:
05-11-2001, 11:06:24

Interessant...

...sind auch die verschiedenen Moeglichkeiten des Komprimierens. Ich habe das ganze mal in einem Informatik-Buch gelesen. Eine sinnvolle Sache ist, wenn zb in Binary im Code steht "00000001111" dann schaut es nach dem packen zb so aus "7x4x1". Zuerst sind es 11 Stellen, dann 5 Stellen, das macht das ganze also mehr als die Hälfte kleiner...Achja, das ist natürlich ein erfundener Syntax...

-----------------------------------------------------
Kein Problem kann so komplex sein, dass es keine Lösung dafür gibt.


[back to top]



Userdaten
User nicht eingeloggt

Gesamtranking
Werbung
Datenbankstand
Autoren:04508
Artikel:00815
Glossar:04116
News:13565
Userbeiträge:16552
Queueeinträge:06243
News Umfrage
Ihre Anforderungen an ein Online-Zeiterfassungs-Produkt?
Mobile Nutzung möglich (Ipone, Android)
Externe API Schnittstelle/Plugins dritter
Zeiterfassung meiner Mitarbeiter
Exportieren in CSV/XLS
Siehe Kommentar



[Results] | [Archiv] Votes: 1144
Comments: 0