Algoritma Kompresi

Teknik Kompresi adalah teknik memadatkan data, sehingga data yang tadinyamempunyai kapasitas data yang besar menjadi kapasitas data yang lebih kecil. Dan   sekumpulan  data  menjadi  suatu  bentuk kode untukmenghematkebutuhantempatpenyimpanan dan waktu untuk transmisi   data

Kompresi data adalah proses mengkodekan informasi menggunakan bit atauinformation-bearing unit lain yang lebih rendah daripada representasi data yangtidak terkodekan dengan suatu sistem enkoding tertentu. Kompresi data menjadisangat penting karena memperkecil kebutuhan penyimpanan data, mempercepatpengiriman 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 bersifatone- pass,  karena  hanya  diperlukan  satu kali   pembacaan   terhadap   isi   file. Contoh: algoritma LZW dan DMC.

Berdasarkan teknik pengkodean/pengubahan simboln yang digunakan, metode kompresidapat dibagi ke dalam tiga kategori, yaitu :

(a) Metode   symbolwise   :   menghitung peluang kemunculan dari tiap simbol dalam fileinput, lalu mengkodekan satu     simbol   dalam   satu   waktu, dimana   simbol  yang lebih   sering muncul diberi kode lebih pendek dibandingkan simbol  yang    lebih jarangmuncul, 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-stateuntukmemprediksi 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 frekuensikemunculan 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 rinciansebagai 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 karakteryang jarang muncul dikodekan dengan rangkaian bit yang lebih panjang. Dengan menggunakan kodeHuffman 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 danLempel pada tahun 1977. Algoritma ini melakukan kompresi dengan menggunakandictionary, dimana fragmen-fragmen teks digantikan dengan indeks yang    diperoleh dari          sebuah “kamus”. Prinsip sejenis juga digunakan dalam kode Braille, di manakode-kode khusus digunakan untuk merepresentasikan kata-kata yang ada.

Pendekatan  ini    bersifat adaptif   dan efektif karena banyak karakter dapat dikodekandengan 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 berikannomor/kode berikutnya yang belum digunakan dalam dictionary untukstring 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 datadilakukan secara on the fly, bersamaan dengan proses penambahan string baru ke dalamdictionary.

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 streamkarakter 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 dekompresiLZW Tabel 4. Tahapan prosesdekompresi 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.

Contoh: 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. 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, hasilkompresinya buruk (dapat > 100 %), karena  pada  umumnya  file  multimedia merupakanfile  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, filemultimedia, 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 hasilkompresi.

4.      Secara rata-rata algoritma LZW membutuhkan waktu kompresi yang tersingkat (kecepatankompresinya = 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 kecepatankompresi 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, fileexecutable, 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.