Graf – Pohon Pengkode Huffman

Posted on

Kita biasanya mengkodekan suatu string dengan menggunakan kode yang panjangnya tetap (fixed-length codes) pada seluruh alfabet (mis. 8 bit untuk ASCII). Akan tetapi, jika karakter yang berbeda muncul dengan frekuensi yang berbeda, kita dapat menghemat memori dan mereduksi waktu transmisi dengan cara menggunakan kode yang panjangnya dapat diubah (VLCvariable length codes). Ide dasar dari teknik pengkodean ini adalah nya adalah memakai kode terpendek untuk karakter yang paling sering muncul.

Ada beberapa hal yang harus diperhatikan ketika menggunakan VLC. Misalnya, kita ingin mengkodekan karakter “e” dengan bit “0”, “a” dengan “1”, dan “t” dengan “01”. Bagaimana kemudian kita mengkodekan kata “tea? Dari system ini, maka kodenya adalah “0101”. Kalau dilihat lebih cermat, kode tersebut rancu, karena kode tersebut bisa juga dihasilkan dari kata “eat” , “eaea”, atau “tt”. Tentu saja kode yang demikian tidak dapat diterima karena dapat menyebabkan kesalahan/kehilangan informasi.

Untuk menghindari kerancuan ini kita dapat menggunakan kode prefix (prefix code). Pada kode prefiks, bit string untuk sebuah karakter tidak pernah akan menjadi prefiks (bagian pertama) dari bit string karakter lainnya. Sebagai contoh, pengkodean “e”  dengan “0”, “a” dengan “10”, dan “t” dengan “ii” adalah kode prefiks. Maka, Kata “tea” akan dikodekan sebagai “11010”. Bit string ini adalah unik karena hanya kata “tea” tidak ada kata lain yang dapat dikodekan dengan hasil sama.

 


Pada pohon biner ini tidak ada leaf yang dapat menjadi ancestor (cabang) dari leaf lainnya. Sehingga, tidak ada kode dari karakter dapat menjadi prefiks dari kode karakter lainnya. Inilah yang dimaksud dengan kode prefiks.Kode prefiks dapat disusun dengan bantuan pohon biner, dimana karakter adalah label dari leaf (daun) dalam pohon biner tersebut. Garis dari tree dilabeli sedemikian hingga garis ke child kiri diberi bit ”0” dan ke child kanan dengan “1”. Bit string yang dipakai untuk menkodekan karakter adalah rangkaian label dari garis dalam lintasan yang unik dari root ke leaf yang dilabeli dengan karakter tersebut. Maka, pohon biner untuk contoh pengkodean “tea” yang telah dibahas adalah sebagai berikut.

Selengkapnya : Pohon Pengkode Huffman

2 thoughts on “Graf – Pohon Pengkode Huffman

    Aryan said:
    Januari 9, 2012 pukul 12:07 am

    Belajar ah

    Diskripsi Matakuliah Matematika Diskrit | Wawan Laksito said:
    Oktober 30, 2013 pukul 6:58 pm

    […] Materi 5 […]

Tinggalkan Balasan

Isikan data di bawah atau klik salah satu ikon untuk log in:

Logo WordPress.com

You are commenting using your WordPress.com account. Logout / Ubah )

Gambar Twitter

You are commenting using your Twitter account. Logout / Ubah )

Foto Facebook

You are commenting using your Facebook account. Logout / Ubah )

Foto Google+

You are commenting using your Google+ account. Logout / Ubah )

Connecting to %s