Bagaimana cara kerja pengkodean Huffman adaptif?

Pengodean Huffman adalah metode pengkodean entropi yang banyak digunakan untuk kompresi data. Diasumsikan bahwa kita memiliki pengetahuan lengkap tentang statistik sinyal. Namun, ada versi pengkodean Huffman yang digunakan dengan media streaming dan tidak mungkin tahu segalanya tentang statistik sinyal. Bagaimana cara kerja encoder Huffman adaptif ini ?

The Artikel Wikipedia memiliki penjelasan yang baik cantik proses coding Huffman adaptif menggunakan salah satu implementasi terkenal, algoritma Vitter. Seperti yang Anda catat, pembuat kode Huffman standar memiliki akses ke fungsi massa probabilitas dari urutan inputnya, yang digunakannya untuk membuat penyandian efisien untuk nilai simbol yang paling mungkin. Dalam contoh prototipis dari kompresi data berbasis file, misalnya, distribusi probabilitas ini dapat dihitung dengan melakukan histogram urutan input, menghitung jumlah kemunculan setiap nilai simbol (simbol dapat berupa urutan 1-byte, misalnya). Histogram ini digunakan untuk menghasilkan pohon Huffman, seperti yang ini (diambil dari artikel Wikipedia):

Pohon diatur dengan mengurangi berat, atau kemungkinan terjadinya dalam urutan input; node daun di atas mewakili simbol yang paling mungkin, yang karenanya menerima representasi terpendek dalam aliran data terkompresi. Pohon kemudian disimpan bersama dengan data yang dikompresi dan kemudian digunakan oleh dekompresor kemudian untuk meregenerasi urutan input (tidak terkompresi) lagi. Sebagai salah satu implementasi kode entropi awal, pengkodean Huffman standar cukup mudah.

Struktur Huffman coder yang adaptif sangat mirip; ia menggunakan representasi berbasis pohon yang serupa dari statistik urutan input untuk memilih pengkodean efisien untuk setiap nilai simbol input. Perbedaan utama adalah bahwa, sebagai implementasi streaming dari algoritma, tidak ada pengetahuan apriori tentang fungsi massa probabilitas input yang tersedia; statistik urutan harus diperkirakan dengan cepat. Jika seseorang ingin menggunakan skema pengkodean Huffman yang sama, ini berarti bahwa pohon yang digunakan untuk menghasilkan setiap pengkodean simbol dalam aliran terkompresi harus dibangun dan dipelihara secara dinamis saat aliran input diproses.

Algoritma Vitter adalah salah satu cara untuk mencapai ini; karena setiap simbol input diproses, pohon diperbarui, mempertahankan karakteristik penurunan kemungkinan munculnya simbol saat Anda bergerak turun pohon. Algoritme mendefinisikan seperangkat aturan untuk bagaimana pohon diperbarui dari waktu ke waktu, dan bagaimana data terkompresi yang dihasilkan dikodekan dalam aliran output. Ketika urutan input dikonsumsi, struktur pohon harus menggambarkan deskripsi probabilitas input yang lebih dan lebih akurat. Berbeda dengan pendekatan pengkodean Huffman standar, decompressor tidak memiliki pohon statis untuk digunakan untuk decoding; ia harus melakukan fungsi pemeliharaan pohon yang sama secara terus menerus selama proses dekompresi.

Singkatnya : Coder Huffman adaptif beroperasi sangat mirip dengan algoritma standar; namun, alih-alih pengukuran statis dari statistik seluruh urutan input (pohon Huffman), estimasi dinamis, kumulatif (yaitu dari simbol pertama ke simbol saat ini) estimasi distribusi probabilitas urutan digunakan untuk menyandikan (dan mendekodekan) setiap simbol . Berbeda dengan pendekatan pengkodean Huffman standar, algoritma Huffman adaptif membutuhkan analisis statistik ini di kedua encoder dan decoder.