Datenkompression: Verlustfreie Verfahren: Statistische Verfahren

Aus Wikibooks
Zur Navigation springen Zur Suche springen
Wiki Bookwizard - ThePacker
Clear page cache
Edit current page
Create or Edit page TOC
include TOC with

{{:Datenkompression: Verlustfreie Verfahren: Statistische Verfahren:_TOC}}

zurück

5 Verlustfreie Verfahren

5.1 Statistische Verfahren 10% fertig
5.1.1 Der Morse Code 20% fertig
5.1.2 Shannon-Fano Codierung 80% fertig
5.1.3 Huffman Codierung 30% fertig
5.1.4 Präfixfreie Codes 00% fertig
5.1.5 MNP - MicroCom Network Protokoll 00% fertig
5.1.6 Arithmetische Codierung 20% fertig
5.1.7 Adaptive Arithmetische Codierung 00% fertig
5.1.8 Quasiarithmetische Codierung 00% fertig
5.1.9 CABAC 10% fertig
5.1.10 Dynamische Markov Codierung 00% fertig
5.1.11 PPM 00% fertig
5.1.12 BWT - Burrows-Wheeler-Transformation 10% fertig
5.1.13 BWCA - Burrows-Wheeler Kompressions Algorithmus 00% fertig


Geplante Teilsektionen[Bearbeiten]

Präfixcodierung[Bearbeiten]

  1. Präfixfreie Codes

MNP - MicroCom Network Protokoll[Bearbeiten]

Bei 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]

5.1.7 Adaptive Arithmetische Codierung 0von10.png
  1. Erweiterung der arithmetischen Codierung durch ein Modell, welches die Auftrittswahrscheinlichkeit der bisher codierten/decodierten Symbole berücksichtigt.

Quasiarithmetische Codierung[Bearbeiten]

5.1.8 Quasiarithmetische Codierung 0von10.png
  1. Tabellengestützte nahezu-arithmetische Codierung (Howard und Vitter) Papers 1993 - 2004
  2. vorteil: ist sehr schnell

Dynamic Marcov Coding[Bearbeiten]

5.1.10 Dynamische Markov Codierung 0von10.png
  1. Implementation eines Modells (Zustands-Automat), der sich an die bedingten Wahrscheinlichkeiten des Symbolstroms anpassen kann.
  2. Die Wahrscheinlichkeiten können anschließend für die arithmetische Codierungverwendet werden.

PPM[Bearbeiten]

5.1.11 PPM 0von10.png
  1. Prediction by partial Matching
  2. Ähnlich wie die dynamische Markov-Codierung, bietet sie einen Automaten um die Auftretenswahrscheinlichkeit des nächsten Eingabesymbols zu schätzen
  3. Modell wird verwendet für die arithmetische Codierung

BWT - Burrows Wheeler Transformation[Bearbeiten]

5.1.12 BWT - Burrows-Wheeler-Transformation 1von10.png

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

  1. http://citeseer.ist.psu.edu/76182.html

BWCA - Burrows Wheeler Kompressions Algorithmus[Bearbeiten]

5.1.13 BWCA - Burrows-Wheeler Kompressions Algorithmus 0von10.png