Huffman Coding

setelah beberapa lama gak ngebahas pelajaran *gak tau kenapa lagi jenuh belajar -,-*, akhirnyaaaaa ngebahas jugaaa..... hahaha

tadaaaaaaaaaa..................

Kompresi Citra

ginii looh, sekarang itu kan banyak banget ntu file" citra kyk video, musik atau gambar yang perlu memori gede buat nyimpen nya. naah, buat bikin file" itu jadi tidak terlalu memakan memori yang gede, perlu kompresi citra. dan diharapkan kompresi citra ini tidak merusak informasi yang ada pada file" tersebut.

Manfaat Kompresi Citra:

1. Waktu pengiriman data pada saluran komunikasi data lebih singkat.
2. Membutuhkan ruang memori dalam storage yang lebih sedikit dibandingkan dengan citra yang tidak dimampatkan.

salah satu cara untuk melakukan kompresi citra adalah Huffman Coding.

naaah disini saia akan sedikit membahas apa itu Huffman Coding dan bagaimana melakukan encode serta decoding pada algoritma ini.

Huffman Coding

Algoritma Huffman adalah algoritma kompresi citra yang menggunakan pendekatan statistik dengan cara melakukan pengkodean dalam bentuk bit untuk mewakili data karakter. Huffman Coding menggunakan struktur pohon dalam pemrosesannya.

ENCODING

Urutan langkah proses encode algoritma ini adalah sebagai berikut :

1. Urutkan nilai-nilai grayscale berdasarkan frekuensi kemunculannya.
2. Gabung 2 buahpohon yang mempunyai frekuensi kemunculan terkecil dan urutkan kembali.
3. Ulangi langkah (2) sampai tersisa satu pohon biner
4. Beri label pohon biner tersebut dengan cara sisi kiri pohon diberi label 0 dan sisi kanan pohon diberi label 1.
5. Telusuri pohon biner dari akar ke daun. Barisan label-label sisi dari akar kedaun adalah kode huffman.

Sebagai contoh, dalam kode ASCII string “ABBABABACAACDDD” ditulis :

Bila dikodekan menggunakan kode Huffman, langkahnya adalah sebagai berikut :
1. Buat daftar frekuensi kemunculan tiap-tiap karakter dan urutkan dari yang terkecil hingga terbesar.

2. Gabung 2 buahpohon yang mempunyai frekuensi kemunculan terkecil dan urutkan kembali.

3. Gabung 2 buah pohon yang mempunyai frekuensi kemunculan terkecil dan urutkan kembali.

4. Gabung 2 buahpohon yang mempunyai frekuensi kemunculan terkecil dan urutkan kembali.

5. Beri label dari akar ke daun, sebelah kiri = 0, kanan = 1.

Penulusuran dari akar ke daun (dari atas ke bawah) menghasilkan kode Huffman berikut :

Dalamkode Huffman, string “ABBABABACAACDDD” ditulis:

0 11 11 0 11 0 11 0 100 0 0 100 101 101 101

Dari contoh tersebut tampak bahwa kode untuk sebuah symbol/karakter tidak boleh menjadi awalan dari kode symbol yang lain guna menghindari keraguan (ambiguitas) dalam proses dekompresi atau decoding.

Jadi maksudnya jika pada symbol A kode Huffmannya 0, maka 0 tidak akan menjadi awalan kode Huffman pada kode selanjutnya.

Ukuran string sebelum pemampatan (dalam kode ASCII) adalah:
= 15 x 8 bit
= 120 bit

Ukuran string setelah pemampatan (dalam kode Huffman) adalah:
= 6 x 1 bit + 4 x 2 bit + 3 x 3 bit + 2 x 3 bit
= 29 bit

Rasio Pemampatan
= (100% - 29/120 x 100%) = 75.8%
Artinya 75.8% dari string semula telah berhasil dimampatkan.

DECODING

Karena tiap kode Huffman yang dihasilkan adalah unik maka proses decoding atau proses dekompresi dapat dilakukan dengan mudah. 

Contohnya, saat membaca kode bit pertama dalam rangkaian bit “0 11 11 0 11 0 11 0 100 0 0 100 101 101 101”, yaitu bit “0”, dapat langsung disimpulkan bahwa kode bit “0” merupakan pemetaan dari symbol “A”. Kemudian, baca kode selanjutnya, yaitu bit “1”. Tidak ada kode Huffman “1”, lalu baca kode bit selanjutnya sehingga menjadi “11”, rangkaian kode bit “11” adalah pemetaan dari symbol “B” dan seterusnya. Proses decoding tidak dapat dilakukan tanpa ada keyword sebelumnya dari proses encoding.

KELAAAARR.....

selamaat belajaaarr semuuaa!!

HWAITIIING \^^/