Algoritma Kompresi

Pengantar Teknik Kompresi Data

Teknik Kompresi Data adalah Suatu teknik pemampatan data sehingga diperoleh file dengan ukuran yang lebih kecil daripada ukuran aslinya dengan cara mengkompres data tersebut melalui proses mengkodekan informasi menggunakan bit atau information-bearing unit yang lain yang lebih rendah daripada representasi data yang tidak terkodekan dengan suatu sistem encoding tertentu. Contoh sederhananya adalah menyingkat kata-kata yang sering digunakan tapi sudah memiliki konvensi umum. Misalnya: kata “yang” dikompres menjadi kata “yg”.

Tujuan dari proses pengubahan sekumpulan data menjadi bentuk kode (Kompresi data) ini adalah untuk menghemat kebutuhan tempat penyimpanan dan waktu untuk transmisi data (memperkecil kebutuhan bandwidth).

Teknik kompresi ini bisa dilakukan terhadap data teks/biner, gambar (JPEG, PNG, TIFF), audio (MP3, AAC, RMA, WMA), dan video (MPEG, H261, H263).

Secara umum, kompresi data dapat di klasifikasikan ke dalam 2 macam, yaitu :

1.          Kompresi Lossy

Teknik kompresi dimana data yang sudah dikompresi tidak dapat dikembalikan seperti data semula, dimana lossy atau distortive atau noise-incurring. Kompresi deperti ini digunakan untuk gambar dan suara dimana kehilangan (loss) data dapat diijinkan dalam kasus tertentu.

2.          Kompresi Lossless

Kompresi lossless/tanpa distorsi/tanpa noise adalah teknik kompresi untuk data seperti file progaram, file dokumen dan record basis data dimana sama sekali tidak diijinkan perbedaan antara awal (sebelum kompresi) dan data setelah dilakukan kompresi. Dengan menggunakan algoritma GZIP, proses pengompresan dilakukan dengan menggunakan prinsip pengkodean, yaitu tiap karakter dikodekan dengan rangkaian beberapa bit lalu disimpan pada sebuah dictionary.

  Macam-macam Algoritma Kompresi

1.                        LZW Algorithm

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. karakter dasar pada KAMUS: {‘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

5. Jika ya, maka W ß W + K (gabungkan W dan K menjadi string baru).

6. 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.

7. Lakukan pengecekan apakah masih ada karakter berikutnya dalam stream karakter

8. Jika ya, maka kembali ke langkah 2.

9. Jika tidak, maka output kode yang menggantikan string W, lalu terminasi proses (stop).

Flowchart Algoritma LZW

Sebagai contoh, string “ABBABABAC” akan dikompresi dengan LZW. Isi dictionary pada

diset dengan tiga karakter dasar yang ada: “A”, “B”, dan “C”. Tahapan proses kompresi ditunjukkan pada Tabel 2

Tabel 2 Tahapan Kompresi LZW

Langkah	Posisi	Karakter	Dictionary	Output
1	1	A	A B	1
2	2	B	B B	2
3	3	B	B A	2
4	4	A	A B A	4
5	6	A	A B A C	7
6	9	C	-	3

Kolom posisi menyatakan posisi sekarang dari karakter dan kolom karakter menyatakan karakter yang terdapat pada posisi tersebut. Kolom menyatakan string baru yang sudah ditambahkan ke dalam dictionary dan nomor indeks untuk string tersebut ditulis apakah , . awal proses Kompresi

Hasil Kompresi

Proses dekompresi data pada algoritma LZW tidak jauh berbeda dengan proses kompresinya. Pada dekompresi LZW, juga dibuat tabel dictionary dari data input kompresi, sehingga tidak diperlukan penyertaan table dictionary ke dalam data kompresi. dekompresi LZW :

1. Dictionary diinisialisasi dengan semua karakter dasar yang ada : {‘A’..’Z’,’a’..’z’,’0’..’9’}.

2. CW kode pertama dari stream salah satu karakter dasar).

3. Lihat dictionary dan output string (string.CW) ke stream karakter.

4. PW CW; CW kode berikutnya dari stream code

5. Apakah string.CW terdapat dalam dictionary

6. Jika ada, maka : Output string CW ke stream karakter.

P ß string PW

C ß karakter pertama dari string CW

Tambahkan string (P+C) ke dalam dictionary

7. Jika tidak, maka : P ß string.PW

C ß karakter pertama dari

Output string (P+C) ke stream tambahkan string tersebut ke dalam (sekarang berkorespondensi dengan CW)

8. Apakah terdapat kode lagi di stream

9. Jika ya, maka kembali ke langkah 4.

10. Jika tidak, maka terminasi proses (stop)

 2.                         Algoritma DMC

Algoritma DMC (Dynamic Markov adalah algoritma kompresi data lossless dikembangkan oleh Gordon Cormack dan Nigel Horspool. Algoritma ini menggunakan pengkodean aritme 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.

model yang diciptakan oleh metode DMC

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 :

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 :

f. s ß s + 1 (state baru t’)

g. T[u][e] ß s ; T[s][0] ß T[t][0] ; T[s][1] ßT[t][1]

h. 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, 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 :

1.                        Semua transisi dari state u dikirim ke state t’. Semua transisi dari state lain ke state t tidak berubah.

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

3.                        Huffman Algorithm

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 orangtuadari s imbol 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:

01000001 01000010 01000001 01000011 01000011 01000100 01000001

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.

Pohon Huffman untuk “ABACCDA”

Tabel 1 Kode Huffman

Karakter	Frekwensi	Peluang	Kode Huffman
A	3	3/7	0
B	1	1/7	110
C	2	2/7	10
D	1	1/7	111

Karakter Frekuensi Peluang Kode Huffman

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 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.

Perbandingan Ketiganya

Jika kinerja algoritma Huffman dibandingkan dengan Algoritma LZW dan DMC, maka akan diperoleh hasil

seperti dibawah ini:

Box Plot Rasio Kompresi Algoritma Huffman, LZW dan DMC

Box Plot Kecepatan Kompresi Algoritma Huffman, LZW dan DMC

Grafik Perbandingan Rasio Kompresi Algoritma Huffman, LZW dan DMC

Grafik Perbandingan Kecepatan Kompresi Algoritma Huffman, LZW dan DMC

Dari grafik di atas, dapat kita lihat bahwa secara ratarata 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.

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.

Referensi

http://webmail.informatika.org/~rinaldi/Matdis/2009-2010/Makalah0910/MakalahStrukdis0910-108.pdf

http://jojoinformation.wordpress.com/2010/05/05/kompresi-data-dengan-algoritma-lzw/

http://home.unpar.ac.id/~integral/Volume%209/Integral%209%20No.%201/Perbandingan%20Kinerja%20Algoritma%20Kompresi.pdf

http://erizal.files.wordpress.com

Napitupulu ,Charles Januari;Universitas Komputer Indonesia