Pengertian Kompresi Data
Kompresi ialah
proses pengubahan sekumpulan data menjadi suatu bentuk kode untuk menghemat
kebutuhan tempat penyimpanan dan waktu transmisi data.
Pengertian teknik
kompresi adalah teknik memadatkan data atau file, sehingga data atau file
yang tadinya memiliki kapasitas data
yang besar menjadi kapasitas data yang lebih kecil. Pengertian teknik
kompresi tersebut memungkinkan kita menyimpan data atau file yang banyak atau
besar pada memory yang memiliki kapasitas kecil.
Kompresi data
adalah proses yang dapat mengubah sebuah aliran data masukan (sumber atau data
asli) ke dalam aliran data yang lain (keluaran atau data yang dimampatkan) yang
memiliki ukuran yang lebih kecil. Kompresi data adalah sebuah penyajian
informasi ke dalam bentuk yang lebih sederhana. Dalam ilmu komputer dan teori
informasi, kompresi data atau source coding adalah proses meng-encode informasi
dengan menggunakan lebih sedikit bit dari suatu sumber yang belum di-encode
melalui penggunaan skema pengkodean yang spesifik.
Saat ini terdapat berbagai tipe algoritma kompresi , antara
lain: Huffman, LIFO, ZHUF, 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. Berdasarkan tipe peta kode yang
digunakan untuk mengubah pesan awal menjadi sekumpulan codeword, metode
kompresi terbagi menjadi dua kelompok, yaitu:
·
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, dan fase kedua untuk mengubah pesan menjadi kumpulan kode yang
akan ditransmisikan.
contoh: algoritma Huffman statik.
·
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
onepass, karena hanya diperlukan satu kali pembacaan terhadap isi file.
contoh: Contoh: algoritma LZW dan DMC.
Tujuan dari kompresi data adalah untuk merepresentasikan
suatu data digital dengan sesedikit mungkin bit, tetapi tetap mempertahankan
kebutuhan minimum untuk membentuk kembali data aslinya. Data digital ini dapat
berupa text, gambar, suara, dan kombinasi dari ketiganya, seperti video.
Jenis-jenis Kompresi Data:
kompresi data berdasarkan mode penerimaan data yang di terima manusia:
·
Dialoque Mode: yaitu proses penerimaan data
dimana pengirim dan penerima seakan berdialog (real time), seperti pada contoh
video conference.
·
Retrieval Mode: yaitu proses penerimaan data
tidak dilakukan secara real time.
kompresi data berdasarkan output:
·
Lossy Compression: Teknik kompresi dimana data
hasil dekompresi tidak sama dengan data sebelum kompresi namun sudah “cukup”
untuk digunakan. Contoh: Mp3, streaming
media, JPEG, MPEG, dan WMA.
·
Loseless: Teknik kompresi dimana data hasil
kompresi dapat didekompres lagi dan hasilnya tepat sama seperti data sebelum
proses kompresi. Contoh aplikasi: ZIP,
RAR, GZIP, 7-Zip.
Klasifikasi Teknik Kompresi
·
Entropy Encoding: Bersifat loseless, Tekniknya
tidak berdasarkan media dengan spesifikasi dan karakteristik tertentu namun
berdasarkan urutan data, Statistical encoding, tidak memperhatikan semantik
data.
·
Source Coding: Bersifat lossy, Berkaitan dengan
data semantik (arti data) dan media.
·
Hybrid Coding: Gabungan antara lossy + loseless.
Tipe-tipe Algoritma Kompresi
1.
Algoritma Huffman
Algoritma Huffman ditemukan oleh David
Huffman pada tahun 1952. Algoritma ini menggunakan pengkodean yang mirip dengan
kode Morse. Berdasarkan tipe kode yang digunakan algoritma Huffman termasuk
metode statistic. Sedangkan berdasarkan teknik pengkodeannya menggunakan metode
symbolwise. Algoritma Huffman merupakan salah satu algoritma yang digunakan
untuk mengompres teks. Algoritma Huffman secara lengkap :
1.
Pilih dua simbol dengan peluang (probability)
paling kecil (pada contoh di atas simbol
B dan D). Kedua simbol tadi
dikombinasikan sebagai simpul orangtua dari simbol B dan
D sehingga menjadi simbol BD
dengan peluang 1/7 + 1/7 = 2/7, yaitu jumlah peluang kedua anaknya.
2.
Selanjutnya, pilih dua simbol berikutnya,
termasuk simbol baru, yang mempunyai peluang terkecil.
3.
Ulangi langkah 1 dan 2 sampai seluruh simbol
habis. Sebagai contoh, dalam kode ASCII
string 7 huruf “ABACCDA”
membutuhkan representasi 7 × 8 bit = 56 bit (7 byte), dengan rincian sebagai
berikut:
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.
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 dari yang seharusnya dibutuhkan 56 bit.
Untuk menguraikan kembali data yang sudah dikodekan sebelumnya dengan algoritma
Huffman, dapat digunakan cara sebagai berikut :
1.
Baca bit pertama dari string biner masukan
2.
Lakukan traversal pada pohon Huffman mulai dari
akar sesuai dengan bit yang dibaca. Jika bit yang dibaca adalah 0 maka baca
anak kiri, tetapi jika bit yang dibaca adalah 1 maka baca anak kanan.
3.
Jika anak dari pohon bukan daun (simpul tanpa
anak) maka baca bit berikutnya dari string biner masukan.
4.
Hal ini diulang (traversal) hingga ditemukan
daun.
5.
Pada daun tersebut simbol ditemukan dan proses
penguraian kode selesai.
6.
Proses penguraian kode ini dilakukan hingga
keseluruhan string biner masukan diproses.
2.
Algoritma LZW (Lempel-Ziv-Welch)
Algoritma LZW dikembangkan oleh Terry
A.Welch dari metode kompresi sebelumnya yang ditemukan oleh Abraham Lempel dan
Jacob Ziv pada tahun 1977. Algortima ini menggunakan teknik dictionary dalam
kompresinya. Dimana string karakter digantikan oleh kode table yang dibuat
setiap ada string yang masuk. Tabel dibuat untuk referensi masukan string
selanjutnya. Ukuran tabel dictionary pada algoritma LZW asli adalah 4096 sampel
atau 12 bit, dimana 256 sampel pertama digunakan untuk table karakter single
(Extended ASCII), dan sisanya digunakan untuk pasangan karakter atau string
dalam data input.
Algoritma
LZW melakukan kompresi
dengan mengunakan kode table 256 hingga 4095 untuk mengkodekan pasangan
byte atau string. Dengan metode ini banyak string yang dapat dikodekan dengan
mengacu pada string yang telah muncul sebelumnya dalam teks.
Algoritma kompresi LZW secara lengkap :
1.
KAMUS diinisialisasi dengan semua karakter dasar yang ada :
{‘A’..’Z’,’a’..’z’,’0’..’9’}.
2. W
= karakter pertama dalam stream karakter.
3. K
= karakter berikutnya dalam stream karakter.
4.
Lakukan pengecekan apakah (W+K) terdapat dalam KAMUS
·
Jika ya, maka W = W + K (gabungkan W dan K
menjadi string baru).
·
Jika tidak, maka Output sebuah kode untuk menggantikan string W.
·
Tambahkan string (W+ K) ke dalam dictionary dan
berikan nomor/kode berikutnya yang belum digunakan dalam dictionary untuk
string tersebut W = K.
·
Lakukan pengecekan apakah masih ada karakter
berikutnya dalam stream karakter.
·
Jika ya, maka kembali ke langkah 2.
·
Jika tidak, maka output kode yang menggantikan
string W, lalu terminasi proses (stop).
Sebagai contoh, string “ABBABABAC” akan dikompresi dengan LZW. Isi
dictionary pada awal proses diset dengan 3 karakter dasar yang ada: “A”, “B”,
dan “C”. Tahapan proses kompresi ditunjukkan pada Tabel 2.
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 kedalam dictionary dan
nomor indeks untukstring tersebut ditulis dalam kurung siku. Kolom output menyatakan kode output yang dihasilkan
oleh langkah kompresi. Hasil proses kompresi ditunjukkan pada Gambar 2.
·
Dictionary diinisialisasi dengan semua karakter
dasar yang ada : {‘A’..’Z’,’a’..’z’,’0’..’9’}.
·
CW = kode pertama dari stream kode (menunjuk ke
salah satu karakter dasar).
·
Lihat dictionary dan output string dari kode
tersebut (string.CW) ke stream karakter.
·
PW = CW; CW = kode berikutnya dari stream kode.
·
Apakah string.CW terdapat dalam dictionary ?
Ø
Jika ada, maka :
Output string.CW ke stream karakter
P = string.PW
C = karakter pertama dari string.CW
Tambahkan string (P+C) ke dalam
Ø
Jika tidak, maka :
P = string.PW
C = karakter pertama dari string.PW
Output string (P+C) ke stream karakter dan tambahkan string tersebut
ke dalam dictionary
(sekarang berkorespondensi dengan CW);
·
Apakah terdapat kode lagi di stream kode ?
Ø
Jika ya, maka kembali ke langkah 4.
Ø
Jika tidak, maka terminasi proses (stop).
3.
Algoritma DMC
Algoritma
DMC (Dynamic Markov Compression) adalah algoritma kompresi data lossless
dikembangkan oleh Gordon Cormack dan Nigel Horspool. Algoritma ini menggunakan
pengkodean aritmetika mirip dengan prediksi oleh pencocokan sebagian (PPM),
kecuali bahwa input diperkirakan satu bit pada satu waktu (bukan dari satu byte
pada suatu waktu). DMC memiliki rasio kompresi yang baik dan kecepatan moderat,
mirip dengan PPM, tapi memerlukan sedikit lebih banyak memori dan tidak
diterapkan secara luas. Beberapa implementasi baru-baru ini mencakup program
kompresi eksperimental pengait oleh Nania Francesco Antonio, ocamyd oleh Frank
Schwellinger, dan sebagai submodel di paq8l oleh Matt Mahoney. Ini didasarkan
pada pelaksanaan tahun 1993 di C oleh Gordon Cormack.
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 3, 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 :
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 :
* u = t
* t = T[u][e] (ikuti transisi)
* Kodekan e dengan probabilitas
: C[u][e] / (C[u][0] + C[u][1])
* C[u][e] = C[u][e]+1
* 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]
Masalah tidak terdapatnya kemunculan suatu bit pada state dapat diatasi dengan menginisialisasi model awal state dengan satu. Probabilitas dihitung menggunakanfrekuensi relatif dari dua transisi yang keluar dari state yang baru. 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 4 dan 5). 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.
Perbandingan Kinerja Algoritma
Huffman dengan Algoritma LZW dan DMC
Jika kinerja algoritma Huffman dibandingkan dengan Algoritma
LZW dan DMC, maka akan diperoleh hasil seperti dibawah ini :
Dari grafik di atas, dapat kita lihat bahwa 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). Dan dari grafik di atas juga, dapat kita lihat bahwa 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.
ada beberapa hal yang
dapat di bandingkan mengenai perbandingan kinerja ketiga metode kompresi yang telah diimplementasikan, yaitu :
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.
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.
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.
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 59 MB membutuhkan waktu kompresi 12,3 menit).
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.
Kesimpulan
1.
Algoritma
Huffman dapat digunakan sebagai dasar untuk kompresi data, dan
pengaplikasiannya cukup mudah serta dapat digunakan dalam berbagai jenis data.
2.
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)
3.
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.
4.
Jika dibandingkan dengan algoritma LZW dan DMC,
dalam kompresi data, algoritma Huffman masih kalah dalam hal rasio kompresi
data maupun kecepatan kompresinya.
Daftar Pustaka
