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

14

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.AAAAAAAABC20.9222

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ć  ?A1B0C

Z góry dziękuję.

Sean C.
źródło

Odpowiedzi:

16

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  810 orazBCz prawdopodobieństwem 110 sztuk, bez korelacji między kolejnymi symbolami. Obliczona entropia dla tego rozkładu0.922oznacza, że ​​nie można reprezentować ciągów wygenerowanych z tego rozkładu przy użyciu mniej niż0,922bitó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 , 1011 do ZA , bdo , ś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 .ZA0,107b


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

David Richerby
źródło
18

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

8108101+38101103+1108104+41101106=1.92
tj.1.92/2=0.96bitów na symbol, nie tak daleko od entropii Shannona w rzeczywistości dla takiego prostego kodowania.

koczownik
źródło
13

re{ZA,b,do}XrePar[X=ZA]=4/5Par[X=b]=Par[X=do]=1/10

ndon:{ZA,b,do}n{0,1}

limnmiX1,,Xnre[don(X1,,Xn)]n=H.(re).

reH.(re)0,922ZA

ZA8bdo

Yuval Filmus
źródło