Wie gut ist der Huffman-Code, wenn keine großen Wahrscheinlichkeitsbuchstaben vorhanden sind?

Der Huffman-Code für eine Wahrscheinlichkeitsverteilung ist der Präfixcode mit der minimalen gewichteten durchschnittlichen Codewortlänge , wobei die Länge des ten Codeworts ist. Es ist ein bekanntes Theorem, dass die durchschnittliche Länge pro Symbol des Huffman-Codes zwischen und , wobei die Shannon-Entropie ist der Wahrscheinlichkeitsverteilung. $p$ $\sum p_i \ell_i$ $\ell_i$ $i$ $H(p)$ $H(p)+1$ $H(p) = -\sum_i \, p_i \log_2 p_i$

Das kanonisch schlechte Beispiel, bei dem die durchschnittliche Länge die Shannon-Entropie um fast 1 überschreitet, ist eine Wahrscheinlichkeitsverteilung wie , bei der die Entropie nahezu 0 ist und die durchschnittliche Codewortlänge 1 beträgt eine Lücke zwischen der Entropie und der Codewortlänge von fast . $\{.999, .001\}$ $1$

Aber was passiert, wenn die Wahrscheinlichkeitsverteilung an die größte Wahrscheinlichkeit gebunden ist? Angenommen, alle Wahrscheinlichkeiten sind kleiner als . Die größte Lücke, die ich in diesem Fall finden konnte, ist für eine Wahrscheinlichkeitsverteilung wie , bei der die Entropie etwas mehr als 1 und die durchschnittliche Codewortlänge etwas weniger als 1,5 beträgt, was a ergibt Lücke nähert sich . Ist das das Beste, was du tun kannst? Können Sie eine Obergrenze für die Lücke angeben, die in diesem Fall streng unter 1 liegt? $\frac{1}{2}$ $\{.499, .499, .002\}$ $0.5$

Betrachten wir nun den Fall, in dem alle Wahrscheinlichkeiten sehr klein sind. Angenommen , Sie eine Wahrscheinlichkeitsverteilung über wählen Buchstaben, von denen jede Wahrscheinlichkeit . In diesem Fall tritt die größte Lücke auf, wenn Sie wählen . Hier erhalten Sie eine Lücke von ungefähr Ist dies das Beste, was Sie in einer Situation tun können, in der alle Wahrscheinlichkeiten gering sind? $M$ $1/M$ $M \approx 2^k \ln 2$

\frac{1 + \ln \ln 2 - \ln 2}{\ln 2} \approx 0.08607.

$\frac{1 + \ln \ln 2 - \ln 2}{\ln 2} \approx 0.08607.$

Diese Frage wurde von dieser TCS Stackexchange-Frage inspiriert .

optimization it.information-theory coding-theory Peter Shor
quelle

Antworten:

Es gibt viele Artikel, die genau das Problem untersuchen, das Sie ansprechen. Die erste in der Reihe ist ein Artikel von Gallager, "Variations on a Theme von Huffman", IEEE-IT, vol. 24, 1978, S. 668-674. Er beweist , dass die Differenz zwischen der durchschnittlichen Codewortlänge eines Huffman - Codes und der Entropie (er nennt diese Menge „Redundanz“) ist immer streng kleiner als (= größte Wahrscheinlichkeit in der Wahrscheinlichkeitsverteilung) im Fall und es ist weniger als , wenn . Bessere Grenzen sind bekannt, Sie können sie in den zahlreichen Artikeln finden, die Gallager Arbeiten zitieren. $p$ $p\geq 1/2$ $p+0.086$ $p<1/2$

Ugo
quelle

Die optimale Grenze wurde von Manstetten gefunden. Enge Grenzen für die Redundanz von Huffman-Codes .

Yuval Filmus

Nach der Grenze von urteilen , haben Sie vermutlich beabsichtigt, eine andere Frage zu stellen ... oder Sie haben einfach nicht angegeben, wie Sie den "Durchschnitt" nehmen. Also werde ich beides beantworten. Die Antwort ist nein auf beide Fragen. $H(p) \leq \ldots \leq H(p)+1$

Wenn Sie die durchschnittliche Codelänge unter Verwendung einer gleichmäßigen Verteilung über Codewörter definieren und als obere Grenze für die Wahrscheinlichkeit eines Elements verwenden, betrachten Sie zunächst den Längencode mit Codewörter haben die Länge und die verbleibenden haben die Länge . Für die durch diesen Code perfekt codierte Verteilung nähert sich die durchschnittliche Länge , es sei denn, Sie haben auch eine Untergrenze für die Wahrscheinlichkeit eines Elements, während die Entropie . $2^{-q}$ $q+k$ $2^{q-1}$ $q$ $2^{q+k-1}$ $q+k$ $q+k$ $q+\frac{k}{2}$

Betrachten wir nun die "durchschnittliche Länge", dh die durchschnittliche Codewortlänge, wenn der Huffman-Code zum Codieren von . Hier ist die Schranke eng, und eine beispielhafte Verteilung, die diese Grenze erreicht, ist eine, bei der jedes Element mit einer Wahrscheinlichkeit von für auftritt(Dem letzten Element wird eine Restwahrscheinlichkeit zugewiesen, die jedoch asymptotisch keinen Unterschied macht.) $p$ $2^{q\pm 1/2}$ $q \in {\mathbb Z}.$

