WikiDer > Huffman-Kodierung

Huffman-Codierung ist ein Verfahren zur optimalen und verlustfreien Verarbeitung von Daten bestehend aus einer Folge von Symbolen Kompresse. Das Codierung wird unter anderem verwendet für Datenkommunikation und für digitale Bilder. Huffman-Codierung ist benannt nach David Huffman, die in . kodiert 1952 erstmals beschrieben.

Jedes Symbol wird als Bitfolge codiert, so dass der Code eines Symbols niemals der erste Teil des Codes eines anderen Symbols ist. Dadurch ist es möglich, eine Reihe von Symbolen zu codieren, indem die Codes der einzelnen Symbole ohne Trennzeichen hintereinander platziert werden. Bei der Dekodierung einer Bitfolge folgt auf jeden erkennbaren Code der Beginn eines nächsten eindeutig erkennbaren Codes. Dies wird ein Präfix-Codierung oder präfixfreie Codierung.

Das Prinzip der Huffman-Codierung ist einfach. Von einer Reihe von Symbolen werden die häufig vorkommenden Symbole durch einen kürzeren Code dargestellt als die weniger verbreiteten. Auf diese Weise kann die gesamte Sequenz kürzer codiert werden.

Algorithmus

1. Listen Sie die Symbole in der zu komprimierenden Datei mit ihren Häufigkeiten in absteigender Reihenfolge auf (dazu 'Fetch-Forward-Codierung' verwendet werden).
2. Mach jetzt einen Baumstruktur wie folgt:
   1. Ordne die beiden Symbole mit der kleinsten Frequenz einem kombinierten Symbol zu, dessen Frequenz die Summe der beiden getrennten Frequenzen ist.
   2. Bringen Sie das kombinierte Symbol in die sortierte Liste zurück.
   3. Führen Sie die vorherigen 2 Schritte aus, bis ein einzelnes Symbol übrig bleibt.
3. Beginnend mit diesem letzten Symbol (dem Wurzel des Baum, Englisch: Wurzel und Baum): Codieren Sie die Zweige jetzt immer so, dass die höchste Frequenz eine 0 und die niedrigste eine 1 bekommt.

Der Huffman-Code eines Symbols ist jetzt die Liste von Bits (Einsen und Nullen), die Sie finden, wenn Sie das Symbol von der Wurzel des Baums aus nachschlagen. Dabei gilt: je höher die Frequenz, desto kürzer die (binär) Code. Auf diese Weise wird eine Kompression erreicht. Speichert man Klartext in (ASCII), dann belegen alle Zeichen im Text 1 Byte (von 8 Bit). Die Huffman-Codierung codiert Zeichen, die oft in einem Text vorkommen, in weniger Bits. Einige Zeichen, die im Text wenig (oder gar nicht) vorkommen, erhalten einen Code, der länger als 8 Bit ist (was keine Komprimierung verursacht), aber da diese Zeichen im Text seltener vorkommen als die Zeichen mit einer geringen Anzahl von Bits, es wird total komprimiert.

Das Obige setzt voraus, dass für jede Datei eine optimale Codierung abgeleitet und dann angewendet wird. Die Huffman-Codierung ist insofern optimal, als sie einen Symbolkettencode ergibt, der aus der kleinsten Anzahl von Bits im Vergleich zu anderen Präfixcodierungen und einer Codierung mit fester Länge besteht. Dabei ist nicht berücksichtigt, dass auch die Codierung selbst bzw. die Frequenzinformation, aus der sie abgeleitet werden kann, mehrere Bits benötigt.

Eine andere Möglichkeit besteht darin, eine Kodierung auf mehrere Dateien anzuwenden, basierend auf den Häufigkeiten in der Gesamtheit der Dateien. Dann ist die Huffman-Codierung optimal in dem Sinne, dass sie erwartet Die Anzahl der Bits der Codierung ist minimal.

Beispiel 1

Bei 3 Symbolen sind die Bitzahlen pro Code 1, 2 und 2, die erste für den Code des häufigsten Symbols. Selbst bei gleichen Frequenzen gibt es bereits eine Einsparung.

Beispiel 2

Bei 4 Symbolen sind die Bitzahlen pro Code 1, 2, 3 und 3, zum Beispiel 1, 01, 001 und 000, wenn die höchste Frequenz größer als die niedrigsten beiden kombiniert ist, ansonsten 2 für jedes Symbol, also 11, 10, 01 und 00.

