Download - 45984585-6-Kompresi-Huffman.pdf
1
����������� �������������
Kompresi adalah proses pengubahan sekumpulan data menjadi bentuk kode
dengan tujuan menghemat kebutuhan tempat penyimpanan dan waktu tramisi
data. Saat ini terdapat banyak algoritma untuk mengompres data termasuk teks,
seperti LIFO, LZHUF, LZ77, dan variannya (LZ78, LZW, GZIP), Dynamic
Markov Compression (DMC), Block-Sorting Lossless, Run-Length, Shannon-
Fano, Arithmetic, PPM (Prediction by Partial Matching), Burrows-Wheeler Block
Sorting, dan Half Byte.
Salah satu algoritma yang sering digunakan dalam teknik pemampatan
adalah kode huffman. Teknik ini mampu memampatkan sampai dengan 30 persen
dari ukuran semula. Tetapi dengan proses decoding string biner menjadi data
kembali masih kurang efisien.
Dengan menggunakan algoritma Huffman, proses pengompresan teks
dilakukan dengan menggunakan prinsip pengkodean, yaitu tiap karakter
dikodekan dengan rangkaian beberapa bit sehingga menghasilkan hasil yang lebih
optimal.
Berdasarkan tipe peta kode yang digunakan untuk mengubah pesan awal (isi
file input) menjadi sekumpulan codeword, metode kompresi terbagi menjadi dua
kelompok, yaitu :
(a) Metode statik : menggunakan peta kode yang selalu sama. Metode ini
membutuhkan dua fase (two-pass): fase pertama untuk menghitung
probabilitas kemunculan tiap simbol/karakter dan menentukan peta
kodenya, fase kedua untuk mengubah pesan menjadi kumpulan kode yang
akan ditransmisikan. Contoh: Algoritma Huffman Statik.
(b) Metode dinamik (adaptif) : menggunakan peta kode yang dapat berubah
dari waktu ke waktu. Metode ini disebut adaptif karena peta kode mampu
beradaptasi terhadap perubahan karakteristik isi file selama proses
kompresi berlangsung. Metode ini bersifat one-pass, karena hanya
2
diperlukan satu kali pembacaan terhadap isi file. Contoh: Algoritma LZW
dan DMC.
Berdasarkan teknik pengkodean/pengubahan simbol yang digunakan,
metode kompresi dapat dibagi ke dalam tiga kategori, yaitu :
(a) Metode symbolwise : menghitung peluang kemunculan dari tiap
simbol dalam file input, lalu mengkodekan satu simbol dalam satu
waktu, dimana simbol yang sering muncul diberi kode lebih pendek
dibandingkan dengan simbol yang jarang muncul, contoh:
algoritma Huffman.
(b) Metode Dictionary : menggantikan karakter/fragmen dalam file
input dengan indeks lokasi dari karakter/fragmen tersebut dalam
sebuah kamus (dictionary), contoh: algoritma LZW.
(c) Metode predictive : menggunakan model finite-context atau finite-
state untuk memprediksi distribusi probabilitas dari simbol-simbol
selanjutnya, contoh: algoritma DMC.
Ada beberapa faktor yang sering menjadi pertimbangan dalam memilih
suatu metode kompresi yang tepat, yaitu kecepatan kompresi, sumber daya yang
dibutuhkan (memori, kecepatan PC), ukuran file hasil kompresi, besarnya
redundansi, dan kompleksitas algoritma. Tidak ada metode kompresi yang paling
efektif untuk semua jenis file.
Algoritma Huffman
Algoritma Huffman, yang dibuat oleh seorang mahasiswa MIT bernama
David Huffman pada tahun 1952, merupakan salah satu metode paling lama dan
paling terkenal dalam kompresi teks. Algoritma Huffman menggunakan prinsip
pengkodean yang mirip dengan kode Morse, yaitu tiap karakter (simbol)
dikodekan hanya dengan rangkaian beberapa bit, dimana karakter yang sering
muncul dengan rangkaian bit yang pendek dan karakter yang jarang muncul
dikodekan dengan rangkaian bit yang lebih panjang.
Berdasarkan tipe peta kode yang digunakan untuk mengubah pesan awal (isi
data yang diinputkan) menjadi sekumpulan codeword, algoritma Huffman
3
termasuk kedalam kelas yang menggunakan metode statik. Metode statik adalah
metode yang selalu menggunakan peta kode yang sama, metode ini membutuhkan
dua fase (two-pass): fase pertama untuk menghitung probabilitas kemunculan tiap
simbol/karakter dan menentukan peta kodenya, fase kedua untuk mengubah pesan
menjadi kumpulan kode yang akan ditransmisikan.
Sedangkan berdasarkan teknik pengkodean simbol yang digunakan,
algoritma Huffman menggunakan metode symbolwise. Metode symbolwise adalah
metode yang menghitung peluang kemunculan dari tiap simbol dalam file input,
lalu mengkodekan satu simbol dalam satu waktu, dimana simbol yang sering
muncul diberi kode lebih pendek dibandingkan dengan simbol yang jarang
muncul.
Algoritma Huffman secara lengkap :
Gambar 1. Algoritma kompresi Huffman
1. Pass Pertama Baca (scan) file input dari awal hingga akhir untuk menghitung frekuensi kemunculan tiap karakter dalam file. n � jumlah semua karakter dalam file input. T � daftar semua karakter dan nilai peluang kemunculannya dalam file input. 2. Pass Kedua Ulangi sebanyak (n – 1) kali : a. Item m1 dan m2 � dua subset dalam T dengan nilai peluang yang lebih
kecil. b. Gantikan m1 dan m2 dengan sebuah item {m1,m2} dalam T, dimana nilai
peluang dari item yang baru ini adalah penjumlahan dari nilai peluang m1 dan m2.
c. Buat node baru {m1,m2} sebagai father node dari m1 dan m2 dalam pohon Huffman.
3. T sekarang tinggal berisi satu item, item ini sekaligus menjadi node akar pohon Huffman. Panjang kode untuk suatu simbol adalah jumlah berapa kali simbol tersebut bergabung dengan item lain dalam T.
4
Pembentukan Pohon Huffman
Kode Huffman pada dasarnya merupakan kode prefiks (prefix code). Kode
prefiks adalah himpunan yang 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,
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. Pohon biner ini biasa disebut pohon Huffman.
Langkah-langkah pembentukan pohon Huffman sebagai berikut :
1. Baca semua karakter di dalam data untuk menghitung frekuensi
kemunculan setiap karakter. Setiap karakter penyusun data dinyatakan
sebagai pohon bersimpul tunggal. Setiap simpun di-assign dengan
frekuensi kemunculan karakter tersebut.
2. Terapkan strategi greedy sebagai berikut : gabungkan dua buah pohon
yang mempunyai frekuensi terkecil pada sebuah akar. Akar mempunyai
frekuensi yang merupakan jumlah dari frekuensi dua buah pohon
penyusunnya.
3. Ulangi langkah 2 sampai hanya tersisa satu buah pohon Huffman. Agar
pemilihan dua pohon yang akan digabungkan berlangsung cepat, maka
semua pohon yang ada selalu terurut menaik berdasarkan frekuensi.
Proses Encoding
Encoding adalah cara menyusun string biner dari data 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 sebagai berikut :
1. Tentukan karakter yang akan di-encoding.
2. Mulai dari akar, baca setiap bit yang ada pada cabang bersesuaian sampai
ketemu daun dimana karakter itu berada.
5
3. Ulangi langkah 2 sampai seluruh karakter di-encoding.
Proses Decoding
Decoding merupakan kebalikan dari encoding. Decoding berarti menyusun
data dari string biner menjadi sebuah karakter kembali. Decoding dapat dilakukan
dengan 2 cara, yang pertama menggunakan pohon Huffman dan yang kedua
menggunakan tabel kode Huffman. Langkah-langkah men-decoding suatu string
biner adalah sebagai berikut :
1. Mulai dari akar.
2. Baca sebuah bit dari string biner.
3. Untuk setiap bit pada langkah 2, lakukan traversal data pada cabang yang
bersesuaian.
4. Ulangi langkah 2 dan 3 sampai bertemu daun. Kodekan rangkaian bit yang
telah dibaca dengan karakter didaun.
5. Ulangi dari langkah 1 sampai semua bit di dalam string habis.
Kompleksitas Algoritma Huffman
Algoritma Huffman mempunyai kompleksitas waktu O(n log n), karena
dalam melakukan sekali proses itersi pada saat penggabungan dua buah pohon
yang mempunyai frekuensi terkecil pada sebuah akar memerlukan waktu O(log n)
dan proses ini dilakukan berkali-kali sampai hanya tersisa satu buah pohon
Huffman itu berarti dilakukan sebanyak n kali.
Contoh Kasus
Dasar pemikiran algoritma Huffman adalah bahwa setiap karakter ASCII
biasanya diwakili oleh 8 bits. Jadi misalnya suatu file berisi deretan karakter
“ABACAD” maka ukuran file tersebut adalah 6 x 8 bits = 48 bit atau 6 bytes. Jika
setiap karakter tersebut di beri kode lain misalnya A=1, B=00, C=010, dan
D=011, berarti kita hanya perlu file dengan ukuran 11 bits (10010101011), yang
perlu diperhatikan ialah bahwa kode-kode tersebut harus unik atau dengan kata
6
lain suatu kode tidak dapat dibentuk dari kode-kode yang lain. Pada contoh diatas
jika kode D kita ganti dengan 001, maka kode tersebut dapat dibentuk dari kode B
ditambah dengan kode A yaitu 00 dan 1, tapi kode 011 tidak dapat dibentuk dari
kode-kode yang lain. Selain itu karakter yang paling sering muncul, kodenya
diusahakan lebih kecil jumlah bitnya dibandingkan dengan karakter yang jarang
muncul. Pada contoh di atas karakter A lebih sering muncul (3 kali), jadi kodenya
dibuat lebih kecil jumlah bitnya dibanding karakter lain.
Untuk menetukan kode-kode dengan kriteria bahwa kode harus unik dan
karakter yang sering muncul dibuat kecil jumlah bitnya, kita dapat menggunakan
algoritma Huffman.
Sebagai contoh lainnya, dalam kode ASCII string 7 huruf “ABACCDA”
membutuhkan representasi 7 x 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 diatas, frekuensi kemunculan A = 3, B = 1, C = 2, D = 1.
Pohon Huffman
1.
2.
A:3 B:1 C:2 D:1
A:3 BD : 2 C:2
B:1 D:1
0 1
7
3.
4.
Gambar 2. Pohon Huffman untuk karakter “ABACCDA”
Karakter String biner Huffman A 0 B 110 C 10 D 111
Tabel 1. Kode Huffman untuk karakter “ABCD”
A:3 BDC : 4
1
C:2
B:1 D:1
BD : 2
1 0
ABDC : 7
A:3
C:2
B:1 D:1
BDC : 4
BD : 2
1
1
1 0
0
0
8
Proses Decoding
Gambar 3. Proses Decoding dengan menggunakn kode Huffman
Sebagai contoh kita akan men-decoding string biner yang bernilai “111”
(lihat gambar 3) setelah kita telusuri dari akar, maka kita akan menemukan bahwa
string yang mempunyai kode Huffman “111” adalah karakter D.
Cara yang kedua adalah dengan menggunakan tabel kode Huffman. Sebagai
contoh kita akan menggunakan tabel 1 untuk merepresentasikan string
“ABACCDA”. Dengan menggunakan tabel 1 string tersebut akan
direpresentasikan menjadi rangkaian bit : 0 110 0 10 10 1110. Jadi, jumlah bit
yang dibutuhkan hanya 13 bit. Dari tabel 1 tampak bahwa kode untuk sebuah
simbol/karakter tidak boleh menjadi awalan dari kode simbol yang lain guna
menghindari keraguan (ambiguitas) dalam proses dekompresi atau decoding.
Karena kode Huffman yang dihasilkan unik, maka proses decoding dapat
dilakukan dengan mudah. Contoh: saat membaca kode bit pertama dalam
rangkaian bit “011001010110”, yaitu bit “0”, dapat langsung disimpulkan bahwa
kode bit “0” merupakan pemetaan dari simbol “A”. Kemudian baca kode bit
selanjutnya, yaitu bit “1”. Tidak ada kode Huffman “1”, lalu baca kode bit
selanjutnya, sehingga menjadi “11”. Tidak ada juga kode Huffman “11”, lalu baca
lagi kode bit berikutnya, sehingga menjadi “110”. Rangkaian kode bit “110”
adalah pemetaan dari simbol “B”.
ABDC : 7
BDC : 4
BD : 2
B:1 D:1
1 0
A:3
0 1
1
C:2
0
9
Pengujian algoritma Huffman
Pada pengujian digunakan, kita akan meng-encoding sebuah teks yang berisi
100.000 string, diantaranya 45.000 karakter ‘g’, 13.000 karakter ‘o’, 12.000
karakter ‘p’, 16.000 karakter ‘h’, 9.000 karakter ‘e’, dan 5.000 karakter ‘r’ dengan
menggunakan 3 cara, yaitu dengan menggunakan kode ASCII , kode 3-bit dan
kode Huffman. Setelah itu ketiga kode tersebut akan dibandingkan satu sama
lainnya.
a. Kode ASCII
Karakter ASCII Biner g 103 1100111 o 111 1101111 p 112 1110000 h 104 1101000 e 101 1100101 r 114 1110010
Tabel 2. Kode ASCII untuk karakter “g, o, p, h, e, r”
Untuk meng-encoding teks tersebut kita membutuhkan sebanyak :
• Untuk karakter ‘g’
45.000 x 8 bit (1100111) = 360.000 bit
• Untuk karakter ‘o’
13.000 x 8 bit (1100111) = 104.000 bit
• Untuk karakter ‘p’
12.000 x 8 bit (1100111) = 96.000 bit
• Untuk karakter ‘h’
16.000 x 8 bit (1100111) = 128.000 bit
• Untuk karakter ‘e’
9.000 x 8 bit (1100111) = 72.000 bit
• Untuk karakter ‘r’
5.000 x 8 bit (1100111) = 40.000 bit
Jumlah = 800.000 bit
10
b. 3 – bit Kode
Karakter Kode String Biner g 0 000 o 1 001 p 2 010 h 3 011 e 4 100 r 5 101
Tabel 3. 3 – bit Kode untuk karakter “g, o, p, h, e, r”
Untuk meng-encoding teks tersebut kita membutuhkan sebanyak :
• Untuk karakter ‘g’
45.000 x 3 bit (000) = 135.000 bit
• Untuk karakter ‘o’
13.000 x 3 bit (001) = 39.000 bit
• Untuk karakter ‘p’
12.000 x 3 bit (010) = 36.000 bit
• Untuk karakter ‘h’
16.000 x 3 bit (011) = 48.000 bit
• Untuk karakter ‘e’
9.000 x 3 bit (100) = 27.000 bit
• Untuk karakter ‘r’
5.000 x 3 bit (101) = 15.000 bit
Jumlah = 300.000 bit
c. Kode Huffman
Karakter Frekuensi Peluang Kode Huffman g 45.000 3/13 0 o 13.000 3/13 101 p 12.000 1/13 100 h 16.000 1/13 111 e 9.000 1/13 1101 r 5.000 1/13 1100
Tabel 4. Kode Huffman untuk karakter “g, o, p, h, e, r”
11
Untuk meng-encoding teks tersebut kita membutuhkan sebanyak :
• Untuk karakter ‘g’
45.000 x 1 bit (0) = 45.000 bit
• Untuk karakter ‘o’
13.000 x 3 bit (101) = 39.000 bit
• Untuk karakter ‘p’
12.000 x 3 bit (110) = 36.000 bit
• Untuk karakter ‘h’
16.000 x 3 bit (111) = 48.000 bit
• Untuk karakter ‘e’
9.000 x 4 bit (1101) = 36.000 bit
• Untuk karakter ‘r’
5.000 x 4 bit (1100) = 20.000 bit
Jumlah = 224.000 bit
Dari data diatas kita dapat lihat bahwa dengan menggunakan kode ASCII
untuk meng-encoding teks tersebut membutuhkan 800.000 bit, sedangkan dengan
menggunakan 3-bit kode dibutuhkan 300.000 bit dan dengan menggunakan kode
Huffman hanya membutuhkan 224.000. Dengan menggunakan data tersebut maka
dapat kita lihat bahwa dengan menggunakan algoritma Huffman dapat
mengompres teks sebesar 70% dibandingkan kita menggunakan kode ASCII dan
sebesar 25,3% dibandingkan kita menggunakan 3-bit kode.
Kesimpulan
1. Algoritma Huffman adalah salah satu algoritma kompresi, yang banyak
digunakan dalam kompresi teks.
2. Terdapat 3 tahapan dalam menggunakan algoritma Huffman, yaitu:
• membentuk pohon Huffman
• melakukan encoding dengan menggunakan pohon Huffman, dan
• melakukan decoding
12
3. Algoritma Huffman mempunyai kompleksitas waktu O(n log n).
4. Algoritma Huffman adalah salah satu algoritma yang menggunakan
prinsip algoritma greedy dalam penyusunan pohon Huffman
5. Dari hasil pengujian yang dilakukan, algoritma Huffman dapat
mengompres teks sebesar 70% jika dibandingkan dengan menggunakan
kode ASCII dan sebesar 25,3% jika dibandingkan dengan kita
menggunakan 3-bit kode.
6. Hasil kompresi Huffman lebih baik dibandingkan LZW hanya pada kasus
file biner, file multimedia, file gambar, dan file hasil kompresi. Algoritma
Huffman memberikan hasil yang relatif hampir sama untuk setiap kasus
uji. Dan secara rata-rata algoritma Huffman membutuhkan waktu
kompresi sebesar 555,8 Kbyte/Sec ± 55,8. Kecepatan kompresi algoritma
Huffman hampir merata untuk semua kategori file. Serta rata-rata
algoritama Huffman menghasilkan rasio file hasil kompresi sebesar 71,4 %
± 15,4.
Pustaka
1. Huffman Coding http://www.en.wikipedia.org/wiki/Huffman_coding 2. Practical Huffman Coding http://www.compressconsult.com/huffman/ 3. Kompresi Teks Menggunakan Algoritma Huffman www.unpar.ac.id 4. PlanetMath Huffman Coding www.planetmath.org 5. Huffman Coding A CS2 Assigment www.cs.duke.edu 6. Munir Rinaldi, 2005, Diktat Kuliah IF2251Strategi Algoritmik, Penerbit ITB. 7. Cormack, G.V., Horspool, R.N., “Data Compression Using Dynamic Markov
Compression”, University of Waterloo and University of Victoria, 1986.