Huffman Tree: Penggunaan Struktur Data Tree untuk Membuat Kode Awalan

Huffman's Tree (Pohon Huffman) adalah salah satu contoh penggunaan Struktur data Pohon atau Tree khususnya dalam algoritme yang dapat menghasilkan Kode Awalan (Prefix Code) dan pengkompresian data yang bersifat lossless data compression.

Algoritme Pembuatan Kode Huffman ditemukan oleh David A. Huffman. Algoritme ini, pada dasarnya akan menghasilkan kode awalan (prefix code) berupa sekumpulan kode biner dimana tidak ada kode biner yang menjadi awalan bagi kode biner lainnya. Algoritme pembuatan kode Huffman sudah banyak dikembangkan dan memiliki banyak variasi. Variasi-variasi algoritme pembuatan kode Huffman tersebut antara lain adalah n-ary Huffman Coding, Adaptive Huffman Coding, dan sebagainya.

Kode Awalan (Prefix Code) pada Algoritme Pembuatan Kode Huffman dapat didefinisikan sebagai himpunan kode, misalnya kode biner, sedemikan rupa sehingga tidak ada anggota himpunan tersebut yang akan menjadi awalan dari anggota yang lain. Gambar 1 menunjukkan perbedaan antara kode yang termasuk kode awalan (Prefix Code) dan kode yang tidak memenuhi syarat sebagai kode awalan.

Untuk menerapkan Algoritme Pembuatan Kode Huffman pada data yang tersusun dari sejumlah simbol, maka masukan yang dibutuhkan adalah simbol-simbol yang akan dikodekan beserta bobot (weight) dari masing-masing simbol tersebut. Bobot dari masing-masing simbol umumnya akan sebanding dengan probabilitas keberadaan simbol tersebut pada data yang akan dikompresi. Untuk data berbentuk teks, maka simbol yang digunakan adalah karakter-karakter pembentuk teks tersebut, sedangkan untuk bobot dapat digunakan nilai frekuensi kemunculan karakter tersebut di dalam teks.

Penciptaan Pohon Huffman (Huffman's Tree)

Untuk menciptakan Kode Awalan (Prefix Code) berdasarkan Algoritme Pembuatan Kode Huffman, maka terlebih dahulu harus diciptakan suatu Pohon Huffman. Langkah-langkah penciptaan Pohon Huffman yang dapat digunakan untuk membuat kode awalan dari karakter-karakter pada suatu data teks atau string adalah sebagai berikut :

• Baca semua karakter di dalam teks untuk menghitung frekuensi kemunculan setiap karakter. Setiap karakter penyusun teks dinyatakan sebagai simpul dari suatu pohon bersimpul tunggal. Setiap simpul yang menyatakan karakter tersebut akan memiliki nilai atau key berupa jumlah frekuensi kemunculan karakter tersebut.
• Hasil dari langkah diatas adalah diperolehnya suatu hutan (forest) yang terdiri dari sejumlah pohon bersimpul tunggal.
• Urutkan hutan (forest) yang sudah diperoleh berdasarkan jumlah nilai key yang ada pada masing-masing simpul setiap pohon , sehingga diperoleh urutan menaik dari pohon-pohon yang membentuk hutan tersebut.
• Lakukan penggabungan 2 pohon yang memiliki nilai key yang berdekatan. Penggabungan dilakukan dengan menciptkan simpul baru sebagai simpul induk dari 2 pohon yang digabungkan, dan nilai/key dari simpul induk tersebut adalah hasil jumlah nilai key dari kedua pohon yang sudah menjadi cabang dari simpul induk tersebut.
• Ulangi seluruh langkah-langkah diatas sampai seluruh pohon akan bergabung dan menjadi 1 pohon. Pohon inilah yang disebut sebagai Pohon Huffman (Huffman's Tree).

Contoh penerapan langkah-langkah penciptaan pohon Huffman diatas dapat dilihat pada gambar 2.

Gambar 2. Contoh Penerapan Langkah-Langkah Penciptaan Huffman's Tree (Dokpri)

Kode awalan berupa kode biner dari setiap karakter dari teks berdasarkan algoritme pembuatan kode Huffman dapat diperoleh dengan terlebih dahulu memberikan simbol bit o atau 1 pada setiap ruas (sisi) dari pohon Huffman yang sudah terbentuk. Ruas yang menghubungkan suatu simpul dengan cabang kirinya diberi simbol 0, sedangkan  ruas (sisi) yang menghubungkan suatu simpul dengan cabang kanannya diberi simbol 1.

Gambar 3 menunjukkan pemberian simbol 0 dan 1 pada ruas - ruas pohon Huffman dan hasil kode awalan yang diperoleh dari contoh Pohon Huffman di gambar 2. 

Gambar 3. Pemberian Simbol 0 dan 1 pada Ruas-Ruas Suatu  Pohon Huffman dan Hasil Kode Awalan Yang Diperoleh (Dokpri)

Penerjemahan String (Decoding Huffman's Code)

Jika suatu string yang berisi kode biner berupa kode huffman akan diterjemahkan kembali ke bentuk simbol/karakter, dan pohon huffman serta kode awalan sudah diketahui/diberikan, maka langkah-langkah yang dapat dilakaukan untuk menerjemahkan string tersebut adalah sebagai berikut :

• Baca string berisi kode biner yang akan diterjemahkan dan lakukan penelusuran di Pohon Huffman
• Penelusuran diatas dimulai dari akar sampai ke salah satu simpul daun yang akan berisi 1 karakter. Karakter/simbol yang diperoleh tersebut adalah terjemahan yang diinginkan.
• Ulang langkah 1 dan 2 sampai seluruh bit pada binary string akan diterjemahkan selesai diterjemahkan.