KOMPRESI DATA
Kompresi ialah proses pengubahan sekumpulan data menjadi suatu bentuk kode untuk menghemat kebutuhan tempat penyimpanan dan waktu untuk transmisi data [1]. Saat ini terdapat berbagai tipe algoritma kompresi [2,3], antaralain: Huffman, LIFO, LZHUF,LZ77 dan variannya (LZ78, LZW, GZIP), Dynamic Markov Compression (DMC), Block-SortingLossless, Run-Length, Shannon-Fano,Arithmetic, PPM (Prediction by PartialMatching), Burrows-Wheeler Block Sorting, dan Half Byte. Berdasarkan tipe peta kode yang digunakan untuk mengubah pesan awal (isi file input) menjadi sekumpulan codeword, metode kompresi terbagi menjadi dua kelompok, yaitu :
• Metode static : menggunakan peta kode yang selalu sama. Metode ini membutuhkan dua fase (two-pass): fasepertama 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 1-kali pembacaan terhadap isi file. Contoh: algoritma LZW dan DMC
Berdasarkan teknik pengkodean/pengubahan simbol 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 untuk memprediksi distribusi probabilitas dari simbol-simbol selanjutnya; contoh: algoritma DMC. Ada beberapa faktor yang sering menjadi pertimbangan dalam memilih suatu metode kompresi yang tepat, yaitu kecepatan kompresi, sumber daya yang dibutuhkan (memori, kecepatan PC), ukuran file hasil kompresi, besarnya redundansi, dan kompleksitas algoritma.
Tidak ada metode kompresi yang paling efektif untuk semua jenis file. Dalam penelitian ini, diimplementasikan tiga buah metode kompresi, yaitu algoritma Huffman, LZW, dan DMC, yang masing-masing mewakili sebuah kategori teknik pengkodean, dalam bentuk sebuah perangkat lunak. Ketiga metode ini diujikan untuk mengkompresi dan mendekompresi berbagai tipe dan ukuran file yang berbeda. Lalu dilakukan analisis statistik untuk membandingkan kinerja setiap metode berdasarkan dua faktor, yaitu rasio/perbandingan ukuran file hasil kompresi terhadap file asli dan kecepatan kompresinya.
ALGORITMA KOMPRESI
Algoritma Kompresi data yang ada saat ini antara lain menggunakan kode/algoritma Huffman dan algoritma-algoritma sejenis yang telah menjelaskan dan membantu kita dalam menangani file-file besar. Termasuk format-format file audio sepert mp3, format gambar seperti jpg dan contoh-contoh sederhana serta penerapannya. Dan teradapat aplikasi-aplikasi yang bermula dari algoritma-algorima tersebut yang sampai sekarang masih dikembangkan softwarenya hingga menjadi lebih baik.
1. 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, 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 :
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)
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 stringdi 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 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 dalamrangkaian 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 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 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 tiga karakter dasar yang ada: “A”, “B”, dan “C”.
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.
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 . 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 4, transisi yang keluar dari state 1 diberi label 0/5, artinya bit 0 di state 1 terjadi sebanyak 5 kali.
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]
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 5 dan 6). 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 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.
KESIMPULAN
1. Penggunaan aplikasi pemampatan data dengan menggunakan algoritma Huffman dan algoritma-algoritma lainnya telah membantu dalam pekerjaan yang melibatkan file-file yang besar dalam bidang informasi dan telekomunikasi. Dari kode-kode dan algoritma tersebut dihasilkanlah software-software pengompres yang selama ini kita kenal
2. Algoritma Huffman dapat digunakan sebagai dasar untuk kompresi data, dan pengaplikasiannya cukup mudah serta dapat digunakan dalam berbagai jenis data.
3. 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)
4. 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.
5. Jika dibandingkan dengan algoritma LZW dan DMC, dalam kompresi data, algoritma Huffman masih kalah dalam hal rasio kompresi data maupun kecepatan kompresinya.
REFERENSI
Linawati. “Perbandingan Kinerja Algoritma Kompresi Huffman, LZW, dan DMC pada Berbagai Tipe File”, 2004.
Postingan
0 komentar:
Posting Komentar