Shannon-Entropie von 0,922, 3 verschiedene Werte

14

Bei einer Reihe von Werten , der Shannon Entropy in Log - Basis  zu kommen . Soweit ich weiß, ist die aufgerundete Shannon-Entropie in Basis  die minimale Anzahl von Binärbits, um einen einzelnen der Werte darzustellen.AAAAAAAABC20.9222

Entnommen aus der Einführung auf dieser Wikipedia-Seite:

https://en.wikipedia.org/wiki/Entropy_%28information_theory%29

Wie können also drei Werte durch ein Bit dargestellt werden?  könnte  ,  könnte  ; aber wie könnten Sie  ?A1B0C

Danke im Voraus.

Sean C
quelle

Antworten:

16

Die Entropie, die Sie berechnet haben, gilt nicht für die bestimmte Zeichenfolge, sondern für eine zufällige Quelle von Symbolen, die mit der Wahrscheinlichkeit  und und  mit der Wahrscheinlichkeit  1 generiertEIN810BC110Jeweils 10 , ohne Korrelation zwischen aufeinanderfolgenden Symbolen. Die berechnete Entropie für diese Verteilung von0,922bedeutet, dass Sie aus dieser Verteilung generierte Zeichenfolgen nicht mitdurchschnittlichweniger als0,922Bit pro Zeichen darstellen können.

Es könnte ziemlich schwierig sein, einen Code zu entwickeln, der diese Rate erreicht. * Zum Beispiel würde die Huffman-Codierung die Codes 0 , 10 und  11 für EIN , B und  C für einen Durchschnitt von 1.2  Bits pro Zeichen zuweisen . Das ist ziemlich weit von der Entropie entfernt, obwohl es immer noch viel besser ist als die naive Codierung von zwei Bits pro Zeichen. Jeder Versuch, eine bessere Codierung wird wahrscheinlich die Tatsache ausnutzen , dass auch ein Lauf von zehn aufeinander folgenden EIN s mehr wahrscheinlich (Wahrscheinlichkeit 0,107 ) als ein einzelnes  B .


* Es stellt sich heraus, dass es nicht schwer ist, so nah wie Sie wollen zu kommen - sehen Sie sich die anderen Antworten an!

David Richerby
quelle
18

Hier ist eine konkrete Codierung, die jedes Symbol im Durchschnitt in weniger als 1 Bit darstellen kann:

Teilen Sie zuerst die Eingabezeichenfolge in aufeinanderfolgende Zeichenpaare auf (z. B. AAAAAAAABC wird zu AA | AA | AA | AA | BC). Dann codiere AA als 0, AB als 100, AC als 101, BA als 110, CA als 1110, BB als 111100, BC als 111101, CB als 111110, CC als 111111. Ich habe nicht gesagt, was passiert, wenn es eine ungerade gibt Anzahl der Symbole, aber Sie können nur das letzte Symbol mit einer beliebigen Codierung codieren. Es ist eigentlich egal, wann die Eingabe lang ist.

Dies ist ein Huffman-Code für die Verteilung unabhängiger Symbolpaare und entspricht der Wahl von n=2 in Yuvals Antwort. Größeres n würde zu noch besseren Codes führen (Annäherung an die Shannon-Entropie im Grenzbereich, wie er erwähnte).

Die durchschnittliche Anzahl von Bits pro Symbolpaar für die obige Codierung beträgt

8108101+38101103+1108104+41101106=1,92
dh1,92/2=0,96Bits pro Symbol, nicht so weit von der Shannon-Entropie entfernt, wie dies für eine solch einfache Codierung der Fall ist.

nomadictype
quelle
13

Sei D die folgende Verteilung über {EIN,B,C} : wenn XDPr[X=EIN]=4/5Pr[X=B]=Pr[X=C]=1/10

Für jedes n wir Präfixcodes Cn:{EIN,B,C}n{0,1} konstruieren : { A , B , C } n{ 0 , 1 } ∗, so dass

limnEX1,,XnD[Cn(X1,,Xn)]n=H(D).

DH(D)0,922EIN

EIN8BC

Yuval Filmus
quelle