Contoh Huffman Code Dan Penyelesaiannya

Pengertian Huffman Code

Huffman Code adalah salah satu metode dalam penyederhanaan suatu data, biasanya dipakai dalam proses kompressi. Contoh penerapan aba-aba huffman, contohnya suatu data mempunyai ukuran 500KB sanggup dikecilkan ukurannya dengan melaksanakan kompressi menjadi 300KB, tergantung dari seberapa effisien  metode Compression yang digunakan. Nah, salah satu metode dalam melaksanakan kompressi tersebut ialah Metode Huffman Coding. 

Contoh metode Huffman code ialah dengan memakai Huffman Tree yang cukup gampang untuk dimengerti.

Teorema dari Huffman Code ialah sebagai berikut:

1. Jika p_j > p_i , maka, l_j ≤ l_i

2. Dua Codeword dari dua simbol dengan probabilitas terendah mempunyai panjang yang sama

3. Dua Codeword terpanjang identik kecuali pada digit terakhir

Ket: 

S = Sumber

P = Probabilitas

C = Codewrod
l = Panjang

 Contoh soal  Huffman code

Metode dari Huffman code ini sanggup kita lihat dari Contoh soal  Huffman code berikut:

Dimisalkan pada sebuah kalimat terdapat huruf-huruf yang muncul  dengan banyaknya kemunculan ialah sebagai berikut:

Huruf	Frekuensi
a	5
b	7
c	10
d	14
e	20

Cara mencari aba-aba huffman dijelaskan di bawah ini:
Di bawah ini terdapat rujukan metode huffman tree atau disebut juga metode pengakaran dimana kita akan menciptakan suatu pola pengakaran pada pohon. Langkah pembentukan pohon huffman ialah sebagai berikut:

Untuk menciptakan Huffman Code pertama kita harus mengurutkan data frekuensi kemunculan dari yang trekecil ibarat tabel diatas, kemudian kita jumlah kan setiap data secara berpasangan dari yang terkecil:

maka kita mulai dengan menjumlahkan a dan b

Maka tabel menjelma sebagai berikut:

Huruf	Frekuensi
c	10
ab	12
d	14
e	20

Dari tabel di atas kita kembali jumlahkan dua nilai terkecil..

c dan ab

Maka tabel menjelma sebagai berikut:

Huruf	Frekuensi
d	14
e	20
abc	22

Dari tabel di atas kita kembali jumlahkan dua nilai terkecil..

 d dan e

Maka tabel menjelma sebagai berikut:

Huruf	Frekuensi
abc	22
de	34

Dari tabel di atas kita kembali jumlahkan dua nilai terkecil..

abc dan de

Lalu, alasannya ialah semua Huruf telah dijumlahkan, kita  tambahkan angka 0 dikiri setiap cabang, dan angka 1 dikanan setiap cabang, ibarat gambar di bawah ini:

Dari data metode pengakaran Hufman tree di atas di dapatkan Codeword  untuk setiap aksara ialah sebagai berikut:

Huruf	CodeWord
a	000
b	100
c	10
d	01
e	11

Dari tabel diatas kita mendapat aba-aba yang unik untuk setiap aksara dengan memakai Metoda Hufman Tree pada Hufman Code. 

Demikian rujukan soal Huffman code dan cara penyelesaiannya memakai metode huffman tree.

Share :