Beispiel 3

In diesem Beispiel wird für jeden niederländischen Text eine Huffman-Codierung abgeleitet, ohne Leerzeichen und Satzzeichen zu berücksichtigen. Dies basiert auf den Buchstabenhäufigkeiten im Niederländischen.^[1]:

Buchstabenhäufigkeit auf Niederländisch

Brief	Häufigkeit (%)		Brief	Häufigkeit (%)		Brief	Häufigkeit (%)		Brief	Häufigkeit (%)
E	18,91		d	5,93		ich	2,21		C	1,24
Nein	10,03		so	3,73		SIE	1,99		f	0,81
ein	7,49		l	3,57		B	1,58		X	0,04
t	6,79		G	3,40		p	1,57		Ja	0,03
ich	6,50		V	2,85		W	1,52		Q	0,01
R	6,41		huh	2,38		J	1,46
Ö	6,06		k	2,25		z	1,39

Zuerst werden die beiden Buchstaben mit der niedrigsten Häufigkeit aus dieser Liste, das Y und das Q, kombiniert. Das Y bekommt eine 0 und das Q eine 1. Zusammen haben sie die Frequenz 0,04. Die resultierende Liste zeigt nun unten die Kombination YQ und das X. YQ bekommt eine 0 (Y also 00, Q 01) und X bekommt eine 1. Der Zweig XYQ hat eine Frequenz von 0,08 und die nächstniedrigere Frequenz ist 0,81 von F. Der F bekommt eine 0 und der Zweig mit XYQ eine 1 So fortfahrend wird das C mit der Frequenz 1,24 hinzugefügt. Das C bekommt eine 0 und der Zweig mit FXYQ eine 1. Der resultierende Zweig hat eine gemeinsame Frequenz von 2,13. Die beiden niedrigsten sind jetzt das J und Z, die die Blätter eines neuen Zweiges bilden. Dies wird fortgesetzt, bis der Baum vollständig ist. Das Endergebnis wird rechts mit der Häufigkeit an jedem Knoten angezeigt (der Baum wurde der Einfachheit halber um 90° gedreht; der obere Zweig ist immer '0', der untere Zweig ist '1') (Dies kommt nicht genau heraus bei 100 %, wahrscheinlich aufgrund von Rundungen in der Quelle, aus der die obige Tabelle entnommen wurde.)

Die erwartete Länge eines Codes für diese Codierung ist:${displaystyle sum { ext{freq}} imes { ext{length}}/sum { ext{freq}}=4{,}11}$

Codes mit fester Länge würden 5 Bits für jeden Buchstaben erfordern.

Beachten Sie, dass der kürzeste Code 11 für den Buchstaben E ist, der am häufigsten vorkommt. Keiner der anderen Codes beginnt mit 11 oder einem der anderen Codes. Es gibt beispielsweise Codes, die mit 0001 beginnen, aber 0001 selbst ist kein Code.

Dies erzeugt die folgende Huffman-Codierung:

In umgekehrter Reihenfolge der FrequenzQ 0001011101Y 0001011100X 000101111F 00010110C 0001010Z 101011J 101010W 011011P 011010B 001101U 001100M 000100K 10111H 10110V 10100G 01100L 00111S 00011D 1001O 1000R 0111I 0101T 0100A 0010N 0000E 11

In alphabetischer ReihenfolgeA 0010B 001101C 0001010D 1001E 11F 00010110G 01100H 10110I 0101J 101010K 10111L 00111M 000100N 0000O 1000P 011010Q 0001011101R 0111S 00011T 0100U 001100V 10100W 011011X 000101111Y 0001011100Z 101011

Zum Vergleich:

• Morse-Code ist auch eine verlustfreie Kodierung für Text. In diesem Fall ist der Code vieler Buchstaben der erste Teil des Codes eines anderen Buchstabens. Dies wird durch das Timing überwunden (der Buchstabenraum ist eine Pause ohne Signal).
• Bei 26 Zeichen gleicher Häufigkeit hätte bei der Huffman-Codierung 16 einen Code von 5 Bits, 4 einen Code von 4 Bits und 6 einen Code von 3 Bits. Die durchschnittliche Anzahl von Bits pro Zeichen beträgt dann 4.385.

Literatur

• (und) D. A. Huffman, "Eine Methode zur Konstruktion von Codes mit minimaler Redundanz", Proceedings of the I.R.E., Sept. 1952, S. 1098-1102