Länge der Binärcodierung im Huffman-Algorithmus?

Was ist die Länge der längsten binären Codierung, die auftritt, wenn Huffmans Algorithmus mit den Gewichten 10, 10, 10, 10, 15, 15, 50 verwendet?Länge der Binärcodierung im Huffman-Algorithmus?

Gibt es einen schnellen Weg, um dies oder tun zu tun, muss ich den Baum bauen und dann die durchschnittliche Anzahl von Bits zu berechnen, die ich würde raten:

= Gesamtlänge/Anzahl der Bits

Diese I ist der Baum generierte:

Quelle

2016-06-12 Square-root

Nun, Ja, es gibt einen schnellen Weg. Mit nur sieben Gewichten braucht man ungefähr eine Minute, um den Baum mit Bleistift und Papier zu zeichnen. Angenommen, Sie verstehen den Huffman-Codierungsalgorithmus. –

@jim Ich habe den Baum erstellt. Wie gehe ich jetzt vor? –

Ja, du musst den Baum machen. Sie können eine untere Schranke von der Entropie finden, die das Negative der Summe der Wahrscheinlichkeiten mal dem Log (Basis 2) der Wahrscheinlichkeiten ist. –

die Länge der längsten Binärkodierung die auftritt, wenn Huffman-Algorithmus verwendet, ist gleich die Höhe des Baumes, der in diesem Fall 4. So längste Länge woul sein d 4.

Es ist leicht zu sehen, dass, wenn Sie 0 nach links Zweig zuweisen und 1 bis rechten Zweig (Sie es auch umgekehrt zu tun), würden die Codes:

Quelle

2016-06-12 04:57:29

Länge der Binärcodierung im Huffman-Algorithmus?

Antwort

Verwandte Themen