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 :
Kodekan setiap karakter dalam ASCII :
Jika MULTIMEDIA diubah dalam bit, menjadi :
01001101 01010101 01001100 01010100 01001001 01001101 01000101 01000100 01001001 01000001
= total 80 bit
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.
0 commen:
Post a Comment