Ist die Huffman-Codierung immer optimal?

9

Die Anforderung, dass die Codierung präfixfrei sein muss, führt zu großen Bäumen, da der Baum vollständig sein muss. Gibt es einen Schwellenwert, bei dem die nicht codierte Speicherung von Daten mit fester Länge effizienter wäre als die Codierung der Daten?

information-theory data-compression Kaveh
quelle
Im Allgemeinen "nein". Für durchschnittliche Daten wäre die Häufigkeit jedes Zeichens> 1 und es ist gut, Huffman-Codierung anstelle von Codes mit fester Länge zu verwenden
@arunmoezhi Könnten Sie bitte das Beispiel ansprechen, das ich oben angegeben habe? Die Häufigkeit jedes Zeichens ist größer als 1, die feste Länge ist jedoch optimaler.
Dieses Beispiel ist interessant. Aber können Sie ein solches Szenario mit den Wahrscheinlichkeiten jedes Zeichens anstelle der Häufigkeit versehen und sicherstellen, dass die Wahrscheinlichkeiten aller Zeichen zu 1
@arunmoezhi Ich habe die Wahrscheinlichkeiten der Zeichen aufgenommen und sie addieren sich zu 1.

Antworten:

4

Die Entropie H(A)für dieses Problem ist 1.998. Sowohl die Huffman-Codierung als auch die Codierung mit fester Länge für dieses Problem haben eine durchschnittliche Codewortlänge von 2. Und zu Ihrer Information, die Codierung, die Sie mit Huffman Encoding erhalten haben, ist falsch. Die Huffman-Codierung erzeugt für dieses Problem auch Codes, die der festen Länge ähneln. Es verwendet einen gierigen Ansatz. Erhält aalso keinen Code als, 0sondern stattdessen 00. Überarbeiten Sie den Baum, den Sie mit Huffman Coding generieren. Der Baum, den Sie bekommen sollten, ist:Geben Sie hier die Bildbeschreibung ein

Arunmoezhi
quelle
Vielen Dank. Könnten Sie einen Beweis dafür liefern, dass die Huffman-Codierung immer optimaler ist als die feste Länge, oder mich zumindest auf einen verweisen?
1
Sie können beziehen Introduction to Algorithmsdurch CLRS. In dem Kapitel, das darüber spricht greedy algorithms, können Sie den formalen Beweis dafür erhalten Huffman algorithm. Es ist ein langer Beweis und braucht Geduld zum Lesen.
8

Die Huffman-Codierung approximiert die Bevölkerungsverteilung mit Potenzen von zwei Wahrscheinlichkeiten. Wenn die wahre Verteilung aus Potenzen mit zwei Wahrscheinlichkeiten besteht (und die Eingabesymbole vollständig unkorreliert sind), ist die Huffman-Codierung optimal. Wenn nicht, können Sie die Bereichskodierung verbessern. Es ist jedoch unter allen Codierungen optimal, die bestimmten Symbolen in der Eingabe bestimmte Sätze von Bits zuweisen.

Antimon
quelle
Was meinst du mit "approximiert die Bevölkerungsverteilung"?
3
Es gibt eine theoretische wahre Verteilung der Nachricht, die hypothetisch gesendet werden könnte. Im Idealfall sollte jede Nachricht auf eine Weise codiert werden, die proportional zum Protokoll ihrer Wahrscheinlichkeit ist. Da Huffman-Codes jedoch eine ganzzahlige Anzahl von Bits sind, entspricht dies implizit Wahrscheinlichkeiten mit Zweierpotenzen. Daher eine Annäherung. Schlagen Sie den Shannons-Codierungssatz nach.
8

Ja, es ist immer optimal.

Nein, es gibt keinen Schwellenwert, bei dem weniger Speicherplatz für die Verwendung nicht codierter Daten fester Länge benötigt würde.

Ich habe eine Reihe von Beweisen im Web gefunden, aber es gibt genügend Diskussionen im Wikipedia-Artikel Huffman-Codierung .

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

Cade Roux
quelle