Kode Huffman

Kode Huffman pada dasarnya merupakan kode Initialize model prefiks (prefix code) yang merupakan himpunan yang berisi sekumpulan kode biner. Kode prefiks direpresentasikan sebagai pohon biner berlabel dimana setiap sisi diberi label 0 (cabang kiri) atau 1 (cabang kanan).
Rangkaian bit yang terbentuk pada setiap lintasan dari akar ke daun merupakan kode prefiks untuk karakter yang berpadanan.
Kode ini pun memiliki berbagai macam variasi antara lain :

1. Adaptive kode Huffman
2. Length-Limited kode Huffman
3. N-Ary Huffman Template Algoritma
4. Huffman With Unequal Letter Costs

1. Macam-macam Variasi Kode Huffman

A. Adaptive kode Huffman
Metode Adaptive digunakan pada saat pembaharuan (update) model algoritma baru baik dari proses kompresi maupun dekompresi
Konsep Dasar :
Encoder :
Initialize_model
Repeat for each character
{
Encode character
Update_model
}
Decoder
Initialize_model
Repeat for each character
{
Decode character
Update_model
}
Masalahnya adalah bagaimana meng-update model algoritma yang terdiri dari menambah jumlah dan mengupdate pohon Huffman. Caranya adalah dengan meng-update bagian pohon di mana terjadi proses pemampatan/nirmampat.

Pohon Huffman diinisialisasikan dengan simpul single yang dikenal dengan Not-Yet-Transmitted (NYT) Code yang dikirimkan setiap kali ditemukan karakter baru. Algoritma bekerja dengan penomoran yang unik pada simpul dengan jumlah daun yang berbeda.

Langkah-langkah peng-update-an model
1. Jika kode yang pertama kali ditemukan adalah NYT, maka tambahkan dua simpul pada simpul NYT. Satu simpul sebagai simpul NYT dan simpul yang lain sebagai daun. Tambahkan jumlah daun. Jika bukan NYT, langsung menuju daun.

2. Jika pada blok tidak terdapat angka tertinggi, tukarkan dengan angka tertinggi pada blok.

3. Tambahkan jumlah dari simpul tersebut.

4. Periksa apakah simpul tersebut merupakan simpul akar. Jika bukan pergi ke simpul parent.

B. Length-Limited Huffman Coding

Variasi Huffman ini digunakan untuk mendapatkan jarak kedalaman terkecil dari suatu simbol, dengan batasan bahwa panjang masing-masing yang dimasukkan tidak kurang dari nilai konstanta yang diberikan. Metode ini biasanya digunakan pada GNU gzip.
Langkah-langkah dalam Metode Length-Limited Huffman adalah :

1. Memilih dua atau lebih simbol yang ingin dimampatkan

2. Gabungkan simbol-simbol tersebut dan gantikan dengan pseudo-symbol beserta frekuensinya.

3. Lakukan langkah di atas secara Literatif sampai semua simpul yang ada menjadi satu simpul akar.

4. Jika simpul-simpul tersebut memiliki frekuensi yang sama, maka pilihlah simpul dengan kedalaman terpendek.

C. Binary Huffman Template Algorima

Algoritma ini sebenarnya mirip dengan algoritma Huffman biasa. Bedanya, pohon Huffman yang digunakan dalam algoritma ini memiliki lebih dari dua akar (0 dan 1). Sementara dengan Huffman template algorithm, memungkinkan untuk menggunakan ukuran non-numerik (ukuran selain biaya dan frekuensi).

D. Huffman With Unequal Letter Costs
Pada metode ini terdapat suatu permasalahan dimana suatu set kode yang terdiri dari beberapa huruf dengan frekuensi kemunculan dan biaya (cost) yang berbeda. Metode ini ditujukan untuk mencari kode prefiks (prefix code) dan menghitung biaya minimumnya (minimum cost). Prefiks Kode merupakan sekumpulan kode yang prefix-free. Biaya (cost ) dari ini merupakan jumlah biaya dari masing-masing huruf pada kode tersebut.
Langkah-langkah umum metode Kode Huffman with Unequal Letter Cost :

1. Mencari kode K-Prefiks yang optimal.

2. Mengubah kode K-Prefiks menjadi kode prefiks yang optimal.

3. Setelah didapat kode hasil kemudian hitung biaya (cost)-nya.

Kesimpulan
Kode Huffman ternyata memiliki banyak variasi, di antaranya adalah Kode Adaptive Huffman,Kode Length-limited Huffman, n-ary Huffman template algoritma, dan Kode Huffman dengan unequal letter costs. Berbagai teknik ini dapat digunakan pada aplikasi yang berbeda-beda, tetapi umumnya digunakan untuk pemampatan data. Hal ini wajar saja terjadi karena inti dari seluruh variasi teknik ini adalah sama dengan kode Huffman, yaitu memecahkan permasalahan optimasi.