Seberapa baik kode Huffman ketika tidak ada huruf probabilitas besar?

Kode Huffman untuk distribusi probabilitas adalah kode awalan dengan panjang codeword rata-rata tertimbang minimum , di mana adalah panjang dari kata sandi ke- . Ini adalah teorema yang terkenal bahwa panjang rata-rata per simbol kode Huffman adalah antara dan , di mana adalah entropi Shannon dari distribusi probabilitas. $p$ $\sum p_i \ell_i$ $\ell_i$ $i$ $H(p)$ $H(p)+1$ $H(p) = -\sum_i \, p_i \log_2 p_i$

Contoh buruk kanonik, di mana panjang rata-rata melebihi entropi Shannon hampir 1, adalah distribusi probabilitas seperti , di mana entropi hampir 0, dan panjang rata-rata kode kata adalah 1. Ini memberikan celah antara entropi dan panjang kode sandi hampir . $\{.999, .001\}$ $1$

Tetapi apa yang terjadi ketika ada batasan pada probabilitas terbesar dalam distribusi probabilitas? Misalkan, misalnya, bahwa semua probabilitas kurang dari . Kesenjangan terbesar yang dapat saya temukan dalam kasus ini adalah untuk distribusi probabilitas seperti , di mana entropi sedikit lebih dari 1 dan panjang rata-rata codeword sedikit kurang dari 1,5, memberikan gap mendekati . Apakah ini yang terbaik yang dapat Anda lakukan? Bisakah Anda memberi batas atas pada celah yang benar-benar kurang dari 1 untuk kasus ini? $\frac{1}{2}$ $\{.499, .499, .002\}$ $0.5$

Sekarang, mari kita perhatikan kasus di mana semua probabilitas sangat kecil. Misalkan Anda memilih distribusi probabilitas atas huruf, masing-masing memiliki probabilitas . Dalam hal ini, kesenjangan terbesar terjadi jika Anda memilih . Di sini, Anda mendapatkan celah sekitar Apakah ini yang terbaik yang dapat Anda lakukan dalam situasi di mana semua probabilitas kecil? $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.$

Pertanyaan ini terinspirasi oleh pertanyaan TCS Stackexchange ini .

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

Jawaban:

Ada banyak makalah yang mempelajari persis masalah yang Anda sebutkan. Yang pertama dalam seri ini adalah makalah oleh Gallager, "Variasi pada Tema oleh Huffman", IEEE-IT, vol. 24, 1978, hlm. 668-674. Dia membuktikan bahwa perbedaan antara panjang kata sandi rata-rata kode Huffman dan entropi (ia menyebut kuantitas "redundansi") selalu benar-benar kurang dari (= probabilitas terbesar dalam distribusi probabilitas), dalam kasus , dan kurang dari , jika . Batas yang lebih baik diketahui, Anda dapat menemukannya di banyak makalah yang mengutip karya Gallager. $p$ $p\geq 1/2$ $p+0.086$ $p<1/2$

Ugo
sumber

Batas optimal telah ditemukan oleh Manstetten, Batas ketat pada redundansi kode Huffman .

Yuval Filmus

Dilihat oleh terikat, saya yakin Anda bermaksud untuk mengajukan pertanyaan yang berbeda ... atau Anda hanya tidak menentukan bagaimana Anda mengambil "rata-rata". Jadi saya akan menjawab keduanya. Jawabannya adalah tidak untuk kedua pertanyaan itu. $H(p) \leq \ldots \leq H(p)+1$

Pertama, jika Anda menentukan panjang kode rata-rata menggunakan distribusi yang seragam di atas kata-kata kode dan menganggap sebagai batas atas pada probabilitas salah satu elemen, maka pertimbangkan kode panjang mana kata kode memiliki panjang dan sisanya memiliki panjang . Untuk distribusi yang dikodekan dengan sempurna oleh kode ini, panjang rata-rata mendekati , kecuali jika Anda juga memiliki batas yang lebih rendah untuk probabilitas satu elemen, sedangkan entropinya adalah $2^{-q}$ $q+k$ $2^{q-1}$ $q$ $2^{q+k-1}$ $q+k$ $q+k$ . $q+\frac{k}{2}$

Sekarang mari kita perhatikan "panjang rata-rata" yang berarti panjang codeword rata-rata ketika kode Huffman digunakan untuk kode untuk . Di sini, terikat ketat, dan distribusi contoh mencapai dalam batas adalah satu di mana setiap elemen terjadi dengan probabilitas untuk (Elemen terakhir diberikan probabilitas sisa, tetapi tidak akan membuat perbedaan asimptotik). $p$ $2^{q\pm 1/2}$ $q \in {\mathbb Z}.$

Sebagai contoh, pertimbangkan Lalu $q = 7.$

menghasilkan. Distribusi kami memilikielemen dengan probabilitas ,dengan probabilitas , dan satu elemen mendapatkan sisanya. $A + B = 128, A\sqrt{2}+B/\sqrt{2}\leq 128, \max_{A \in {\mathbb Z}} A$ $A = 52, B = 76$ $52$ $2^{-6.5}$ $76$ $2^{-7.5}$

Kemudian , sedangkan kode Raih Huffman kehilangan entropi. (Kebetulan, kerugian entropi memiliki nama, apakah Anda melakukan pengkodean Huffman atau pengkodean sewenang-wenang untuk : K divergensi Kullback-Liebler $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$ . Menggunakannya, saya menemukan beberapa hari yang lalu, mengarah ke batas Chernoff dua sisi yang lebih ketat, seperti yang dapat Anda lihat di Wikipedia untuk batas Chernoff.) $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
sumber

- \log_{2} p_{i}

$-\log_2 p_i$

p

$p$

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.$

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$

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$