Datenkompression: Verlustfreie Verfahren: Statistische Verfahren
| Wiki Bookwizard - ThePacker |
| Clear page cache |
| Edit current page |
| Create or Edit page TOC include TOC with {{:Datenkompression: Verlustfreie Verfahren: Statistische Verfahren:_TOC}} |
- 5.1 Statistische Verfahren
- 5.1.1 Der Morse Code
- 5.1.2 Shannon-Fano Codierung
- 5.1.3 Huffman Codierung
- 5.1.4 Präfixfreie Codes
- 5.1.5 MNP - MicroCom Network Protokoll
- 5.1.6 Arithmetische Codierung
- 5.1.7 Adaptive Arithmetische Codierung
- 5.1.8 Quasiarithmetische Codierung
- 5.1.9 CABAC
- 5.1.10 Dynamische Markov Codierung
- 5.1.11 PPM
- 5.1.12 BWT - Burrows-Wheeler-Transformation
- 5.1.13 BWCA - Burrows-Wheeler Kompressions Algorithmus
- 5.1.1 Der Morse Code
Geplante Teilsektionen
BearbeitenPräfixcodierung
Bearbeiten- Präfixfreie Codes
MNP - MicroCom Network Protokoll
BearbeitenBei der Datenübertragung mit Modems erfolgt die Kompression der Daten nach dem Microcom Network Protocol1, abgekürzt MNP. Es sind zwei Varianten des MNP Protokolls gebräuchlich, die als MNP5 und MNP7 bezeichnet werden. In beiden Protokoll-Varianten ist die Lauflängen-Codierung ein Teil der Datenkompression. Jedes Byte, das mindestens dreimal in Folge auftritt, wird in eine vier Byte lange Folge von drei gleichen Bytes abgebildet mit nachfolgendem Wiederholgungszähler. Die Markierung, dass eine Kompression stattgefunden hat, wird damit durch die drei aufeinander folgenden Bytes gekennzeichnet. Der anschließende Wiederholungszähler gibt die um die Zahl Drei verminderte Anzahl der aufeinander folgenden gleichen Zeichen an. Der Vorteil, dass kein spezielles Kompressionszeichen benötigt wird, wird mit dem Nachteil erkauft, dass eine Zeichenfolge von drei gleichen Zeichen um ein Byte länger dargestellt wird. (INFO: FHT-Esslingen)
Wie man dem Titel bereits entnehmen kann, handelt es sich bei MNP um Protokolldefinitionen. Es wird/wurde für die Übertragung per Modems benötigt. Diese Protokolle erfüllen verschiedene Anforderungen. Eine war unter anderem die Kompression der zu übertragen Daten und die andere ist, für einen Fehlerschutz der übertragenen Daten zu sorgen.
- MNP1 - Übertragungsprotokoll - Blockmode - Halb Duplex
- MNP2 - Übertragungsprotokoll - Streammode - Voll Duplex
- MNP3 - Übertragungsprotokoll - Streammode mit Start/Stop Bits
- MNP4 - Übertragungsprotokoll - Fehlerschutz
- MNP5 - Datenkompressionsalgorithmus - Dynamische Anpassung der Länge einzelner Symbole and die Häufigkeit - und RLE-Codierung
- MNP6 - ?
- MNP7 - Datenkompressionsalgorithmus
- MNP8 - ?
- MNP9 - Datenkompressionsalgorithmus
- MNP10 - Übertragungsprotokoll zur Anpassung der Modulationsgeschwindigkeit an die Güte der Modem-Leitung
MNP5 MNP7
MNP9
Adaptive Arithmetische Codierung
Bearbeiten
- Erweiterung der arithmetischen Codierung durch ein Modell, welches die Auftrittswahrscheinlichkeit der bisher codierten/decodierten Symbole berücksichtigt.
Quasiarithmetische Codierung
Bearbeiten- Tabellengestützte nahezu-arithmetische Codierung (Howard und Vitter) Papers 1993 - 2004
- vorteil: ist sehr schnell
Dynamic Marcov Coding
Bearbeiten- 5.1.10 Dynamische Markov Codierung
- Implementation eines Modells (Zustands-Automat), der sich an die bedingten Wahrscheinlichkeiten des Symbolstroms anpassen kann.
- Die Wahrscheinlichkeiten können anschließend für die arithmetische Codierungverwendet werden.
PPM
Bearbeiten- 5.1.11 PPM
- Prediction by partial Matching
- Ähnlich wie die dynamische Markov-Codierung, bietet sie einen Automaten um die Auftretenswahrscheinlichkeit des nächsten Eingabesymbols zu schätzen
- Modell wird verwendet für die arithmetische Codierung
BWT - Burrows Wheeler Transformation
Bearbeiten
Im Jahr 1994 haben die beiden Forscher M. Burrows und David J. Wheeler in der Arbeit "A Block-sorting Lossless Data Compression Algorithm" einen Algorithmus vorgestellt, der in der Lage ist eine Transformationscodierung für einen endlich langen Text vorzunehmen. Die beiden Autoren beschreiben in der Arbeit einen verlustfreien Kompressions-Algorithmus, der mit Hilfe einer Sortierung eines Textblockes arbeitet. Dazu wird eine reversible Transformation auf einen Textblock angewendet. Das Resultat dieser Transformation wird durch weitere geeignete Verarbeitungsschritte anschließend codiert. Die Transformation selbst ist nicht in der Lage, die Daten zu komprimieren, aber die Neusortierung macht es teilweise einfacher, die Daten mit einem einfachen Algorithmus zu codieren.
Der Vorteil ist, dass dieser Transformationsalgorithmus in der Lage ist, die Daten so aufzuteilen, dass eine Kompressionsrate erreicht werden kann, die insbesondere durch komplexe statistische Modelle erreicht werden kann. Dennoch hat diese Transformation einen Nachteil, die transformierte Ausgabe wird erst dann besonders effizient codierbar, wenn der zu transformierende Text einige Kilobyte Größe hat.
Citeseer Link auf den Artikel