Verwirrt über Huffman-Bäume

Question

A quick tutorial on generating a huffman tree

Verwirrt über Huffman-Bäume. Am Ende dieses Links oben zeigt es den Baum mit 2 Elementen und dann den fertigen Baum. Ich bin verwirrt über die Art, wie es verzweigt ist. Gibt es eine bestimmte Art, wie ein Huffman-Baum verzweigt werden muss?

Zum Beispiel 57: * mit seinem rechten Kind 35: * ist nach rechts abgezweigt. Könnte es nach links verzweigt sein, 22 nach rechts verzweigt? Auch, warum wurde nicht 22: * gepaart mit 15: 4 - es nur gepaart mit 20: 5, um einen neuen Baum zu erstellen.

Aus anfänglichen Beobachtungen scheint es, dass der Baum nicht ausgeglichen sein muss oder eine bestimmte Reihenfolge haben muss, außer dass die Häufigkeiten eines Blattes sich zum Wert des Elternknotens addieren. Könnten zwei Personen, die einen Huffman-Baum mit den gleichen Daten erstellen, unterschiedliche Kodierungswerte erhalten?

Answer 1

Der Schlüssel zum Huffman Bäume ist dies:

sortieren diese Liste nach Häufigkeit und machen die zwei niedrigsten Elemente in Blätter

Wenn Sie mehr als zwei Elemente aufweisen, die haben niedrigste Frequenz (zB 3,4,4 ...), jede zwei wird tun (3 und jede von 4s - nicht zwei 4s). Es ist auch nicht wichtig, welches dieser niedrigsten Elemente mit 0 und welches mit 1 belegt ist. Diese beiden Tatsachen erlauben es, dass unterschiedliche, jedoch gültige Huffman-Codierungen aus den gleichen Daten entstehen.

Der Huffman-Baum soll durch Frequenzen ausgeglichen werden, nicht durch die Anzahl der Knoten. Somit ist die folgende ausgeglichene:

(100 (50 (25 (12 (12 1))))) 

und dies ist nicht:

(((100 50) 25) ((12 12) 1))) 

Insbesondere in Frage, 15 mit 20 gepaart ist und nicht 22, da 15 und 20 sind die beiden niedrigsten verbleibenden Werte (beide niedriger als 22). Jede Verzweigung (links oder rechts) wäre in Ordnung gewesen, solange sie konsistent ist (immer kleiner-links oder immer kleiner-rechts, innerhalb desselben Algorithmus, so dass die Kodierung am anderen Ende rekonstruiert werden kann).

Answer 2

Alles wird auf der Seite erklärt. 22: * wurde nicht mit 15: 4 verknüpft, da in jedem Schritt zwei Knoten mit den niedrigsten Elementen kombiniert werden. Dies erzeugt eine eindeutige Reihenfolge.

Huffman-Codes können unterschiedlich sein (wenn Sie mehrere Werte mit der gleichen Frequenz haben oder 0 und 1-Darstellung von links/rechts austauschen), aber Huffman-Längen können nicht sein.

Die Verzweigung nach links/rechts ist nur eine Frage des Zeichnens des Baums oder der graphischen Darstellung, also spielt dies keine Rolle.

Answer 3

Die Pfosten sind so viel falsch und irreführend: Die Wahl der Blätter mit gleichen Gewichten tut Materie und sie ändern sich, wie gut sie Daten zu komprimieren.

Hier ist ein Gegenbeispiel, das zeigt, wie die verschiedenen Möglichkeiten zu unterschiedlichen Komprimierungsraten führen: ABBBCCCDDDDEEEEEEEE

A: 1 B: 3, C: 3, D 4, E: 8. Erster Schritt: Nimm A und B, um einen Knoten mit Gewicht 4 zu bilden. Zweiter Schritt:

Wenn Sie den neu erstellten Knoten im ersten Schritt mit C nehmen, dann bekommen Sie (19 (11 (7 (4 (1-A) (3-B)) (3-C)) (4-D)) (8-E)), die 37-Bit-komprimierte Daten gibt.

Wenn Sie andererseits D nehmen, das auch das Gewicht 4 hat, anstelle des neu erstellten Knotens, erhalten Sie (19 (11 (4 (1-A) (3-B)) (7 (3-C) (4-D))) (8-E)), die 41-Bit komprimierte Daten gibt.