KOMPRESI DATA TEKS MENGGUNAKAN ALGORITMA HUFFMAN

ALGORITMA HUFFMAN adalah salah satu algoritma kompresi. Algoritma huffman merupakan algoritma yang paling terkenal untuk mengkompres teks. Terdapat tiga fase dalam menggunakan algoritma huffman untuk mengkompres sebuah teks, sebagai berikut :

1. Fase pembentukan pohon Huffman
2. Fase Encoding
3. Fase Decoding

Prinsip dari algoritma Huffman adalah karakter yang sering  muncul di-encoding dengan rangkaian bit yang pendek dan karakter yang jarang muncul di-encoding dengan rangkaian bit yang lebih panjang. Teknik kompresi algoritma Huffman mampu memberikan penghematan pemakaian memori sampai 30%

Algoritma Huffman mempunyai kompleksitas 0(n log n) untuk himpunan dengan n karakter

Kode Huffman pada dasarnya merupakan kode prefiks (prefix code). Kode prefiks adalah himpunan yang berisi sekumpulan kode biner, dimana pada kode prefik ini tidak ada kode biner yang menjadi awal bagi kode biner yang lain. Kode prefiks biasanya direpresentasikan sebagai pohon biner yang diberikan nilai atau label. Untuk cabang kiri pada pohon biner  diberi label 0, sedangkan pada cabang kanan pada pohon biner diberi label 1. Rangkaian bit yang terbentuk pada setiap lintasan dari akar ke daun merupakan kode prefiks untuk karakter yang berpadanan. Pohon biner ini biasa disebut pohon Huffman.

• Langkah-langkah pembentukan pohon huffman :

1. Baca semua karakter di dalam teks untuk menghitung frekuensi kemunculan setiap karakter. Setiap karakter penyusun teks dinyatakan sebagai pohon bersimpul tunggal. Setiap simpul di-assign dengan frekuensi kemunculan karakter tersebut.
2. Terapkan strategi algoritma greedy sebagai berikut : Gabungkan 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 yang ada selalu terurut menaik berdasarkan frekuensi.

Sebagai contoh, dalam kode ASCII string 7 huruf “ABACCDA” membutuhkan representasi 7 × 8 bit = 56 bit (7 byte), dengan rincian sebagai berikut:

A = 01000001

B = 01000010 

A = 01000001

C = 01000011

C = 01000011

D = 01000100

A = 01000001

Pada string di atas, frekuensi kemunculan A = 3, B = 1, C = 2, dan D = 1, Untuk lebih jelas mengenai proses pembentukkan pohon hufman, dapat dilihat ilustrasi pembuatan pohonnya dibawah ini:

• Proses Encoding

Encoding adalah cara menyusun string biner dari teks yang ada. Proses encoding untuk satu karakter dimulai dengan membuat pohon Huffman terlebih dahulu. Setelah itu, kode untuk satu karakter dibuat dengan menyusun nama string biner yang dibaca dari akar sampai ke daun pohon Huffman.

Langkah-langkah untuk men-encoding suatu string biner adalah sebagai berikut :

1. Tentukan karakter yang akan di-encoding

2. Mulai dari akar, baca setiap bit yang ada pada cabang yang bersesuaian sampai ketemu daun dimana karakter itu berada

3. Ulangi langkah 2 sampai seluruh karakter diencoding 

Sebagai contoh kita dapat melihat tabel dibawah ini, yang merupakan hasil encoding untuk pohon Huffman.

Kode Huffman untuk karakter "ABCD"

Dengan menggunakan kode Huffman ini, string “ABACCDA” direpresentasikan menjadi rangkaian bit : 0 110 0 10 10 111 0. Jadi, jumlah bit yang dibutuhkan hanya 13 bit.

• Proses Decoding

Decoding merupakan kebalikan dari encoding. Decoding berarti menyusun kembali data dari string biner menjadi sebuah karakter kembali. Decoding dapat dilakukan dengan dua cara, yang pertama dengan menggunakan pohon  Huffman dan yang kedua dengan menggunakan tabel kode Huffman.

Langkah-langkah men -decoding suatu string biner dengan menggunakan pohon Huffman adalah sebagai berikut :

1. Baca sebuah bit dari string biner.
2. Mulai dari akar
3. Untuk setiap bit pada langkah 1, lakukan traversal pada cabang yang bersesuaian.
4. Ulangi langkah 1, 2 dan 3 sampai bertemu daun. Kodekan rangkaian bit yang telah dibaca dengan karakter di daun.
5. Ulangi dari langkah 1 sampai semua bit di dalam string habis. Sebagai contoh kita akan men-decoding string biner yang bernilai ”111”

Proses decoding menggunakan pohon Huffman

Setelah kita telusuri dari akar, maka kita akan menemukan bahwa string yang mempunyai kode Huffman “111” adalah karakter D.

Sekian artikel kali ini, apabila masih banyak kekurangan saya mohon maaf

Terimakasih & Semoga bermanfaat.