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”



45.000 x 3 bit (000) = 135.000 bit


13.000 x 3 bit (001) = 39.000 bit


12.000 x 3 bit (010) = 36.000 bit


16.000 x 3 bit (011) = 48.000 bit


9.000 x 3 bit (100) = 27.000 bit


5.000 x 3 bit (101) = 15.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



45.000 x 1 bit (0) = 45.000 bit


13.000 x 3 bit (101) = 39.000 bit


12.000 x 3 bit (110) = 36.000 bit


16.000 x 3 bit (111) = 48.000 bit


9.000 x 4 bit (1101) = 36.000 bit


5.000 x 4 bit (1100) = 20.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.

45984585-6-kompresi-huffman.pdf

Documents