Stichpunkte

Allgemein
	die jedem einzelnen Zeichen eines Textes eine unterschiedlich lange Folge von Bits zuordnet
	Die Entropiekodierung ist eine Methode zur verlustfreien Datenkompression
	Im Gegensatz zu Stringersatzverfahren (wie LZ77 oder LZ78)
	die einer Folge von Zeichen des Originaltextes durch eine Folge von Zeichen eines anderen Alphabets ersetzt
	die den Zeichen zugeordnet werden
	kann die Anzahl der Bits
	Da eine bestimmte Mindestanzahl von Bits notwendig ist
	um alle Zeichen voneinander zu unterscheiden
	nicht unbegrenzt klein werden
	Die optimale Anzahl von Bits
	wird durch die Entropie bestimmt
	die einem Zeichen mit einer gegebenen Wahrscheinlichkeit zugeordnet werden sollte
	Entropiekodierer werden häufig mit anderen Kodierern kombiniert
	LHarc zum Beispiel verwendet einen LZ-Kodierer und gibt die von diesem Kodierer ausgegebenen Zeichen an einen Huffman-Kodierer weiter
	"Verbergen") 1 Kodierung 1.1 Mit ganzen Bits 1.2 Verbesserung 2 Modell 2.1 Statisches Modell 2.2 Dynamisches Modell 2.3 Level des Modells 3 Literatur 4 Weblinks [Bearbeiten]
	Auch ZIP und BZIP besitzen als letzte Stufe einen Entropiekodierer. Inhaltsverzeichnis showTocToggle("Anzeigen"
Kodierung
	Die Kodierung der Zeichen mit einer variablen Anzahl von Bits stellt ein Problem dar
	dass die Entropie für fast alle Wahrscheinlichkeiten eine rationale Zahl ergibt. [Bearbeiten]
	insbesondere wenn man bedenkt
Mit ganzen Bits
	die die Anzahl der Bits auf ganze Zahlen rundet
	Die Shannon-Fano-Kodierung schlägt eine Möglichkeit vor
	Dieser Algorithmus liefert aber in bestimmten Fällen nicht die optimale Lösung
	Deshalb wurde der Huffman-Code entwickelt
	der beweisbar immer eine der optimalen Lösungen mit ganzen Bits liefert
	Beide Algorithmen erzeugen einen präfixfreien Code variabler Länge
	indem ein binärer Baum konstruiert wird
	In diesem Baum stehen die "Blätter" für die zu kodierenden Symbole
	Die inneren Knoten für die abzulegenden Bits
	gibt es auch Varianten
	die feste Codetabellen verwenden
	die individuelle Tabellen speziell angepasst auf die zu kodierenden Daten erstellen
	Neben diesen Verfahren
	Der Golomb code kann z.B. bei Daten verwendet werden
	bei denen die Häufigkeitsverteilung bestimmten Regeln unterliegt
	Diese Codes haben Parameter
	um ihn auf die exakten Parameter der Verteilung der Häufigkeiten anzupassen. [Bearbeiten]
Verbesserung
	Diese Verfahren treffen aber die von der Entropie vorgeschriebene Anzahl von Bits nur in Ausnahmefällen
	Das führt zu einer nicht optimalen Kompression
	Ein Beispiel: Eine Zeichenkette mit nur 2 verschiedenen Symbolen soll komprimiert werden
	Das eine Zeichen hat eine Wahrscheinlichkeit von <math>mathrm{p}(A)=0{
	}25<math>
	das andere von <math>mathrm{p}(B)=0{
	}75<math>
	Die Verfahren von Shannon und Huffman führen dazu
	dass beide Zeichen mit je einem Bit abgespeichert werden
	die so viele Bits enthält wie die Eingabe an Zeichen
	Das führt zu einer Ausgabe
	}41<math> Bits für das Zeichen A verwenden und dafür <math>-log_2(0{
	}25)=2<math> Bits für B
	}75)approx 0{
	Ein optimaler Entropie-Kodierer würde aber nur <math>-log_2(0{
	die nur <math>-0{
	}75*log_2(0{
	}25*log_2(0{
	}75)-0{
	Das führt zu einer Ausgabe
	}75)approx 0.81<math> Bits pro Zeichen enthält
	Mit einem Arithmetischen Kodierer kann man Zeichen entropieoptimal abspeichern. [Bearbeiten]
Modell
	Um die Anzahl der Bits für jedes Zeichen festlegen zu können
	muss man zu jedem Zeitpunkt des Kodierungsprozesses möglichst genaue Angaben über die Wahrscheinlichkeit der einzelnen Zeichen machen
	Diese Aufgabe hat das Modell
	desto besser die Kompression
	Je besser das Modell die Wahrscheinlichkeiten vorhersagt
	Das Modell muss beim Komprimieren und Dekomprimieren genau die gleichen Werte liefern
	Im Laufe der Zeit wurden verschiedene Modelle entwickelt. [Bearbeiten]
Statisches Modell
	Beim Statischen Modell wird vor der Kodierung der Zeichenfolge eine Statistik über die gesamte Folge erstellt
	Die dabei gewonnenen Wahrscheinlichkeiten werden zur Kodierung der gesamten Zeichenfolge verwendet. Vorteile Kodiertabellen müssen nur einmal erstellt werden
	Das Verfahren ist deshalb sehr schnell
	Die Ausgabe ist ohne die zum Dekomprimieren notwendigen Statistiken garantiert nicht größer als der Originaltext. Nachteile Die Statistik muss an den Decoder übermittelt werden (entweder als Statistik oder in Form der Huffman- oder Shannon-Fano-Codes)
	was Speicher kostet
	Die Statistik bezieht sich auf die gesamte Zeichenfolge
	d.h. die Werte passen sich nicht an lokale Gegebenheiten in der Zeichenkette an. [Bearbeiten]
Dynamisches Modell
	In diesem Modell verändern sich die Wahrscheinlichkeiten im Laufe des Kodierungsprozesses
	d.h. hier wird nach dem Kodieren eines Zeichens die Wahrscheinlichkeit dieses Zeichens erhöht. Rückwärts dynamisch: Hier wird vor dem Kodieren ausgezählt
	wie oft jedes Zeichen vorkommt
	Dabei gibt es mehrere Möglichkeiten: Vorwärts dynamisch: Die Wahrscheinlichkeiten beziehen sich auf bereits kodierte Zeichen
	Aus dieser Anzahl lassen sich genaue Wahrscheinlichkeiten ermitteln
	sodass gegen Ende die Wahrscheinlichkeiten für die einzelnen Zeichen sehr exakt werden. Vorteile Anpassung des Modells an lokale Gegebenheiten Statistik-Informationen müssen im vorwärts-dynamischen Modell nicht übertragen werden. Nachteile Tabellen müssen nach jedem Zeichen überarbeitet werden
	Im Laufe des Kodierungsprozesses werden die Anzahlen erniedrigt
	Das kostet Rechenzeit. Die Statistik eilt den wahren Gegebenheiten hinterher
	sondern mit den Häufigkeiten der Zeichen
	Im schlimmsten Fall stimmt die Statistik nie mit den wahren Wahrscheinlichkeiten überein
	was dazu führt
	das mehr Bits benötigt werden. Normalerweise arbeitet man bei dynamischen Modellen nicht wirklich mit Wahrscheinlichkeiten
	Dynamische Modelle lassen auch noch andere Variationsmöglichkeiten zu
	Man kann Statistik-Daten altern
	indem man von Zeit zu Zeit die Häufigkeiten der Zeichen halbiert
	Damit verringert man den Einfluss von weit zurückliegenden Zeichen
	so daß alle Zeichen kodiert werden können
	Für noch nie vorgekommene Zeichen gibt es mehrere Varianten: Man nimmt eine Häufigkeit von mindestens 1 für jedes Zeichen an
	Man fügt dem Alphabet ein neues Zeichen hinzu
	Dieses Zeichen deutet ein Verlassen des Kontextes an
	können alle Zeichen des Alphabetes mit einem festen Kode geschrieben oder gelesen werden
	Nachdem diese Zeichen kodiert wurden
	Das Zeichen wird normalerweise Escape-Zeichen genannt
	die der Familie PPM
	Einige der besten Komprimieralgorithmen
	benutzen dieses Vorgehen. [Bearbeiten]
Level des Modells
	Das Level eines Modells bezieht sich darauf
	wie viele Zeichen der Historie vom Modell für die Berechnung der Wahrscheinlichkeiten herangezogen werden
	Ein Level 0 Modell betrachtet keine Historie und gibt die Wahrscheinlichkeiten global an
	Ein Level 1 Modell dagegen betrachtet das Vorgängerzeichen und trifft in Abhängigkeit von diesem Zeichen seine Aussage über die Wahrscheinlichkeit. (Soll Deutscher Text kodiert werden ist zum Beispiel die Wahrscheinlichkeit des Buchstaben "U" nach einem "Q" viel höher
	oder die Wahrscheinlichkeit eines großen Buchstaben in der Mitte eines Wortes viel kleiner als nach einem Leerzeichen)
	Das Level kann theoretisch beliebig hoch sein
	erfordert dann aber enormen Speicherplatz für gigantische Datenmengen
	um aussagekräftige Statistiken zu erhalten
	PPM verwenden einen arithmetischen Kodierer mit einem dynamischen Modell des Levels 5. [Bearbeiten]
Literatur
	Es gibt nur sehr wenige Bücher zum Thema Datenkompression Mark Nelson: The Data Compression Book. bereitet einen relativ guten Einstieg
	Das Buch beschäftigt sich allerdings mehr mit der Implementation als mit der Theorie der Datenkompression. [Bearbeiten]
Weblinks
	u.a. auch für PPM (http://www.geocities.com/SiliconValley/Bay/1995/compression-pointers.html) en:Entropy encoding ja:エントロピー符� ko:엔트로피 부호화
	Compression Pointers - Enthält eine lange Liste mit Links zum Thema Datenkomprimierung

Dieser Artikel basiert auf dem Artikel Entropiekodierung aus der freien Enzyklopädie wikipedia und steht unter der GNU Lizenz für freie Dokumentation. In der wikipedia ist eine Liste der Autoren verfügbar.