| Symbol | Anzahl | Code | Bit | Bit insgesamt |
|---|
Huffman-Codierer
Warum sollte ein häufiger Buchstabe wie e so viele Bit belegen wie ein seltener wie q? Die Huffman-Codierung gibt häufigen Symbolen kurze und seltenen lange Codes, und zwar auf die bestmögliche Weise. Geben Sie einen Text ein oder wählen Sie ein Beispiel und bauen Sie seinen Huffman-Baum Schritt für Schritt auf: Die zwei leichtesten Bäume verbinden sich unter einem neuen Knoten, immer wieder, bis nur noch ein Baum übrig ist. Dann ergibt jeder Pfad von oben einen Code, und Sie können jedes Symbol durch die codierten Bits verfolgen. Geben Sie einen Text ein oder wählen Sie ein Beispiel. Jedes Symbol beginnt als Blatt mit seiner Anzahl. Gehen Sie den Aufbau Schritt für Schritt durch: Jeder Schritt verbindet die zwei leichtesten Bäume unter einem neuen Knoten mit ihrer Summe, bis nur noch ein Baum übrig ist. Dann ergibt der Pfad von oben zu einem Blatt dessen Code, 0 für links und 1 für rechts. Klicken Sie auf ein Blatt, eine Zeile oder ein Stück der Bitfolge, um ein Symbol zu verfolgen, und vergleichen Sie die Summe mit einem Code fester Länge und mit der Entropie.
Wie es funktioniert
- Geben Sie einen Text ein, fügen Sie ihn ein oder wählen Sie ein Beispiel wie ABRACADABRA oder MISSISSIPPI RIVER.
- Gehen Sie den Aufbau mit „Nächster Schritt“ durch oder drücken Sie „Abspielen“: Jeder Schritt verbindet die zwei leichtesten Bäume unter einem Knoten mit ihrer Summe.
- Wenn der Baum fertig ist, klicken Sie auf ein Blatt, eine Zeile der Tabelle oder ein Stück der Bitfolge, um ein Symbol zu verfolgen, und vergleichen Sie die Summen in den Kacheln.
Wie der Baum entsteht
Zählen Sie, wie oft jedes Symbol vorkommt, und machen Sie aus jedem einen Baum aus einem einzigen Blatt, gewichtet mit seiner Anzahl. Wiederholen Sie dann einen einfachen Schritt: Nehmen Sie die zwei Bäume mit den kleinsten Gewichten und hängen Sie sie unter einen neuen Knoten, dessen Gewicht ihre Summe ist. Jeder Schritt lässt einen Baum weniger übrig, sodass nach n − 1 Schritten bei n Symbolen ein einziger Baum bleibt. Die seltenen Symbole wurden zuerst verbunden und sitzen tief unten; die häufigen wurden spät verbunden und sitzen nahe der Spitze.
Die Codes ablesen
Gehen Sie von oben nach unten: Ein Schritt nach links fügt eine 0 an, ein Schritt nach rechts eine 1. Der Pfad zu einem Blatt ist der Code dieses Symbols. Weil Symbole nur an den Blättern sitzen, ist kein Code der Anfang eines anderen, und eine Bitfolge lässt sich ohne Trennzeichen decodieren: Folgen Sie den Bits im Baum nach unten, und wann immer Sie ein Blatt erreichen, schreiben Sie sein Symbol und beginnen oben von vorn. Für ABRACADABRA braucht Huffman 23 Bit, gegenüber 33 für einen festen Code mit 3 Bit pro Buchstabe.
Häufig gestellte Fragen
Warum ist der Huffman-Code der bestmögliche?
Unter allen Codes, die jedem Symbol eine eigene Folge ganzer Bits geben, hat keiner für die gegebenen Anzahlen eine kürzere Gesamtlänge. Der Beweis folgt der Konstruktion: In einem optimalen Code lassen sich die zwei seltensten Symbole immer zu Geschwistern auf der tiefsten Ebene machen, und wenn man sie verbindet, bleibt ein kleineres Problem derselben Art übrig. Die Gesamtzahl der Bits ist gleich der Summe der Gewichte aller inneren Knoten des Baums.
Was ist ein Präfixcode?
Ein Code, in dem kein Codewort der Anfang eines anderen ist, etwa 0, 10, 110 und 111. Diese Eigenschaft erlaubt es einem Decoder, einen Bitstrom ohne Trennzeichen zu lesen, weil er immer weiß, wo ein Codewort endet. Jeder Huffman-Code ist ein Präfixcode: Die Symbole sitzen nur an den Blättern des Baums.
Ist der Huffman-Baum eindeutig?
Nicht ganz: Wenn zwei Bäume dasselbe Gewicht haben, kann jeder von beiden zuerst genommen werden, und links und rechts lassen sich vertauschen. Verschiedene Entscheidungen ergeben verschiedene Codes, aber immer dieselbe Gesamtzahl an Bits. Der Codierer entscheidet bei Gleichstand immer auf dieselbe Weise, sodass ein Text immer denselben Baum ergibt.
Wie nahe kommt Huffman an die Entropie heran?
Die mittlere Codelänge ist mindestens so groß wie die Entropie und weniger als ein Bit größer. Sie ist gleich der Entropie, wenn jede Wahrscheinlichkeit eine Potenz von einhalb ist, wie im Beispiel mit den halbierten Anzahlen. Die arithmetische Codierung und moderne Range-Coder umgehen die Grenze ganzer Bits und kommen noch näher heran.
Wird mein Text irgendwohin gesendet?
Nein. Der Baum und die Codes werden in Ihrem Browser berechnet, und Ihr Text bleibt im lokalen Speicher dieses Browsers.
Bereit, es auszuprobieren?
Öffnen Sie PictorX in Ihrem Browser – keine Installation, zum Starten ist keine Kreditkarte erforderlich.
Zum Editor