Algoritma Adaptive Huffman Coding

03.29 Endicka E Prakarsa No comments

Adaptive Huffman coding pertama kali diperkenalkan oleh Faller dan Gallager (Faller 1973; Gallaber 1978). Knuth memberikan kontribusi dengan peningkatan pada algoritmanya (Knuth 1985) dan menghasilkan algoritma yang dikenal dengan algoritma FGK. Versi terbaru dari adaptive Huffman Coding diperkenalkan oleh Vitter (Vitter 1987). Semua metode yang ditemukan merupakan skema define-word tabf menentukan mapping dari pesan sumber menjadi codeword didasari pada perkiraan probabilitas pesan sumber. Kode bersifat adaptive, berganti sesuai dengan perkiraan optimalnya pada saat itu. Dalam hal ini, Adaptive Huffman Code merespon lokalitas. Dalam pengertian, encoder mempelajari karakteristik dari sumber. Dekoder harus mempelajari bersamaan dengan encoder dengan selalu memperbaharui Huffman tree sehingga selalu sinkron dengan encoder.

Keuntungan lain dari system ini adalah kebutuhan akan lewatnya data, data akan lewat hanya sekali (tanpa table statistic). Tentu saja, metode one-pass tidak akan menarik apabila jumlah bit yang ditransmisikan lebih besar dari metoda twopass. Namun, performa dari metode ini, dalam ruang lingkup jumlah bit yang ditransmisikan, dapat lebih baik daripada static Huffman coding. Permasalahan ini tidak kontradiktif dengan optimalisasi pada metode statis, karena metode ini optimal hanya [ada metode yang mengasumsikan mapping berdasarkan time-variant. Kinerja dari metode adaptive dapat lebih buruk daripada metode static. Metode adaptive Faller, Gallager dan Knuth merupakan dasar dari UNIX utility compact. Kinerja compact ini termasuk bagus, karen factor kompresinya mencapai 30-40%.

Dasar dari algoritma FGK adalah adanya sibling (factor turunan) property, didefinisikan oleh Gallager [Gallager 1978]: binary code tree mempunyai sibling apabila setiap node )kecuali root) mempunyai sebuah sibling dan apabila node-node tersebut dapat diurutkan dalam weight dengan setiap node berhubungan dengan siblingnya masing-masing. Gallager membuktikan bahwa sebuah code prefik biner

merupakan Huffman code jika dan hanya jika code tree mempunyai sibling property. Dalam algoritma FGK, baik pengirim dan penerima menangani perubahan dinamis dari Huffman code tree. Daun dari setiap pohon Huffman code merepresentasikan pesan sumber dan berat dari setiap daun merepresentasikan hitungan frekuensi untuk setiap pesan. Pada titik manapun dalam satuan waktu, k dari kemungkinan n pesan sumber terdapat pada susunan pesan.

Gambar 3. Algoritma FGK

Pada Gambar 3, Algoritma FGK mengolah susunan EXAMPLE (a) Pohon setelah memproses “aa bb“; 11 akan ditransmisikan untuk b selanjutnya. (b) Setelah b ketiga; 101 akan ditransmisikan untuk tempat selanjutnya; pohon tidak berubah; 100 akan ditransmisikan untuk c pertama. (c) Pohon setelah diperbaharui dengan c pertama.

Pada awalnya, the code tree consists of a single leaf node, yang disebut 0- node. 0-node digunakan untuk menggambarkan pesan n-k yang tidak digunakan. Untuk setiap pesan yang ditransmisikan, kedua bagian harus menambahkan weight dan menghitung kembali code tree untuk mempertahankan simbling property. Pada titik dalam satuan waktu dimana t pesan telah ditransmisikan. Pada titik dimana t pesan telah ditransmisikan, k dari mereka berbeda, dan k < n, pohon merupakan Huffman tree asli dengan daun sebanyak k+1, 1 yaitu k pesan dan 0-node. Apabila pesan ke (t+1) adalah salah satu dari k, maka algoritma mentrasmisikan code ke a(t+1), menaikkan counter dan menghitung kembali pohon. Apabila terdapat pesan yang tidak digunakan, 0-node dipisah untuk membuat 2 pasang daun, satu untuk

a(t+1), dan siblingnya adalah 0-node yang baru. Sekali lagi dalam proses ini, pohon diperhitungkan kembali. Dalam kasus ini, kode untuk 0-node dikirimkan; sebagai tambahan, penerima harus memberitahukan pesan n-k mana yang tidak digunakan yang muncul. Pada setiap node, penyimpanan perhitngan dari pesan yang muncul dilakukan. Node diberikan nomor untuk mengindikasikan posisi mereka dalam urutan sibling propertinya. Pembaharuan dari pohon dapat dilakukan dalam sebuah single traversal dari node a(t+1) sampai dengan root-nya. Traversal ini harus meningkatkan perhitungan untuk node a(t+1) dan untuk setiap bagian atas dari node tersebut. Node boleh berubah untuk memelihara sibling property-nya, namun perubahan membutuhkan keterlibatan node pada path a(t+1) ke root-nya.

Posted in: MULTIMEDIA