Shannon Entropy dari 0,922, 3 Nilai Berbeda

14

Diberikan serangkaian nilai , Shannon Entropy di log base  mencapai . Dari apa yang saya mengerti, dalam basis  Shannon Entropy dibulatkan adalah jumlah minimum bit dalam biner untuk mewakili satu nilai.AAAAAAAABC20.9222

Diambil dari pengantar di halaman wikipedia ini:

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

Jadi, bagaimana tiga nilai diwakili oleh satu bit?  bisa  ,  bisa  ; tetapi bagaimana Anda bisa mewakili  ?A1B0C

Terima kasih sebelumnya.

Sean C
sumber

Jawaban:

16

Entropi yang Anda hitung sebenarnya bukan untuk string spesifik tetapi, lebih tepatnya, untuk sumber simbol acak yang menghasilkan A dengan probabilitas  810 , danBdan Cdengan probabilitas 110 masing-masing, tanpa korelasi antara simbol berturut-turut. Entropi yang dihitung untuk distribusi ini,0.922berarti Anda tidak dapat mewakili string yang dihasilkan dari distribusi ini menggunakan rata-rata kurang dari0.922bit per karakter.

Mungkin sangat sulit untuk mengembangkan kode yang akan mencapai tingkat ini. * Sebagai contoh, coding Huffman akan mengalokasikan kode 0 , 10 dan  11 untuk A , B dan  C , masing-masing, untuk rata-rata 1.2  bit per karakter. Itu cukup jauh dari entropi, meskipun masih jauh lebih baik daripada pengkodean naif dua bit per karakter. Setiap upaya pengkodean yang lebih baik mungkin akan mengeksploitasi fakta bahwa bahkan menjalankan sepuluh A berturut - turut lebih mungkin (probabilitas 0.107 ) daripada B tunggal  .


* Ternyata tidak sulit untuk sedekat yang Anda inginkan - lihat jawaban lain!

David Richerby
sumber
18

Berikut ini adalah pengkodean konkret yang dapat mewakili setiap simbol dalam rata-rata kurang dari 1 bit:

Pertama, pisahkan string input menjadi pasangan karakter yang berurutan (misalnya AAAAAAAABAB menjadi AA | AA | AA | AA | BC). Kemudian menyandikan AA sebagai 0, AB 100, AC 101, BA 110, CA 1110, BB 111100, BC 111101, CB 111110, CC 111111. Saya belum mengatakan apa yang terjadi jika ada yang aneh jumlah simbol, tetapi Anda hanya dapat menyandikan simbol terakhir menggunakan beberapa encoding sewenang-wenang, tidak masalah ketika input panjang.

Ini adalah kode Huffman untuk distribusi pasangan simbol yang independen, dan sesuai dengan pemilihan n=2 dalam jawaban Yuval. Lebih besarn akan mengarah pada kode yang lebih baik (mendekati entropi Shannon dalam batas, seperti yang dia sebutkan).

Jumlah rata-rata bit per pasangan simbol untuk pengkodean di atas adalah

8108101+38101103+1108104+41101106=1.92
yaitu1.92/2=0.96 bit per simbol, tidak jauh dari entropi Shannon sebenarnya untuk pengkodean sederhana.

nomadictype
sumber
13

Biarkan D menjadi distribusi berikut lebih {A,B,C} : jika XD maka Pr[X=A]=4/5 dan Pr[X=B]=Pr[X=C]=1/10 .

Untuk setiap n kita dapat membuat kode awalan Cn:{A,B,C}n{0,1} sedemikian rupa sehingga

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

Dengan kata lain, jika kita mengkodekan sejumlah besar sampel independen dari D , maka rata-rata kita membutuhkan H(D)0.922 bit per sampel. Secara intuitif, alasan yang bisa kita lakukan dengan kurang dari satu bit adalah bahwa setiap sampel individu sangat mungkin menjadi A .

Ini adalah arti sebenarnya dari entropi, dan ini menunjukkan bahwa menghitung "entropi" dari string A8BC adalah latihan yang agak tidak berguna.

Yuval Filmus
sumber