Ist Huffman Coding immer optimal?

Question

Die Anforderung der Codierung sein Präfix kostenlos führt zu großen Bäumen, da der Baum vollständig sein muss. Gibt es einen Schwellenwert, an dem eine nicht kodierte Speicherung von Daten mit fester Länge effizienter wäre als die Kodierung der Daten?

Answer 1

Die Entropie H(A) Denn dieses Problem ist 1.998. Sowohl die Codierung von Huffman als auch die Codierung der festen Länge für dieses Problem haben eine AVG -Codewortlänge als 2. Und zu Ihrer Information, die Codierung, die Sie mit Huffman -Codierung verwendet haben, ist falsch. Die Huffman -Codierung erzeugt auch Codes, die der festen Länge für dieses Problem ähneln. Es verwendet einen gierigen Ansatz. So a bekommt keinen Code als 0 aber stattdessen wird es 00. Überarbeiten Sie den Baum, den Sie mit Huffman -Codierung erzeugen. Der Baum, den Sie bekommen sollten, ist:

Answer 2

Ja, es ist immer optimal.

Nein, es gibt keinen Schwellenwert, an dem weniger Platz für die Verwendung nichtcodierter Daten mit fester Länge verwendet wird.

Ich habe eine Reihe von Beweisen im Web gefunden, aber es gibt eine ausreichende Diskussion in Der Wikipedia -Artikel Huffman -Codierung.

Dies deckt auch andere Techniken ab, die eine höhere Komprimierung erzielen (außerhalb des Raums, für den der Huffman -Code optimal ist).

Answer 3

Die Huffman -Codierung nähert sich der Bevölkerungsverteilung mit zwei Wahrscheinlichkeiten an. Wenn die wahre Verteilung aus Kräften von zwei Wahrscheinlichkeit besteht (und die Eingangsymbole vollständig unkorreliert sind), ist die Huffman -Codierung optimal. Wenn nicht, können Sie mit der Reichweite besser abschneiden. Es ist jedoch unter allen Codierung optimal, die bestimmte Symbole in der Eingabe bestimmte Bitssätze zuweisen.