Salah satu algorithma yang sering digunakan dalam teknik pemampatan data adalah Kode Huffman (Huffman’s Code). Proses pemampatan dengan menggunakan Kode Huffman dilakukan dengan pengkodean tiap karakter dengan rangkaian beberapa bit sehingga menghasilkan hasil yang optimal.
Kode Huffman secara luas telah digunakan pada berbagai aplikasi pemampatan dan transmisi data digital, seperti pada mesin fax, modem, jaringan komputer, high-definition televition (HDTV) dan berbagai aplikasi yang berhubungan dengan transmisi data. Didalam pemampatan data, kode Huffman mampu memampatkan media penyimpan data dan waktu transmisi data antara 20%-90%.
Tujuan dari penulisan makalah ini adalah untuk mengetahui keefektifan algorithma Huffman dalam pemampatan data.
Untuk mencapai tujuan tersebut, penulis melakukan serangkaian kegiatan yaitu mengumpulkan data dan eferensi-referensi serta melakukan studi pustaka.
Dasar Teori
1. Algorithma Huffman
Algorithma Huffman, dibuat pertama kali oleh Prof. David A. Huffman (1925-1999) pada tahun 1952 sebagai desertasi Ph.D dengan publikasi berjudul ”A Method for the Construction of Minimum-Redundancy Codes”. Algorithma Huffman menggunakan prinsip bahwa setiap karakter dikodekan dengan serangkaian bit, dimana karakter yang sering muncul dikodekan dengan rangkaian bit yang pendek dan karakter yang jarang muncul dikodekan dengan rangkian bit yang lebih panjang. [4].
Berdasarkan tipe pemetaan kode yang digunakan untuk mengubah data awal menjadi codeword, algorithma Huffman adalah algorithma yang menggunakan metode statik, yaitu selalu menggunakan pemetaan kode yang sama. Dalam metode ini ada dua fase yang harus dilalui, yaitu: fase pertama adalah menghitung probabilitas kemunculan tiap karakter dan menentukan pemetaan kodenya, dan fase kedua adalah mengubah data menjadi sekumpulan kode yang akan ditransmisikan.
Berdasarkan teknik pengkodeannya, algorithma Huffman menggunakan metode symbolwise, yaitu menghitung peluang kemunculan dari setiap karakter, dimana karakter yang sering muncul diberi kode yang lebih pendek dibandingkan dengan karakter yang jarang muncul.[3]
2. Pembentukan Pohon Huffman (Huffman Tree)
Kode Huffman adalah string biner yang digunakan untuk mengkodekan setiap karakter di dalam data. Kode Huffman pada dasarnya merupakan kode prefiks (prefiks code), yaitu berisi sekumpulan kode biner yang dalam hal ini tidak ada kode biner yang menjadi awal bagi kode biner yang lain.
Kode prefiks biasanya direpresentasikan sebagai pohon biner yang berlabel 0 (cabang kiri) atau 1 (cabang kanan). Rangkaian bit yang terbentuk pada setiap lintasan dari akar sampai tree merupakan kode prefiks untuk karakter yang berpadanan.
Pada awalnya David Huffman hanya menencoding karakter dengan hanya menggunakan pohon biner biasa, namun setelah itu David Huffman menemukan bahwa penggunaan algoritma greedy dapat membentuk kode prefiks yang optimal.[5]
Penggunaan algoritma greedy pada algoritma Huffman adalah pada saat pemilihan dua pohon dengan frekuensi terkecil dalam membuat pohon Huffman. Algoritma greedy ini digunakan pada pembentukan pohon Huffman agar meminimumkan total cost yang dibutuhkan. Cost yang digunakan untuk menggabungkan dua buah pohon pada akar setara dengan jumlah frekuensi dua buah pohon yang digabungkan, oleh karena itu total cost pembentukan pohon Huffman adalah jumlah total seluruh penggabungan. Penggabungan dua buah pohon dilakukan setiap langkah dan algoritma Huffman selalu memilih dua buah pohon yang mempunyai frekuensi terkecil untuk meminimumkan total cost. Oleh karena itu algoritma Huffman adalah salah satu contoh algoritma yang menggunaan dari algoritma Greedy.
Langkah-langkah pembentukan pohon Huffman adalah sebagai berikut:
1. Baca semua karakter di dalam data untuk menghitung frekuensi kemunculan karakter. Setiap karakter penyusun teks dinyatakan sebagai pohon bersimpul tunggal.Setiap simpul di-assign dengan frekuensi kemunculan karakter.
2. Terapkan algorithma Greedy yaitu dengan menggabungkan dua buah pohon yang mempunyai frekuensi terkecil pada sebuah akar. Setelah digabungkan akar tersebut akan mempunyai frekuensi yang merupakan jumlah dari frekuensi dua buah pohon-pohon penyusunnya.
3. Ulangi langkah 2 sampai hanya tersisa satu buah pohon Huffman. Agar pemilihan dua pohon yang akan digabungkan berlangsung cepat, maka semua harus terurut naik berdasarkan frekuensinya. [6]
Sebagai contoh diberikan tabel frekuensi untuk setiap karakter sebagai berikut:
| No | Karakter | Frekuensi |
| 1 | Spasi | 76 |
| 2 | A | 77 |
| 3 | E | 120 |
| 4 | F | 24 |
| 5 | H | 50 |
| 6 | M | 24 |
| 7 | N | 67 |
| 8 | R | 59 |
| 9 | T | 85 |
| 10 | U | 37 |
Tidak ada komentar:
Posting Komentar