Apakah Pengodean Huffman selalu optimal?

9

Persyaratan pengkodean sebagai awalan gratis menghasilkan pohon besar karena pohon harus lengkap. Apakah ada ambang batas tempat penyimpanan data yang tidak dikodekan dengan panjang tetap akan lebih efisien daripada pengkodean data?

information-theory data-compression Kaveh
sumber
Secara umum 'tidak'. Untuk data rata-rata, frekuensi masing-masing karakter akan> 1 dan bagus untuk menggunakan Pengodean Huffman daripada kode panjang tetap
@arunmoezhi Bisakah Anda menjawab contoh yang saya berikan di atas? Frekuensi setiap karakter lebih besar dari 1, namun panjang tetap lebih optimal.
Contoh ini menarik. Tetapi bisakah Anda memberikan skenario seperti itu dengan probabilitas masing-masing karakter alih-alih frekuensi dan memastikan probabilitas semua karakter ditambahkan ke 1
@arunmoezhi Saya telah menyertakan probabilitas karakter dan mereka menambahkan hingga 1.

Jawaban:

4

Entropi H(A)untuk masalah ini adalah 1.998. Baik pengkodean Huffman dan pengkodean panjang tetap untuk masalah ini memiliki panjang kode rata-rata avg sebagai 2. Dan FYI pengkodean yang Anda dapatkan menggunakan Huffman Encoding salah. Huffman Encoding juga menghasilkan kode yang mirip dengan panjang tetap untuk masalah ini. Itu menggunakan pendekatan serakah. Jadi atidak mendapatkan kode 0melainkan mendapat 00. Mengolah ulang pohon yang Anda hasilkan menggunakan Huffman Coding. Pohon yang harus Anda dapatkan adalah:masukkan deskripsi gambar di sini

arunmoezhi
sumber
Terima kasih. Bisakah Anda memberikan semacam bukti bahwa Huffman Encoding selalu lebih optimal daripada panjang tetap, atau setidaknya merujuk saya ke satu?
1
Anda dapat merujuk Introduction to Algorithmsoleh CLRS. Dalam bab yang membahas tentang ini, greedy algorithmsAnda bisa mendapatkan bukti formal Huffman algorithm. Ini bukti yang panjang dan perlu kesabaran untuk membaca.
8

Pengodean Huffman mendekati distribusi populasi dengan kekuatan dua probabilitas. Jika distribusi sebenarnya terdiri dari kekuatan dua probabilitas (dan simbol input sama sekali tidak berkorelasi), pengkodean Huffman optimal. Jika tidak, Anda bisa melakukan yang lebih baik dengan pengkodean rentang. Namun optimal di antara semua pengkodean yang menetapkan set bit tertentu untuk simbol tertentu dalam input.

Antimon
sumber
Apa yang Anda maksud dengan "perkiraan distribusi populasi"?
3
Ada distribusi pesan yang benar secara teoretis yang secara hipotesis dapat dikirim. Idealnya, setiap pesan harus dikodekan dengan cara yang proporsional dengan log probabilitasnya, tetapi karena kode Huffman adalah bilangan integer bit, yang secara implisit sesuai dengan probabilitas yang merupakan kekuatan dua. Karena itu perkiraan. Cari Teorema Coding Shannons.
8

Ya, selalu optimal.

Tidak, tidak ada ambang batas di mana ia akan menggunakan lebih sedikit ruang untuk menggunakan data yang tidak dikodekan dengan panjang tetap.

Saya menemukan sejumlah bukti di Web, tetapi ada diskusi yang cukup di artikel Wikipedia pengkodean Huffman .

Ini juga mencakup teknik lain yang mencapai kompresi lebih tinggi (bekerja di luar ruang di mana kode Huffman optimal).

Cade Roux
sumber