Huffman Kodierung
Dieser Onlinerechner erstellt eine Huffman-Kodierung anhand eines Satzes von Symbolen und deren Wahrscheinlichkeiten.
Dieser Onlinerechner erstellt eine Huffman-Kodierung anhand eines Satzes von Symbolen und deren Wahrscheinlichkeiten. Eine kurze Beschreibung des Huffman-Codes kann man unter dem Rechner finden.
Huffman-Kodierung
Tabelle der Symbol-Wahrscheinlichkeit
| Name | Wert | ||
|---|---|---|---|
Von Wikipedia
In der Informatik und Informationstheorie ist die Huffman-Kodierung ein Entropie-Kodierung , die für verlustfreie Kompression genutzt wird. In diesem Verfahren wird eine feste Anzahl von Quellsymbolen jeweils Codewörter mit variabler Länge zugeordnet. David A. Hufmann hat diese Kodierung in 1952 in seiner Zeit als PHD Student an der MIT entwickelt und in der Abhandlung "A Method for the Construction of Minimum-Redundancy Codes." veröffentlicht.
Die Huffman Kodierung nutzt eine spezielle Methode, um die Repräsentation für jedes Symbol auszuwählen. Dies ergibt einen Präfix-Kocde (auch manchmal präfixfrei genannt, das bedeutet, das die Bitfolge, die ein bestimmtes Zeichen darstellt, ist niemals ein Präfix der Bitfolge, die ein anderes Zeichen darstellt), dass das häufigst genutzte Quellenzeichen mit einem kürzeren Bitfolge als für ein weniger gerbrauchten Quellenzeichen genutzt wird, darstellt. Huffman war in der Lage, die effizienteste Komprimierungsmethode dieses Verfahrens zu entwickeln. Mit dieser Methode führt keine andere Zuordnung einzelner Quellenzeichen zu eindeutigen Bitfolgen zu einer kleineren durchschnittlichen Ausgabegröße wenn die tatsächliche Zeichenfrequenz mit denen übereinstimmen, die zum Erstellen des Codes verwendet wurden.
Huffman-Kodierung ist ein solch weitverbreitete Methode um Präfix-Codes zu erstellen, dass der Begriff „Huffman-Code“ ein oft genutztes Synonym ist für Präfix-Codes, obwohl der Huffman Algorithmus einen solchen Code gar nicht produziert
Dieses Verfahren funktioniert mit der Erstellung eines Binärbaums mit Knoten. Am Anfang sind alle Knoten Blattknoten, die das Zeichen, die Gewichtung (Häufigkeit des Auftretens) des Zeichens, und optional eine Verbindung zu einem übergeordneten Knotens, welches es das Lesen des Codes (in umgekehrter Reihenfolge) von einem Blattknoten vereinfacht. Interne Knoten enthalten Zeichengewichtung, Verknüpfung zu zwei untergeordneten Knoten, sowie optional eine Verknüpfung mit dem übergeordneten Knoten. Standardmäßig folgt das Bit „0“ dem linken untergeordneten, und das Bit „1“ dem rechten untergeordneten Knoten. Ein kompletierter Baum hat bis zu n- Blattknoten und n-1 interne Knoten. Ein Huffman-Baum, der nicht verwendete Zeichen weglässt, erzeugt die optimale Codelänge.
Der Prozess fängt eigentlich mit den Blattknote an, die die Wahrscheinlichkeiten des Zeichen, das sie darstellt, enthält. Ein neuer Knoten, deren Kindknoten die 2 mit den geringsten Wahrscheinlichkeiten, wird kreiert, sobald die Wahrscheinlichkeit des neuen Knotens ist gleich der Summe der Wahrscheinlichkeit der beiden Kindknoten. Die 2 vorherigen Knoten verbinden sich in einen neuen (und werden daher nicht weiter beachtet). Mit dem neuen Knoten nun beachtet, wiederholt sich dieser Prozess bis nur noch ein Knoten im Huffman-Baum übrig ist.
Kommentare