Tentang Coding Huffman

Sejarah dan Pengertian

Pada tahun 1951 Dosen pengajar Huffman (bernama Robert M. Fano) menawarkan kepada para mahasiswanya bahwa siapa saja yang dapat menulis sebuah artikel tentang membangun pohon biner yang efisien akan mendapatkan nilai bagus tanpa harus menempuh ujian. Tantangan in ditanggapi oleh David A Huffman. Pada akhirnya ia berhasil menciptakan suatu pohon biner yang lebih efisien bahkan di bandingkan dengan pohon biner buatan dosennya sendiri. Untuk selanjutnya pohon tersebut di sebut huffman tree. Huffman sebenarnya hampir menyerah pada saat mengerjakan tugas ini, namun akhirnya ia menemukan sebuah metode untuk mngetasi Binary Tree yang ia buat yaitu menggunakan metode frekuensi. Binary Tree buatannya kemudian berkembang menjadi dasar algoritma untuk kompresi data (seperti ZIP dan format MP3). 

Secara kasar Algoritma huffman ini bisa diartikan sebagai sebuah teknik kompresi dokumen yang menggunakan jumlah kemunculan relatif simbol-simbol karakter pada dokumen teks untuk menghasilkan representasi biner dengan panjang tertentu untuk tiap karakter. Sebuah teknik kompresi dokumen yang menggunakan jumlah kemunculan relatif simbol-simbol karakter pada dokumen teks untuk menghasilkan representasi biner dengan panjang tertentu untuk tiap karakter. 

Contoh Huffman Tree 

Baiklah jika hanya sebuah tulisan definisi tanpa contoh anda tetntu tidak akan mengerti oleh karena itu akan saya coba untuk memberikan contoh dari sumber yang saya dapat di internet tentunya. 

Gambar di atas adalah contoh kasar dari sebuah huffman tree, karena pada dasaranya huffman tree ini adalah sebuah pohon biner, maka cabang yang dimiliki pun tidak sebanyak yang ada di tree general. Jika anda dapat perhatikan dengan baik, pada gambar terlihat sebuah angka “0″ dan angka “1″ pada jalur dari root ke sibling. Nomor tersebut tidak diletakkan secara sembarang, karena itu adalah aturan dalam pembuatan pohon huffman ini. Untuk seterusnya, jika root punya anak ke arah sebelah kiri maka anak tersebut juga akan mendapat sebuah “weight” di jalurnya yaitu angka “0″. Hal yang sama juga berlaku pada anak sebelah kanan, hanya saja “weight” yang diberikan bukan “0″ tetapi angka “1″.

Sekarang mari kita masuk ke dalam pembahasan selanjutnya. Kini muncul di benak anda bagaimana cara membuat sebuah coding huffman ini? Mudah saja sebenarnya. Langkahnya akan di sajikan di bawah ini :  

1. Misalkan String yang kita masukkan untuk kompresi adalah WINDA WINANTI, langkah selanjutnya adalah buat tabel frekuensi dari string tersebut. 

Peluang yang ada di sebelah kanan tabel adalah peluang kemunculan dari sebuah karakter dalam string.
2. Buat semua karakter menjadi simpul bebas dan sertakan probabilitas kemunculan karakter tersebut dalam string. Dalam contoh ini string yang digunakan adalah ‘WINDA<>WINANTI’. Maka simpulnya setelah diurut dari terkecil hingga terbesar menurut frekuensinya adalah seperti gambar di bawah ini :

3. Pilih dua simpul dengan frekuensi paling kecil lalu gabungkan kedua simpulnya menjadi simpul baru. Dalam contoh ini dua simpul terkecil adalah D dan T, lalu gabungkan menjadi simpul baru dengan menerapkan 1 + 1 = 2. Setelah simpul DT terbentuk maka urutkan lagi simpul DT dengan simpul sebelumnya sehingga menjadi seperti :

4. Lakukan kembali langkah 2 untuk semua simpul hingga terbentuk pohon Huffman. Dengan demikian maka langkah berikutnya adalah menggabungkan dua simpul dengan frekuensi terkecil yaitu simpul “Spasi” dan “DT” sehingga menghasilkan simpul baru yaitu “<>DT” dengan kekerapan 1 + 2 = 3. Setelah simpul “<>DT” terbentuk maka urutkan lagi simpul “<>DT” dengan simpul sebelumnya sehingga menjadi seperti : 

5. Gabungkan dua simpul dengan kekerapan terkecil yaitu simpul A dan W sehingga menghasilkan simpul baru yaitu AW dengan kekerapan 2 + 2 = 4. Setelah simpul AW terbentuk maka urutkan lagi simpul AW dengan simpul sebelumnya sehingga menjadi seperti :  

6. Gabungkan dua simpul dengan kekerapan terkecil yaitu simpul I dan N sehingga menghasilkan simpul baru yaitu IN dengan kekerapan 3 + 3 = 6. Setelah simpul IN terbentuk maka urutkan lagi simpul IN dengan simpul sebelumnya sehingga menjadi seperti :

7. Gabungkan dua simpul dengan kekerapan terkecil yaitu simpul <spasi>DT dan AW sehingga menghasilkan simpul baru yaitu <spasi>DTAW dengan kekerapan

3 + 4 = 7. Setelah simpul <spasi>DTAW terbentuk maka urutkan lagi simpul <spasi>DTAW dengan simpul sebelumnya sehingga menjadi seperti :

8. Gabungkan dua simpul dengan kekerapan terkecil yaitu simpul IN dan <spasi>DTAW sehingga menghasilkan simpul baru yaitu IN<spasi>DTAW dengan kekerapan 6 + 7 = 13. Simpul ini sudah menjadi akar dari pohon Huffman dan pembentukan pohon telah selesai.

Jika Pohon telah selesai, maka kita dapat memberikan coding huffman pada tabel yang sebelumnya kita buat di mulai dari root dan mengikuti aturan pemberian nomor “0″ dan “1″ sehingga hasilnya dapat dilihat di bawah ini :