Teknik Kompresi adalah teknik memadatkan data, sehingga data yang tadinya mempunyai kapasitas data yang besar menjadi kapasitas data yang lebih kecil. Dan sekumpulan
data
menjadi suatu bentuk kode untukmenghematkebutuhantempat penyimpanan dan
waktu untuk transmisi
data
Kompresi data adalah proses mengkodekan informasi
menggunakan bit atau information-bearing unit lain yang lebih rendah daripada representasi data
yang tidak terkodekan dengan suatu sistem enkoding tertentu.
Kompresi data menjadi sangat penting karena memperkecil kebutuhan penyimpanan data, mempercepat pengiriman data, memperkecil kebutuhan bandwidth.
Teknik kompresi bisa dilakukan terhadap data teks/biner,
gambar (JPEG, PNG,
TIFF), audio (MP3, AAC,
RMA,
WMA), dan video (MPEG, H261, H263)
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,dan 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 diperlukan
satu
kali pembacaan
terhadap isi
file. Contoh: algoritma LZW dan DMC.
Berdasarkan teknik pengkodean/pengubahan simboln
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 lebih sering muncul diberi kode lebih pendek dibandingkan simbol yang lebih 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
untukmemprediksi distribusi probabilitas dari simbol-simbol
selanjutnya; contoh: algoritma DMC.
Macam-macam
algoritma kompresi :
·
Algoritma Huffman
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,
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 item,
dan 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.
Gambar 1. Algoritma kompresi Huffman
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 Huffman
|
A
|
3
|
3/7
|
0
|
B
|
1
|
1/7
|
110
|
C
|
2
|
2/7
|
10
|
D
|
1
|
1/7
|
111
|
dimana
karakter yang sering muncul dikodekan
dengan rangkaian bit yang pendek dan karakter yang jarang
muncul dikodekan dengan rangkaian bit yang lebih panjang.
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.
·
Algoritma LZW
Algoritma
LZW dikembangkan dari metode kompresi yang dibuat oleh Ziv dan
Lempel pada tahun 1977. Algoritma
ini melakukan kompresi dengan menggunakan dictionary, dimana 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 string
yang 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 Gambar 2.
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).
Gambar 2. Algoritma kompresi LZW
Sebagai contoh, string “ABBABABAC”
akan dikompresi dengan LZW. Isi dictionary pada awal proses
diset dengan tiga karakter dasar
yang
ada: “A”, “B”, dan “C”.
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 ke dalam 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).
Gambar 4. Algoritma dekompresi LZW Tabel 4.
Tahapan proses dekompresi LZW
Langkah
|
Kode
|
Output
|
Dictionary
|
1.
|
[1]
|
A
|
- - -
|
2.
|
[2]
|
B
|
[4] A B
|
3.
|
[2]
|
B
|
[5] B B
|
4.
|
[4]
|
A B
|
[6] B A
|
5.
|
[7]
|
A B A
|
[7] A B A
|
6.
|
[3]
|
C
|
[8] A B A C
|
- Algoritma DMC (Dynamic Markov Compression) Algoritma DMC (Dynamic Markov Compression) adalah algoritma kompresi data lossless yang dikembangkan oleh Gordon Cormack dan Nigel Horspool. Algoritma ini menggunakan pengkodean aritmatika mirip dengan prediksi pencocokan sebagian (PPM), kecuali bahwa input diperkirakan satu bit pada satu waktu (bukan dari satu byte pada satu waktu). DMC memiliki rasio kompresi yang baik dan kecepatan moderat, mirip dengan PPM, tapi memerlukan sedikit lebih banyak memori dan juga tidak diterapkan secara luas. Beberapa implementasinya 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 pelaksanaannya pada tahun 1993 di C oleh Gordon Cormack. Pada DMC, input simbol alfabet diproses per bit, bukan per byte. Setiap output transisi menandakan berapa banyak simbol tersebut muncul. Penghitungan tersebut dipakai untuk memperkirakan probabilitas dari transisi.
Secara umum, transisi ditandai dengan 0/p atau 1/q dimana p dan q menunjukkan jumlah transisi dari state dengan input 0 atau 1. Bahwa nilai probabilitas 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 ditransisi dan ditambah satu menjadi p+1. Begitu pula bila bit sesudahnya ternyata bernilai 1, jumlah bit 1 sekarang ditransisi dan 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 : a. u <- t
b. t <- T[u][e] (ikuti transisi) c. Kodekan e dengan probabilitas : C[u][e]
/ (C[u][0] + C[u][1]) d. C[u][e] <- C[u][e]+1 e. 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 menggunakan frekuensi relatif dari dua transisi yang keluar dari state yang baru.
Jika frekuensi transisi dari suatu state t ke state sebelumnya (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’.
Aturan cloning adalah sebagai berikut :
1. Semua transisi dari state u dikirim ke state t’. Semua transisi dari state lain ke state t tidak dirubah.
2. Jumlah transisi yang keluar dari t’ harus mempunyai rasio yang sama (antara 0 dan 1) dengan jumlah transisi yang keluar dari t.
3. Jumlah transisi yang keluar dari t dan t’ diatur supaya mempunyai nilai yang sama dengan jumlah transisi yang masuk.
Model Markov sebelum cloning
Model Markov setelah cloning
Kesimpulan :
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.
Hasi lkompresi 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.
Referensi :
http://home.unpar.ac.id/~integral/Volume%209/Integral%209%20No.%201/Perbandingan%20Kinerja%20Algoritma%20Kompresi.pdf