Betrachten Sie zum Beispiel Dann $q = 7.$

$A + B = 128, A\sqrt{2}+B/\sqrt{2}\leq 128, \max_{A \in {\mathbb Z}} A$ ergibt . Unsere Distribution hat Elemente mit einer Wahrscheinlichkeit von , mit einer Wahrscheinlichkeit von und ein Element erhält die Reste. $A = 52, B = 76$ $52$ $2^{-6.5}$ $76$ $2^{-7.5}$

Dann ist , während der Huffman-Code einen Entropieverlust von . (Übrigens hat der Entropieverlust einen Namen, egal ob Sie Huffman-Codierung oder beliebige Codierung für : die Kullback-Liebler-Divergenz . Ich habe vor ein paar Tagen herausgefunden, dass die Verwendung zu engeren doppelseitigen Chernoff-Grenzen führt, wie Sie auf Wikipedia für Chernoff-Grenzen sehen können.) $H(X) = (52\cdot 6.5 + 76 \cdot 7.5)/128 = 7.09375$ $(52 \cdot 0.5 - 76 \cdot 0.5)/128 \approx 0.99436$ $Q$ $D(P\Vert Q) = \sum p_i \log \frac{p_i}{q_i} + \sum (1-p_i) \log \frac{1-p_i}{1-q_i}$

Carl
quelle

Dieses zweite Beispiel verblüfft mich ein wenig. Wenn Sie 128 Codewörter haben, gibt es einen Code mit einer durchschnittlichen Wortlänge von 7 (tatsächlich haben alle Wortlängen 7), was Ihrer Aussage, dass die Entropie 7.09375 ist, widerspricht. Die Entropie dieser Verteilung (die Sie erhalten, indem Sie einen gewichteten Durchschnitt von und keinen Durchschnitt nehmen) beträgt 6,88, während die durchschnittliche Länge des Huffman-Codes 7 beträgt. Dies ergibt eine Lücke (oder Kullback-Liebler-Divergenz) von um 0.12, was ziemlich viel besser zu sein scheint als mein Beispiel, aber nicht nahe am 1.

- \log_{2} p_{i}

$-\log_2 p_i$

Peter Shor

Und in der Tat hast du recht. Ich wollte nach der erwarteten Codewortlänge unter der Wahrscheinlichkeitsverteilung fragen .

p

$p$

Peter Shor

Hoppla, ich habe mich über gegen verrechnet . Wir wollen weiterhin, dass etwas kleiner als , aber so etwas wie , um die kleineren Einträge in die untere Zeile zu zwingen. Dies ergibt

A

$A$

B

$B$

A \sqrt{2} + B / \sqrt{2}

$A\sqrt{2}+B/\sqrt{2}$

2^{k}

$2^k$

A + 2 B = 2^{k}

$A+2B=2^k$

A = \frac{2 - 1 / \sqrt{2}}{\sqrt{2} - 1} B .

$A = \frac{2-1/\sqrt{2}}{\sqrt{2}-1}B.$

Carl

Eigentlich wäre das ... aber dieses Gleichungssystem hat keine positive Lösung - es scheint, dass wir nicht alles zu einer halben ganzen Potenz von zwingen können . Anstelle von und wir z. B. für die Hälfte des Huffman-Codes und berücksichtigen. für den Rest Einträge geben ...

2 A + B

$2A+B$

2

$2$

\sqrt{2}

$\sqrt{2}$

1 / \sqrt{2}

$1/\sqrt{2}$

(1 + x) / 2^{k}

$(1+x)/2^k$

(1 - x) / 2^{k + 1}

$(1-x)/2^{k+1}$

3 * 2^{k}

$3*2^k$

Carl

Probieren Sie dies aus (nicht optimal - das hängt vermutlich davon ab, wie Sie ab- oder aufrunden möchten). Einträge mit einer Wahrscheinlichkeit von und Einträge mit einer Wahrscheinlichkeit von eine Entropie von . Ändern Sie dies stattdessen in Einträge mit einer Wahrscheinlichkeit von und Einträge mit einer Wahrscheinlichkeit von . Die Entropie dieser Verteilung beträgt 5,802, was 6,4023 ergibt, während die Entropie des Huffman-Codes unter Uniform 7,5 beträgt, undWenn ich mich also nicht verrechnet habe (und das tue ich oft), ergibt sich eine Lücke von ungefähr

64

$64$

1 / 128

$1/128$

128

$128$

1 / 256

$1/256$

7.5

$7.5$

64

$64$

1 / 128 \sqrt{2}

$1/128\sqrt{2}$

128

$128$

1 / 256 (2 - 1 / \sqrt{2})

$1/256(2-1/\sqrt{2})$

1 / (2 \sqrt{2}) * 7.5 + (1 - 1 / (2 \sqrt{(} 2))) * 5.802

$1/(2\sqrt{2})*7.5+(1-1/(2\sqrt(2)))*5.802$

(1 - 2^{- 1.5}) * 7 + 2^{- 1.5} * 8 = 7.3535.

$(1-2^{-1.5})*7+2^{-1.5}*8 = 7.3535.$

0.95

$0.95$ .

Carl