Huffman Code dan Shannon Fano (I)

Huffman Code dan Shannon Fano merupakan algoritma untuk melakukan sebuah kompresi data. Secara umum, kompresi dapat diartikan dengan mengecilkan ukuran, dalam hal ini adalah data.  Tujuan dari kompresi data adalah untuk memperkecil kebutuhan penyimpanan data, mempercepat pengiriman data dan memperkecil kebutuhan bandwith. Sebuah teks yang menggunakan karakter yang cukup panjang, namun dalam teks tersebut terdapat beberapa karakter yang sama, akan membutuhkan ruang data yang besar pula. Maka dengan algoritma ini, ukuran data tersebut dapat diperkecil. Dalam metode Huffman dan Shannon Fanno ada beberapa perbedaan, untuk mengetahui perbedaan tersebut, kita lihat contoh di bawah ini.

Huffman Coding

Contoh mengkodekan kata “MULTIMEDIA”
Kodekan setiap karakter dalam  ASCII :

Jika MULTIMEDIA diubah dalam bit, menjadi :
 01001101  01010101  01001100  01010100  01001001  01001101  01000101  01000100  01001001    01000001
= total 80 bit

Kompresi dengan Huffman Coding

Menghitung jumlah frekuensi tiap karakter(frekuensi adalah jumlah masing-masing karakter dalam teks):

Urutkan tiap karakter dari frekuensi terendah, jika ada karakter yang sama jumlah frekuensinya, urutkan sesuai ASCII binary.

Setelah diurutkan, kemudian ambil 2 node di sebelah kiri (A and D), kemudian buatlah node baru yang merupakan kombinasi dari kedua node. Kombinasi node akan mempunyai dua cabang dari kedua komponen node. Frekuensi dari kombinasi node merupakan jumlah frekuensi kedua cabang node.

Jika sudah selesai, letakkan bit 0 dan 1 pada pohon,

Buat daftar kode Huffman dari pohon

Dari cara diatas, dapat dihitung selisih bit yang digunakan setelah di kompresi

Yaitu 80 - 30 = 50 bit.

Untuk yang Metode Shannon Fano siakan baca Huffman Code dan Shannon Fano (II)

Terimakasih, semoga bermanfaat.