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 :
0 komentar:
Posting Komentar