Contoh Encoding Dan Decoding Huffman


            Agar algoritma di atas lebih jelas akan diberikan contoh encoding dan decoding Huffman pada sebuah data file Wave seperti di bawah ini. Data file Wave ini dimulai dari offset byte ke-45 dan diambil hanya 10 byte dan dinyatakan dalam heksadesimal.
FF 06 00 FA FF 06 00 7C FE 06
Langkah awal adalah membentuk tabel distribusi frekuensi seperti terlihat pada tabel berikut ini.
Tabel 3.1  Tabel Distribusi Frekuensi
Karakter
06
FF
00
FA
7C
FE
Frekuensi
3
2
2
1
1
1

Setelah itu dibentuk node pohon untuk tiap karakter beserta nilai frekuensinya masing-masing seperti gambar di bawah ini. Pada contoh ini pengurutan dilakukan secara menurun (descending) dari nilai frekuensi terbesar hingga terkecil dan frekuensi yang sama didahulukan sesuai dengan urutan abjad.
Gambar 3.5  Gambar Contoh I
Selanjutnya dimulai dengan memilih dua node yang terkecil, dalam kasus ini adalah karakter “FE” dan “7C”.  Gabungkan kedua node tersebut hingga membentuk sebuah pohon baru dengan nilai akarnya merupakan penjumlah nilai (weight) dari ‘FE’ dan ‘7C’. Dalam kasus ini adalah bernilai 2. Kemudian, kedua node pohon tersebut dihapus dan diganti dengan pohon baru hasil penggabungan mereka. Gambar berikut ini menunjukkan hasil pada tahap ini.
Gambar 3.6  Gambar Contoh II
Setelah itu masing-masing node diurutkan lagi dari nilai terbesar hingga terkecil.
Gambar 3.7  Gambar Contoh III
Berikutnya, dengan mengulang proses seperti di atas, gabungkan ‘FE 7C’ dan ‘FA’. Dengan mengambil dua buah node tersebut keluar, dan seperti halnya pada langkah di atas, menggabungkan mereka menjadi sebuah pohon dengan nilai 3. Sebagai catatan, pada setiap iterasi, jumlah node yang sisa dalam kumpulan dikurangi satu, karena dua buah node dihilangkan dan digantikan dengan sebuah node akar tunggal.
Gambar 3.8  Gambar Contoh IV
Setelah itu masing-masing node diurutkan lagi dari nilai terbesar hingga terkecil.
Gambar 3.9  Gambar Contoh V
            Sekali lagi, dua buah node yang terkecil ditarik keluar dan dibentuk sebuah pohon dengan nilai 4. Perhatikan ini merupakan node yang tidak mempunyai daun atau non- leaf nodes (node tidak berada di bagian akhir) maka node tersebut tidak merepresentasikan karakter tunggal.
Gambar 3.10  Gambar Contoh VI
            Berikutnya adalah mengurutkan lagi secara descending node-node tersebut seperti langkah di atas.
Gambar 3.11  Gambar Contoh VII
            Sekali lagi, dua buah node yang terkecil ditarik keluar dan dibentuk sebuah pohon dengan nilai 6.
Gambar 3.12  Gambar Contoh  VIII
            Seperti langkah di atas maka dua node terakhir ini akan diurutkan dari terbesar hingga terkecil seperti gambar berikut ini.
Gambar 3.13  Gambar Contoh IX
            Selanjutnya, menggabung sisa dua node yang terakhir untuk memperoleh pohon biner akhir. Akar dari pohon ini selalu mempunyai nilai setara dengan jumlah karakter dalam file input, yang dalam kasus ini adalah 10.
Gambar 3.14  Gambar Contoh X
Dengan menggunakan aturan yang disebutkan di bagian atas, untuk membaca kode dari pohon Huffman ini, dimulai dari akar dan tambahkan ‘0’ setiap kali menuju ke sisi kiri dari anak pohon, dan menambahkan ‘1’ setiap kali menuju ke kanan.
Gambar 3.15  Gambar Contoh XI
Tabel berikut ini merupakan hasil dari bit code atau code word untuk tiap karakter
Tabel 3.2  Bit Code Hasil Pohon Huffman
Simbol
Bit Code
06
00
FF
10
00
11
FA
011
7C
0101
FE
0100

            Untuk melakukan encoding dengan encoding Huffman, misalkan dalam data file Wave tersebut adalah “FF 06 00 FA FF 06 00 7C FE 06” maka hasilnya dengan melihat pada tabel bit code akan menjadi:
10  00  11  011  10  00  11  0101 0100 00
Untuk menentukan rasio kompresi maka ditentukan terlebih jumlah bit data sebelum dikompresi yaitu: jumlah karakter dalam byte ´  8 bit = 10 ´ 8 bit = 80 bit. Sedangkan jumlah bit hasil kompresi adalah 25 bit, berarti rasio kompresi yang didapat adalah  = 31,25 %
            Untuk proses dekompresi balik maka bit hasil kompresi dibaca ulang dan terlebih dahulu dibentuk kembali pohon Huffman. Misalkan dibaca bit pertama adalah bit “1” maka pindah ke sisi kanan pohon jika node bukan merupakan leaf maka baca lagi bit kedua yang merupakan bit “0” dan pindah ke sisi kiri pohon dan bertemu dengan node tunggal berarti karakter tersebut dicetak yaitu “FF”. Setelah itu pembacaan akan dimulai dari bagian akar lagi. Langkah pembacaan seperti langkah sebelumnya sampai semua bit hasil kompresi selesai diproses. 

Popular posts from this blog

Kode Singkatan Komponen Listrik Dan Elektronik

Cara Mengatasi E31 Canon MP258

Cara Mengukur Trimpot