Huffman code adalah salah satu teknik dalam kompresi data yang menggunakan struktur data binary tree. Hal ini dilakukan dengan tujuan mengurangi penggunaan diskspace dan network traffic.
Algortima Huffman / huffman code merupakan salah satu algoritma kompresi data yang cukup terekenal dan populer, hal ini dikarenakan algortima huffman cukup efektif untuk kompresi data. Dalam encoding sebuah character dengan binary code biasa sebuah character akan memakan memory secara static 8 bit, atau 1 byte.
Seumpama sebuah string “Yohanda” dimana terdapat 7 character didalamnya akan memakan memori sebesar 7 x 8 bit = 56 bit atau 7 byte. Dimana jika string tersebut diencoding dengan algoritma huffman, akan memakan memori yang lebih kecil dari itu. Karena jumlah bit yang merepresentasikan suatu character dalam algoritma huffman bersifat dinamis, sehigga satu character dengan lainnya akan berbeda dalam jumlah bitnya.
Ada beberapa langkah untuk men encoding sebuah data dengan algoritma huffman, yaitu sebagai berikut :
1. Baca semua character dalam string yang akan diencoding, dan simpan tiap character yang unique pada string tersebut dan simpan pada suatu list, beserta frekuensi kemunculannya, lalu sorting list tersebut dari kecil ke besar.
Contoh “Yohanda_Mandala”
Y -> frekuensinya : 1
o -> frekuensinya :1
h -> frekuensinya :1
_ -> frekuensinya :1
M -> frekuensinya :1
l -> frekuensinya :1
n -> frekuensinya :2
d -> frekuensinya :2
a -> frekuensinya :5
Seumpama sebuah string “Yohanda” dimana terdapat 7 character didalamnya akan memakan memori sebesar 7 x 8 bit = 56 bit atau 7 byte. Dimana jika string tersebut diencoding dengan algoritma huffman, akan memakan memori yang lebih kecil dari itu. Karena jumlah bit yang merepresentasikan suatu character dalam algoritma huffman bersifat dinamis, sehigga satu character dengan lainnya akan berbeda dalam jumlah bitnya.
Ada beberapa langkah untuk men encoding sebuah data dengan algoritma huffman, yaitu sebagai berikut :
1. Baca semua character dalam string yang akan diencoding, dan simpan tiap character yang unique pada string tersebut dan simpan pada suatu list, beserta frekuensi kemunculannya, lalu sorting list tersebut dari kecil ke besar.
Contoh “Yohanda_Mandala”
Y -> frekuensinya : 1
o -> frekuensinya :1
h -> frekuensinya :1
_ -> frekuensinya :1
M -> frekuensinya :1
l -> frekuensinya :1
n -> frekuensinya :2
d -> frekuensinya :2
a -> frekuensinya :5
2. Gabung dua node list terkecil menjadi sebuah node tree, semisal node yang digabungkan adalah node Y dan none O maka tree yang terbentuk adalah :
3. Parent dari tree yang baru dibentuk ke dalam list4. Remove 2 node yang telah dibentuk tree nya tadi
5. Sorting ulang list tadi.
6. Ulangi Langkah ke -2 Hingga node dari list cuma tersisa satu.
7. Baca pohon huffman yang terbentuk dengan aturan jika bergerak ke nodeChild kiri “0”, dan jika nodeChild kanan “1”.
Sebagai contoh, mari kita coba encoding String “Yohanda_Mandala” ini :
>> Iterasi ke -1 (membangun sebuah list dari string tersebut)
Y -> frekuensinya : 1
o -> frekuensinya :1
h -> frekuensinya :1
_ -> frekuensinya :1
M -> frekuensinya :1
l -> frekuensinya :1
n -> frekuensinya :2
d -> frekuensinya :2
a -> frekuensinya :5
>> Iterasi ke -2 (membuat tree dari 2 node list terkecil dan memasukan nya kembali ke list, serta meremove node dari list yang telah dibangun treenya)
h -> frekuensinya :1
_ -> frekuensinya :1
M -> frekuensinya :1
l -> frekuensinya :1
Yo ->frekuensinya : 2
n -> frekuensinya :2
d -> frekuensinya :2
a -> frekuensinya :5
>> Iterasi ke -3 (Sama seperti iterasi ke 2)
M -> frekuensinya :1
l -> frekuensinya :1
h_ ->frekuensinya : 2
Yo ->frekuensinya : 2
n -> frekuensinya :2
d -> frekuensinya :2
a -> frekuensinya :5
>> Iterasi ke -4 (Sama seperti iterasi ke 2)
Ml -> frekuensinya : 2
h_ ->frekuensinya : 2
Yo ->frekuensinya : 2
n -> frekuensinya :2
d -> frekuensinya :2
a -> frekuensinya :5
>> Iterasi ke -5 (Sama seperti iterasi ke 2)
Yo ->frekuensinya : 2
n -> frekuensinya :2
d -> frekuensinya :2
Mlh_ ->frekuensinya : 4
a -> frekuensinya :5
>> Iterasi ke -6 (Sama seperti iterasi ke 2)
d -> frekuensinya :2
Yon -> frekuensinya :4
Mlh_ ->frekuensinya : 4
a -> frekuensinya :5
>> Iterasi ke -7 (Sama seperti iterasi ke 2)
Mlh_ ->frekuensinya : 4
a -> frekuensinya :5
Yond -> frekuensinya :6
>> Iterasi ke -8 (Sama seperti iterasi ke 2)
Yond -> frekuensinya :6
aMlh_ -> frekuensinya :9
>> Iterasi ke -9 (Sama seperti iterasi ke 2)
YondaMlh_ -> frekuensinya :15
>> Iterasi berhenti karena node dari list hanya tinggal 1.
Maka tree yang terbentuk dari encoding string diatas adalah seperti ini :
Jika dilihat dari pohon diatas makan encoding String “Yohanda_Mandala” dengan aturan jika berjalan ke kiri = 0 dan kekanan = 1, maka akan menjadi seperti ini
Y = 0010
o = 0011
h = 1010
a = 11
n = 000
d = 01
_ = 0100
M = 1000
a = 11
n = 000
d = 01
a = 11
l = 1001
maka jika kita jumlahkan seluruh dari bitwise diatas adalah = 40 bit atau hanya cukup 5 byte dataspace saja. Jika kita bandingkan, jika menggunakan binary biasa adalah 13 x 8 = 104 bit atau 13 byte diskspace maka dengan itu kita telah menghemat ruang sebesar sekitar 60%.
l = 1001
maka jika kita jumlahkan seluruh dari bitwise diatas adalah = 40 bit atau hanya cukup 5 byte dataspace saja. Jika kita bandingkan, jika menggunakan binary biasa adalah 13 x 8 = 104 bit atau 13 byte diskspace maka dengan itu kita telah menghemat ruang sebesar sekitar 60%.
Untuk implementasinya dalam java atau C# dapat didownload melalui link dibawah ini :
17 komentar:
amin...... thx kk... gendut tapi lucu.. wkwkkw.. ^^
wah menarik mas artikelnya....
Mas mau nanya nih bisa ga' kode huffman ini dipake ke j2me???
apakah codingnya beda lagi dengan source code yang mas berikan ini,,,
Salam,,,
Kalo kodingannya sih ngga berbeda cuma ada beberapa hal yang harus diubah, soalnya banyak fitur2 dari j2se yang dihilangkan di j2me untuk menghemat memori...
Mas Yohanda, itu kan untuk kompresnya...,trus bagaimana untuk dekompresnya
Kalo dekompresinya itu prinsipnya sama, jadi barisan bilangan biner hasil kompresi huffman tersebut dicocokan dengan tree huffmannya, sehingga akan ketemu string asli dari huffman code tersebut
Mas Yohanda, saya coba ganti teks string input jadi kalimat yg panjang (1 paragraf), tapi ko' muncul error "java.lang.stackoverflow" gitu.. Emang dibatasi string nya ya.. Gimana merubahnya? Terima kasih.
Iya jelas stack overflow , soalnya tree dari huffman saya diatas menggunakan recursive tree, kan setiap operasi recursive itu ada batasannya, jika tidak maka akan memakan memory terlalu banyak, bah solusinya cukup merubah tree saya tersebut menjadi non-recursive tree, pasti bisa deh,,,
makasih ya.. sudah membantu sekali... ^^
mas mw tanya..kok tree nya gak muncul ya??
mas,aq mo download implementasi Huffman code dalam Java ( netbeans project sama source codenya) kug linknya dihapus ea??
mas codenya gak bisa di download
bisanya cuma download doang...
ckckckck..
MAS mohon di upload lagi mas
saya butuh sekali mas >makasih
mas lingnya dah di hapus?
mas lingnya dah di hapus?
mas lingnya dah di hapus?
maaf mas, link source codenya sudah dihapus ya??
Poskan Komentar