Bagaimana cara membuat kode imbuhan optimal?

Sebuah kode imbuhan adalah kode yang bersamaan awalan dan akhiran kode. Artinya, tidak ada codeword yang bukan awalan atau sufiks dari codeword lainnya. Kode Affix dapat didekodekan secara instan di kedua arah (maju dan mundur).

Saya ingin membuat satu yang secara optimal mengompresi distribusi simbol input yang diberikan, diberikan satu set simbol output.

Algoritma Huffman (yang membuat kode awalan) paling dekat, tetapi karena strategi serakahnya, tampaknya tidak cocok untuk modifikasi pada tujuan ini.

Bagaimana kode afiks optimal dapat ditemukan?

coding-theory prefix-free-code Anko
sumber

Jawaban:

Saya benar-benar tidak berpikir bahwa ada algoritma yang diketahui optimal. Bahkan, ada dugaan utama tentang seberapa efektif satu set kata-kata kode dapat, lihat: http://arxiv.org/abs/0709.2598 (nama yang saya tahu untuk kode imbuhan adalah kode bebas-fix). Jika suatu algoritma terbukti optimal, maka kemungkinan besar itu juga akan memecahkan (atau menonaktifkan) dugaan ini juga.

domotorp
sumber

Jawaban ini tampaknya menunjukkan bahwa algoritma Huffman menghasilkan kode optimal dalam kondisi yang wajar.

Anko

Saya tidak melihat bagaimana jawaban itu terkait dengan masalah Anda. Jika Anda hanya satu algoritma, Anda dapat menggunakan huffman, dan kemudian memperpanjang beberapa kata-kata buruk.

domotorp

Saya hanya menekankan bahwa beberapa kode dapat dibuktikan optimal. Memperluas codeword kode Huffman kemungkinan membuatnya tidak optimal, karena setiap ekstensi membuatnya mendekati blok kode. Ini mungkin merupakan titik awal!

Anko

Tetapi Huffman adalah untuk bebas awalan yang kita ketahui ketidaksetaraan Kraft ( en.wikipedia.org/wiki/Kraft%27s_inequality ). Jika kita memiliki bukti optimalitas, ketimpangan seperti kraft mengikuti. Tetapi untuk kode fix-free, resp. ketidaksetaraan adalah dugaan, sehingga tidak ada bukti.

domotorp

Di halaman 8, bawah, beberapa kode bebas-fix untuk bahasa Inggris dijelaskan, dan disebutkan bahwa tidak ada algoritma yang digunakan untuk membangunnya yang terbukti optimal. Jadi agaknya tidak ada algoritma yang efisien yang diketahui.

Yuval Filmus

FWIW, sepertinya bagi saya ada PTAS untuk masalah ini, mengikuti ide dasar dalam makalah ini . (Ini tidak persis menjawab pertanyaan Anda, tetapi saya masih akan menjelaskan PTAS di sini di bagian jawaban karena terlalu panjang untuk dimasukkan dalam komentar.)

Perbaiki konstanta . Biarkan menjadi contoh masalah, yaitu distribusi probabilitas pada . $\epsilon>0$ $p$ $[n]$

$K$ $K$

$K=\lceil 1/\epsilon^2\rceil$ $K$ $p$ $n$ $S$ $K$ $K$ $C(S)$ $|S|$ $p$ $S$ $n-|S|$ $K$ $S$ $n-|S|$ $n-|S|$ $S$ $C(S)$ $C_0$ $S$ $C_0$ $K$ $p$ .

$C_0$ $p$ $K$

$C_0$ $(1+O(\epsilon))$

$C_0$ $K' = \lceil 1/\epsilon \rceil$ $(1+\epsilon)$ $K$ $K$ $C_0$ $K$ $K'$ $K'$ $1+O(\epsilon)$ $C_1$

$C_1$ $(1+O(\epsilon))$ $C_0$ $C_0$ $C_1$ $(1+O(\epsilon))$

Neal Young
sumber