Shannon Entropia 0,922, 3 odrębne wartości

Biorąc pod uwagę ciąg wartości , Shannon Entropy w bazie log  wynosi . Z tego, co rozumiem, w bazie  Entropia Shannona zaokrąglona w górę to minimalna liczba bitów w systemie binarnym, która reprezentuje jedną z wartości.$AAAAAAAABC$$2$$0.922$$2$

Zaczerpnięte ze wstępu na tej stronie Wikipedii:

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

Jak więc trzy wartości mogą być reprezentowane przez jeden bit?  może wynosić  ,  może wynosić  ; ale jak mógłbyś reprezentować  ?$A$$1$$B$$0$$C$

Z góry dziękuję.

Obliczona entropia nie jest tak naprawdę dla konkretnego ciągu, ale raczej dla losowego źródła symboli, które generuje $A$ z prawdopodobieństwem  $\tfrac{8}{10}$ oraz$B$i $C$z prawdopodobieństwem $\tfrac1{10}$ sztuk, bez korelacji między kolejnymi symbolami. Obliczona entropia dla tego rozkładu$0.922$oznacza, że ​​nie można reprezentować ciągów wygenerowanych z tego rozkładu przy użyciu mniej niż$0.922$bitów na znak.

Opracowanie kodu, który osiągnie ten wskaźnik, może być dość trudne. ^* Na przykład kodowanie Huffmana przydzieli kody $0$ , $10$ i  $11$ do $A$ , $B$ i  $C$ , średnio po $1.2$  bitu na znak. Jest to dość dalekie od entropii, choć wciąż o wiele lepsze niż naiwne kodowanie dwóch bitów na znak. Każda próba lepszego kodowania będzie prawdopodobnie wykorzystać fakt, że nawet biegać dziesięć kolejnych S jest bardziej prawdopodobne (prawdopodobieństwo 0,107 ) niż jednym  pensjonatów .$A$$0.107$$B$

---

^* Okazuje się, że nie jest trudno zbliżyć się tak blisko, jak chcesz - zobacz pozostałe odpowiedzi!

Oto konkretne kodowanie, które może reprezentować każdy symbol średnio w mniej niż 1 bit:

Najpierw podziel ciąg wejściowy na pary kolejnych znaków (np. AAAAAAAABC staje się AA | AA | AA | AA | BC). Następnie zakoduj AA jako 0, AB jako 100, AC jako 101, BA jako 110, CA jako 1110, BB jako 111100, BC jako 111101, CB jako 111110, CC jako 111111. _{Nie powiedziałem, co się stanie, jeśli wystąpi nieparzysta liczbę symboli, ale można po prostu zakodować ostatni symbol za pomocą dowolnego dowolnego kodowania, tak naprawdę nie ma znaczenia, kiedy wejście jest długie.}

Jest to kod Huffmana do dystrybucji niezależnych par symboli i odpowiada wybraniu $n = 2$ w odpowiedzi Yuvala. Większe $n$ prowadziłoby do jeszcze lepszych kodów (zbliżając się do entropii Shannona w limicie, jak wspomniał).

Średnia liczba bitów na parę symboli dla powyższego kodowania wynosi

$$\frac{8}{10} \cdot \frac{8}{10} \cdot 1 + 3 \cdot \frac{8}{10} \cdot \frac{1}{10} \cdot 3 + \frac{1}{10} \cdot \frac{8}{10} \cdot 4 + 4 \cdot \frac{1}{10} \cdot \frac{1}{10} \cdot 6 = 1.92$$ tj.$1.92/2 = 0.96$bitów na symbol, nie tak daleko od entropii Shannona w rzeczywistości dla takiego prostego kodowania.

$\mathcal{D}$$\{A,B,C\}$$X \sim \mathcal{D}$$\Pr[X=A] = 4/5$$\Pr[X=B]=\Pr[X=C]=1/10$

$n$$C_n\colon \{A,B,C\}^n \to \{0,1\}^*$

$$\lim_{n\to\infty} \frac{\operatorname*{\mathbb{E}}_{X_1,\ldots,X_n \sim \mathcal{D}}[C_n(X_1,\ldots,X_n)]}{n} = H(\mathcal{D}).$$

$\mathcal{D}$$H(\mathcal{D}) \approx 0.922$$A$

$A^8BC$