Kompresi Data adalah salah satu subyek di bidang teknologi informasi yang saat ini telah
diterapkan secara luas. Gambar-gambar yang anda dapatkan di berbagai situs internet pada
umumnya merupakan hasil kompresi ke dalam format GIF atau JPEG. File video MPEG adalah
hasil proses kompresi pula. Penyimpanan data berukuran besar pada server pun sering
dilakukan melalui kompresi. Sayangnya tidak banyak mata kuliah yang memberikan perhatian
pada subyek ini secara memadai. Tulisan berikut ini akan memperkenalkan tentang dasar-dasar Kompresi Data kepada anda.
Kompresi Data merupakan cabang ilmu komputer yang bersumber dari Teori
Informasi. Teori Informasi sendiri adalah salah satu cabang Matematika yang
berkembang sekitar akhir dekade 1940-an. Tokoh utama dari Teori Informasi adalah
Claude Shannon dari Bell Laboratory. Teori Informasi mengfokuskan pada berbagai
metode tentang informasi termasuk penyimpanan dan pemrosesan pesan. Teori
Informasi mempelajari pula tentang redundancy (informasi tak berguna) pada pesan.
Semakin banyak redundancy semakin besar pula ukurang pesan, upaya mengurang
redundancy inilah yang akhirnya melahirkan subyek ilmu tentang Kompresi Data.
Teori Informasi menggunakan terminologi entropy sebagai pengukur berapa
banyak informasi yang dapat diambil dari sebuah pesan. Kata “entropy” berasal dari
ilmu termodinamika. Semakin tinggi entropy dari sebuah pesan semakin banyak
informasi yang terdapat di dalamnya. Entropy dari sebuah simbol didefinisikan sebagai
nilai logaritma negatif dari probabilitas kemunculannya. Untuk menentukan konten
informasi dari sebuah pesan dalam jumlah bit dapat digunakan rumus sebagai berikut:
number of bits = -log base 2 (probability)
Entropy dari keseluruhan pesan adalah jumlah dari keseluruhan entropy dari seluruh
symbol.
Teknik Kompresi Data dapat dibagi menjadi dua kategori besar, yaitu:
1. Lossy Compression
Lossy compression menyebabkan adanya perubahan data dibandingkan sebelum
dilakukan proses kompresi. Sebagai gantinya lossy compression memberikan
derajat kompresi lebih tinggi. Tipe ini cocok untuk kompresi file suara digital dan
gambar digital. File suara dan gambar secara alamiah masih bisa digunakan
walaupun tidak berada pada kondisi yang sama sebelum dilakukan kompresi.
2. Lossless Compression
Sebaliknya Lossless Compression memiliki derajat kompresi yang lebih rendah
tetapi dengan akurasi data yang terjaga antara sebelum dan sesudah proses
kompresi. Kompresi ini cocok untuk basis data, dokumen atau spreadsheet. Pada
lossless compression ini tidak diijinkan ada bit yang hilang dari data pada proses
kompresi.
Secara umum kompresi data terdiri dari dua kegiatan besar, yaitu Modeling dan
Coding. Proses dasar dari kompresi data adalah menentukan serangkaian bagian dari
data (stream of symbols) mengubahnya menjadi kode (stream of codes). Jika proses
kompresi efektif maka hasil dari stream of codes akan lebih kecil dari segi ukuran
daripada stream of symbols. Keputusan untuk mengindentikan symbols tertentu
dengan codes tertentu adalah inti dari proses modeling. Secara umum dapat diartikan
bahwa sebuah model adalah kumpulan data dan aturan yang menentukan pasangan
antara symbol sebagai input dan code sebagai output dari proses kompresi. Sedangkan
coding adalah proses untuk menerapkan modeling tersebut menjadi sebuah proses
kompresi data.
ALGORITMA KOMPRESI
1. Algoritma hufftman
Algoritma Huffman, yang dibuat oleh seorang mahasiswa MIT bernama David
Huffman, 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 dikodekan dengan rangkaian bit yang pendek dan karakter yang jarang muncul dikodekan dengan rangkaian bit yang lebih panjang.
Algoritma Huffman secara lengkap diberikan pada Gambar 1.
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.
Tiap karakter menjadi node daun pada pohon Huffman.
2. Pass kedua
Ulangi sebanyak (n -1) kali :
a. Item m1 dan m2 Å dua subset dalam T dengan nilai peluang yang terkecil.
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 node m1 dan m2 dalam pohon
Huffman.
3. T sekarang tinggal berisi satu itemdan 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.
Sebagai contoh, dalam kode ASCII string 7 huruf “ABACCDA” membutuhkan
representasi 7 × 8 bit = 56 bit (7 byte), dengan rincian sebagai berikut:
01000001 01000010 01000001 01000011 01000011 01000100 01000001
A B A C C D A
Untuk mengurangi jumlah bit yang dibutuhkan, panjang kode untuk tiap karakter dapat
dipersingkat, terutama untuk karakter yang frekuensi kemunculannya besar. Pada string
di atas, frekuensi kemunculan A = 3, B = 1, C = 2, dan D = 1, sehingga dengan
menggunakan algoritma di atas diperoleh kode Huffman seperti pada Tabel 1.
Tabel 1. Kode Huffman untuk “ABACCDA”
Simbol
|
Frekuensi
|
Peluang
|
Kode hufftman
|
A
|
3
|
3/7
|
0
|
B
|
1
|
1/7
|
110
|
C
|
2
|
2/7
|
10
|
D
|
1
|
1/7
|
111
|
Dengan menggunakan kode Huffman ini, string “ABACCDA” 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 tiap kode Huffman yang dihasilkan unik, maka proses dekompresi 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”. Metode Huffman yang diterapkan dalam penelitian ini adalah tipe statik, dimana dilakukan dua kali pembacaan (two-pass)
terhadap file yang akan dikompresi; pertama untuk menghitung frekuensi kemunculan karakter dalam pembentukan pohon Huffman, dan kedua untuk mengkodekan simbol dalam kode
Huffman.
2. Algoritma LZW
Algoritma LZW dikembangkan dari metode kompresi yang dibuat oleh Ziv dan Lempel pada tahun 1977. Algoritma ini melakukan kompresi dengan menggunakan dictionary, di mana fragmen-fragmen teks digantikan dengan indeks yang diperoleh dari sebuah “kamus”. Prinsip sejenis juga digunakan dalam kode Braille, di mana kode-kode khusus digunakan untuk merepresentasikan kata-kata yang ada. Pendekatan ini bersifat adaptif dan efektif karena banyak karakter dapat dikodekan dengan mengacu pada stringyang telah muncul sebelumnya dalam teks. Prinsip kompresi tercapai jika referensi dalam bentuk pointer dapat disimpan dalam jumlah bit yang lebih sedikit dibandingkan string aslinya. Algoritma kompresi LZW diberikan pada
1. Dictionary diinisialisasi dengan semua karakter dasar yang ada :
{‘A’..’Z’,’a’..’z’,’0’..’9’}.
2. P Å karakter pertama dalam stream karakter.
3. C Å karakter berikutnya dalam stream karakter.
4. Apakah string (P + C) terdapat dalam dictionary ?
• Jika ya, maka P Å P + C (gabungkan P dan C menjadi string baru).
• Jika tidak, maka :
i. Output sebuah kode untuk menggantikan string P.
ii. Tambahkan string (P + C) ke dalam dictionary dan berikan nomor/kode
berikutnya yang belum digunakan dalam dictionary untuk string tersebut.
iii. P Å C.
5. Apakah masih ada karakter berikutnya dalam stream karakter ?
• Jika ya, maka kembali ke langkah 2.
• Jika tidak, maka output kode yang menggantikan string P, lalu terminasi proses
(stop).
Sebagai contoh, string “ABBABABAC” akan dikompresi dengan LZW. Isi dictionary pada
awal proses diset dengan tiga karakter dasar yang ada: “A”, “B”, dan “C”. Tahapan proses
kompresi ditunjukkan pada Tabel 3. Kolom posisi menyatakan posisi sekarang dari stream
karakter dan kolom karakter menyatakan karakter yang terdapat pada posisi tersebut.
Kolom dictionary menyatakan string baru yang sudah ditambahkan ke dalam dictionary
dan nomor indeks untuk string tersebut ditulis dalam kurung siku. Kolom output menyatakan
kode output yang dihasilkan oleh langkah kompresi. Hasil proses kompresi ditunjukkan
pada Gambar 3
Tabel 3. Tahapan proses kompresi LZW
LANGKAH
|
POSISI
|
KARAKTER
|
DICTIONARY
|
OUTPUT
|
1
|
1
|
A
|
[4]AB
|
[1]
|
2
|
2
|
B
|
[5]BB
|
[2]
|
3
|
3
|
B
|
[6]BA
|
[2]
|
4
|
4
|
A
|
[7]ABA
|
[4]
|
5
|
6
|
A
|
[8]ABAC
|
[7]
|
6
|
9
|
C
|
---
|
[3]
|
stream karakter : a b b ab aba c
↓ ↓ ↓ ↓ ↓ ↓
kode output : [1] [2] [2] [4] [7] [3]
frasa baru yang 4 5 6 7 8
ditambahkan ke = = = = =
dictionary ab bb ba aba abac
Proses dekompresi pada LZW dilakukan dengan prinsip yang sama seperti proses
kompresi. Algoritma diberikan pada Gambar 4. Pada awalnya, dictionary diinisialisasi
dengan semua karakter dasar yang ada. Lalu pada setiap langkah, kode dibaca satu per satu
dari stream kode, dikeluarkan string dari dictionary yang berkorespondensi dengan kode tersebut, dan ditambahkan string baru kedalam dictionary. Tahapan proses dekompresi
ini ditunjukkan pada Tabel 4.
Metode LZW yang diterapkan dalam penelitian ini bertipe dinamik, dimana hanya
dilakukan satu kali pembacaan (one-pass) terhadap file yang akan dikompresi.
Pengkodean data dilakukan secara on the fly, bersamaan dengan proses penambahan string
baru ke dalam dictionary
1. Dictionary diinisialisasi dengan semua karakter dasar yang ada : {‘A’..’Z’,’a’..’z’,’0’..’9’}.
2. CW Å kode pertama dari stream kode (menunjuk ke salah satu karakter dasar).
3. Lihat dictionary dan output string dari kode tersebut (string.CW) ke stream karakter.
4. PW Å CW; CW Å kode berikutnya dari stream kode.
5. Apakah string.CW terdapat dalam dictionary ?
‰ Jika ada, maka :
i. output string.CW ke stream karakter
ii. P Å string.PW
iii. C Å karakter pertama dari string.CW
iv. tambahkan string (P+C) ke dalam dictionary
‰ Jika tidak, maka :
i. P Å string.PW
ii. C Å karakter pertama dari string.PW
iii. output string (P+C) ke stream karakter dan tambahkan string tersebut ke dalam
dictionary (sekarang berkorespondensi dengan CW);
6. Apakah terdapat kode lagi di stream kode ? Jika ya, maka kembali ke langkah 4. Jika tidak, maka terminasi proses (stop)
Tabel 4. Tahapan proses dekompresi LZW
Gambar 4. Algoritma dekompresi LZW
LANGKAH
|
KODE
|
OUTPUT
|
DICTIONARY
|
1
|
[1]
|
A
|
---
|
2
|
[2]
|
B
|
[4]AB
|
3
|
[2]
|
B
|
[5]BB
|
4
|
[4]
|
AB
|
[6]BA
|
5
|
[7]
|
ABA
|
[7]ABA
|
6
|
[3]
|
C
|
[8]ABAC
|
3. Algoritma DMC
Algoritma DMC merupakan teknik pemodelan yang didasarkan pada model finite-state
(model Markov). DMC membuat probabilitas dari karakter biner berikutnya dengan
menggunakan pemodelan finite-state, dengan model awal berupa mesin FSA dengan transisi
0/1 dan 1/1, seperti ditunjukkan pada Gambar 5. DMC merupakan teknik kompresi yang
adaptif, karena struktur mesin finite-state berubah seiring dengan pemrosesan file.
Kemampuan kompresinya tergolong amat baik, meskipun waktu komputasi yang
dibutuhkan lebih besar dibandingkan metode lain [2].
Pada DMC, simbol alfabet input diproses per bit, bukan per byte. Setiap output transisi
menandakan berapa banyak simbol tersebut muncul. Penghitungan tersebut dipakai untuk
memperkirakan probabilitas dari transisi. Contoh: pada Gambar 6, transisi yang keluar
dari state 1 diberi label 0/5, artinya bit 0 di state 1 terjadi sebanyak 5 kali.
Secara umum, transisi ditandai dengan 0/p atau 1/q dimana p dan q menunjukkan jumlah
transisi dari state dengan input 0 atau 1. Nilai probabilitas bahwa input selanjutnya bernilai 0
adalah p/(p+q) dan input selanjutnya bernilai 1 adalah q/(p+q). Lalu bila bit sesudahnya
ternyata bernilai 0, jumlah bit 0 di transisi sekarang ditambah satu menjadi p+1. Begitu
pula bila bit sesudahnya ternyata bernilai 1, jumlah bit 1 di transisi sekarang ditambah satu
menjadi q+1. Algoritma kompresi DMC diberikan pada Gambar 7. Masalah tidak terdapatnya kemunculan suatu bit pada state dapat diatasi dengan menginisialisasi model awal state dengan satu. Probabilitas dihitung menggunakan frekuensi relatif dari dua transisi yang keluar dari state
yang baru.
1. s Å 1 /* jumlah state sekarang */
2. t Å 1 /* state sekarang */
3. T[1][0] = T[1][1] Å 1 /* model inisialisasi */
4. C[1][0] = C[1][1] Å 1 /* inisialisasi untuk menghindari masalah frekuensi nol */
5. Untuk setiap input bit e :
i. u Å t
ii. t Å T[u][e] /*ikuti transisi*/
iii. Kodekan e dengan probabilitas : C[u][e] / (C[u][0] + C[u][1])
iv. C[u][e] Å C[u][e]+1
v. Jika ambang batas cloning tercapai, maka :
‰ s Å s + 1 /* state baru t’ */
‰ T[u][e] Å s ; T[s][0] Å T[t][0] ; T[s][1] Å T[t][1]
‰ Pindahkan beberapa dari C[t] ke C[s]
Jika frekuensi transisi dari suatu state t ke state sebelumnya, yaitu state u, sangat tinggi, maka
state t dapat di-cloning. Ambang batas nilai cloning harus disetujui oleh encoder dan
decoder. State yang di-cloning diberi simbol t’ (lihat Gambar 8). Aturan cloning adalah
sebagai berikut :
Ø ‰ Semua transisi dari state u dikirim ke state t’. Semua transisi dari state lain ke state t tidak berubah.
Ø Jumlah transisi yang keluar dari t’ harus mempunyai rasio yang sama (antara 0 dan 1) dengan jumlah transisi yang keluar dari t.
Ø Jumlah transisi yang keluar dari t dan t’ diatur supaya mempunyai nilai yang sama dengan jumlah transisi yang masuk [2].
Metode DMC yang diterapkan dalam penelitian ini bertipe dinamik, dimana hanya
dilakukan satu kali pembacaan terhadap file input. Kalkulasi dilakukan secara on the fly
(proses perhitungan probabilitas dilakukan bersamaan dengan pengkodean data).
PERBANDINGAN ANTAR ALGORTIMA KOMPRESI
1. 1. Secara rata-rata algoritma DMC menghasilkan rasio file hasil kompresi yang terbaik (41.5% ± 25.9), diikuti algoritma LZW (60.2% ± 28.9) dan terakhir algoritma Huffman (71.4% ± 15.4).
2. 2. Untuk kategori file teks, source code, file aplikasi, dan file basis data, DMC memberikan hasil kompresi yang baik sekali. Sedangkan untuk file multimedia, hasil kompresinya buruk (dapat > 100 %), karena pada umumnya file multimedia merupakan file hasil kompresi juga, dan hasil kompresi DMC terhadap file yang telah terkompresi sebelumnya memang kurang baik.
3. 3. 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, sedangkan LZW memberikan hasil kompresi yang buruk (dapat > 100%) untuk file multimedia dan file hasil kompresi
4. 4. Secara rata-rata algoritma LZW membutuhkan waktu kompresi yang tersingkat (kecepatan kompresinya = 1139 KByte/sec ± 192,5), diikuti oleh algoritma Huffman (555,8 KByte/sec ± 55,8), dan terakhir DMC (218,1 KByte/sec ± 69,4). DMC mengorbankan kecepatan kompresi untuk mendapatkan rasio hasil kompresi yang baik. File yang berukuran sangat besar membutuhkan waktu yang sangat lama bila dikompresi dengan DMC (contoh: file multimedia dengan ukuran 59MB membutuhkan waktu kompresi 12,3 menit).
5. 5. Kecepatan kompresi algoritma LZW secara signifikan berkurang pada file UNIX, file executable, file gambar, file multimedia, dan file hasil kompresi. Kecepatan kompresi algoritma DMC berkurang pada file gambar dan file hasil kompresi, bahkan untuk file multimedia kecepatan kompresi berkurang lebih dari sepertiga kalinya dibandingkan kecepatan kompresi rata-rata. Kecepatan kompresi algoritma Huffman hampir merata untuk semua kategori file.
