→ Suche diesen Artikel in der aktuellen Wikipedia
![[Home]](/wikipedia/wiki.jpg)
DatenkompressionKompression:
Dekompression:
Populäre Anwendungen, die solche Komprimierungsverfahren beinhalten, sind etwa im Personal-Computerbereich ZIP? - Programme, Huffman?-Kodierung für Faxübermittlung, JPG? Bildformate mit Komprimierung von Bild- und MP3? für die Komprimierung von Klangdaten. Diese erstellen die verkürzten, gepackten Dateiversionen in einem entsprechenden Format und entpacken diese Archive? genannten Dateien oder Dateisammlungen wieder hin zu den ursprünglichen Originalen.
Zur Verkürzung eines Textes werden zwei wesentliche Ideen verwendet. (a) Zur Verkürzung werden einerseits bestimmte häufiger vorkommende Zeichen oder Gruppen von Zeichen im Ausgangstext durch kurze Zeichenfolgen und andererseits selten vorkommende Zeichen durch längere Zeichen im Kodiertext kodiert. (b) Ein anderer wesentlicher Aspekt ist die Betrachtung von möglicher Verschwendung bei der Repräsentation, d.h. es wird im Gegensatz zum Ausgangstext jede Kombination von Zeichen mit einer Bedeutung verbunden, was zumeist sonst nicht der Fall ist. (c) Bei verlustbehafteten Verfahren wird in der einen oder anderen Weise entschieden, dass Information im Ausgangstext überflüssig ist (etwa auf die Hörfähigkeit des menschlichen Ohres bezogen, bei MP3) und dass diese Information weggelassen (oder mit geringerer Detailiertheit aufgezeichnet) werden kann. Diese wird dann auch nicht in den Kodiertext übernommen. Ein Verfahren, welches nur einzelne Symbolketten durch einzelne andere ersetzt, erreicht im Allgemeinen keine Kompression. Kompression benötigt mehr als Kodierung.
Ausgangstext: AUCH EIN KLEINER BEITRAG IST EIN BEITRAG Kodiertext: AUCH EIN KLEINER BEITRAG IST -4 -3
Hier würde erkannt, dass die Worte EIN und BEITRAG zweimal auftauchen, und dadurch angegeben, dass diese mit den gerade zurückliegenden übereinstimmen. Bei genauerer Betrachtung könnte dann auch das EIN in KLEINER entsprechend kodiert werden. (Im Sinne von Kodierung ist -3 ein Code für BEITRAG)
Jedes Verfahren praktiziert in direkter oder indirekter Weise auch solch eine Form von wahrscheinlichkeitsgesteuerter Vorgehensweise. Einige Verfahren verwenden dazu explizit Statistik im Verfahren (Huffman). Andere verwenden radikal einfache Mechanismen der Wiedererkennung über Zwischenspeicher (Lempel-Ziv) um die gleiche Wirkung zu erzielen. Eine typische Rolle spielen auch die natürlichen Zahlen als natürliche Codes, indem sie als Index oder Adresse auf einen orginalen Inhalt verweisen. Hier kommt zum Tragen, das kleine Zahlen kürzer sind als grosse Zahlen.
Gemeinsam ist den Verfahren die interne Verwendung einer Datenbasis (Gedächtnis, Statistik, Modell von Zeichenabhängigkeiten), die während der Analyse eines Textes geführt wird. Diese kann bei statischen Verfahren als Ganzes vor der eigentlichen Herstellung des Kodiertextes geschehen oder bei dynamischen Verfahren on-th-fly?, kontinuierlich während des Aufschreibens bzw. Übertragens eines komprimierten Textes. Aus praktischen Gründen haben sich Verfahren durchgesetzt, die kontinuierlich verkürzen und Zeichen für Zeichen kodieren und umgekehrt (beim Entpacken) kontinuierlich auslesen und die ursprüngliche (lange) Version in gleicher Reihenfolge wiederherstellen. Eine wichtiges Konzept ist die Idee einer mitgeführten Modellierung? bzw. interner Statistik, die beim Kodieren Zeichen für Zeichen intern statistisch erfasst. Diese Statistik wird beim Auspacken (dann mit Hilfe der entpackten Zeichen) noch einmal erstellt, um das gleiche Wissen um die Häufigkeit wie beim Einpacken verwenden zu können. Auf diese Weise muss keine besondere Statistik und keine Art von Kodebuch übertragen werden.
Huffmann?. Hier wird eine Statistik zumeist für den Text als Ganzes erstellt. (Es gibt jedoch auch dynamische Varianten.) Entsprechend der Häufigkeit? werden für Gruppen von Ausgangssymbolen (z.B. Wörtern) bestimmte Folgen von 0 und 1 in einem Kodebuch definiert. Die Festlegung im Kodebuch? erfolgt geschickterweise so, dass Untergruppen von Code, die sich durch eine folgende 0 und 1 unterscheiden, einer etwa gleichgrosse Menge an Ausgangszeichen entspricht. Im Kodiertext wird jeweils nur der Code aufgeschrieben. Beim Entpacken wird aufgrund des Codes im Kodebuch das dazpassende Originalwort nachgesehen, ausgelesen und damit der Orginaltext wieder hergestellt.
Lempel?,Ziv?-I. Es wird ein Zwischenspeicher mitgeführt, der einen Teil des bereits gelesen Textes speichert. Zu kodierende Zeichen oder Textstücke werden als Referenzen (einer Adresse vergleichbar) auf diesen Zwischenspeicher kodiert. Der Zwischenspeicher dient hier als eine Art lokale Version eines Kodebuches. Dies hat den Vorteil, dass dieses nicht getrennt erstellt und/oder übertragen werden muss und, dass der Packer sich etwaigen Veränderungen im Text automatisch anpassen kann (lokal adaptiv).
Lempel?/Ziv?-II. Die zweite Lempel-Ziv-Konzeption ist bis heute eine der bedeutsamsten Komprimiermethoden und in vielen Varianten in fast allen typischen Anwendungen enthalten. Sie liest Zeichen für Zeichen ein und vergleicht diese Kette mit bereits vorhanden Einträgen. Schliesslich entsteht ein neuer Eintrag in dem internen Verzeichnis. Dieser besteht aus einem bereits vorhandenen Eintrag und dem neu eingelesenen Zeichen. Dieses enthält mit der Zeit immer längere tatsächlich vorkommende Textfragmente. Tatsächlich übertragen werden jedoch nur jeweils Adressen (Indizes) dieser Fragmente und jeweils ein neuer Buchstabe. Das interne Wörterbuch der bekannten Textstücke ist somit zugleich auch Kodebuch. Es gibt dann unterschiedliche Varianten, die sich mit der Frage des Managements dieses internen Gedächtnisses befassen. Die Umsetzung liefert eine auch unter praktischen Gesichtspunkten optimale Methode. Es ist bemerkenswert welche Grade von Kompression und Allgemeinverwendbarkeit mit diesem Verfahren erreicht werden, welches im Kern nur auf Wiedererkennung, Kombination und Referenz aufbaut.
[Arithmetisches Kodieren]?. Bei diesem Verfahren wird eine kontinuierliche Berechnung durchgeführt, die gewissermassen in einer einzigen sehr langen Zahl (= komprimierte Datei) Information speichert. Dabei bestimmen die Häufigkeiten im Ausgangstext Anteile beim jeweiligen Rechenschritt. Die verwendeten Rechenoperationen werden beim Auslesen durch die gelieferte 'lange Zahl' ersichtlich und lassen den Rückschluss auf das jeweils kodierte, gepackte Zeichen zu. Die Kernidee ist, dass sich häufigere Symbole in einer geringeren Veränderung der globalen Zahl (eigentlich ein Teilungsinterval) wiederspiegeln. Arithmetisches Kodieren besticht dadurch, dass es wesentlich die Bitgrenzen aufhebt und eigentlich einen rein mathematischen Formalismus verwendet. Dieser macht eigentlich notwendig, riesige Zahlen zu berechnen. Durch geschickte Wahl von Randparametern kann aber dennoch eine praktikable Implementation erreicht werden.
MP3? Kodierung. Diesem Verfahren für die Kodierung von akustischen Medieninhalten (Musik, Filmsound, etc.) liegt die genaue Untersuchung der Hörfähigkeit des menschlichen Gehörs zugrunde. Ergebnis ist die Möglichkeit bestimmte Folgen von Höreindrücken verändern zu können, ohne dass es zu einer subjektiv feststellbaren Veränderung des Gehörten kommt. Dies wird bei der eigentlichen Kodierung als Quelle für Kompaktifizierung genutzt.
Wavelet Kodierung. (Sorry, darüber weiss ich zu wenig. Schreib Du mal.)