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.