Teknik Kompresi Data

TEKNIK KOMPRESI DATA

Dalam ilmu komputer, pemampatan data atau Kompresi Data merupakan salah satu subyek di bidang teknologi informasi yang saat ini telah diterapkan secara luas. Kompresi Data adalah sebuah cara untuk memadatkan data sehingga hanya memerlukan ruangan penyimpanan lebih kecil sehingga lebih efisien dalam menyimpannya atau mempersingkat waktu pertukaran data tersebut. Teori Informasi sendiri adalah salah satu cabang Matematika yang berkembang sekitar akhir dekade 1940-an. Tokoh utama dari Teori Informasi adalah Claude Shannon dari Bell Laboratory. Teori Informasi mengfokuskan pada berbagai metode tentang informasi termasuk penyimpanan dan pemrosesan pesan. Teori Informasi mempelajari pula tentang redundancy (informasi tak berguna) pada pesan. 

Semakin banyak redundancy semakin besar pula ukurang pesan, upaya mengurangi redundancy inilah yang akhirnya melahirkan subyek ilmu tentang Kompresi Data. Teori Informasi menggunakan terminologi entropy sebagai pengukur berapa banyak informasi yang dapat diambil dari sebuah pesan. Kata “entropy” berasal dari ilmu termodinamika. Semakin tinggi entropy dari sebuah pesan semakin banyak informasi yang terdapat di dalamnya. Entropy dari sebuah simbol didefinisikan sebagai nilai logaritma negatif dari probabilitas kemunculannya.

Ada terdapat jenis Teknik Kompresi dapat dibagi menjadi dua kategori besar, yaitu pemampatan tanpa kehilangan (lossless data compression) dan pemampatan berkehilangan (lossy data compression).

1. Lossy Compression

    Lossy compression menyebabkan adanya perubahan data dibandingkan sebelum dilakukan proses kompresi. Sebagai gantinya lossy compression memberikan derajat kompresi lebih tinggi. Tipe ini cocok untuk kompresi file suara digital dan gambar digital. File suara dan gambar secara alamiah masih bisa digunakan walaupun tidak berada pada kondisi yang sama sebelum dilakukan kompresi.

2. Lossless Compression

    Sebaliknya Lossless Compression memiliki derajat kompresi yang lebih rendah tetapi dengan akurasi data yang terjaga antara sebelum dan sesudah proses kompresi. Kompresi ini cocok untuk basis data, dokumen atau spreadsheet. Pada lossless compression ini tidak diijinkan ada bit yang hilang dari data pada proses kompresi.

Secara umum kompresi data terdiri dari dua kegiatan besar, yaitu Modeling dan Coding. Proses dasar dari kompresi data adalah menentukan serangkaian bagian dari data (stream of symbols) mengubahnya menjadi kode (stream of codes). Jika proses kompresi efektif maka hasil dari stream of codes akan lebih kecil dari segi ukuran daripada stream of symbols. Keputusan untuk mengindentikan symbols tertentu dengan codes tertentu adalah inti dari proses modeling. Secara umum dapat diartikan bahwa sebuah model adalah kumpulan data dan aturan yang menentukan pasangan antara symbol sebagai input dan code sebagai output dari proses kompresi. Sedangkan coding adalah proses untuk menerapkan modeling tersebut menjadi sebuah proses kompresi data.

Algoritma Kompresi 

     ada berbagai tipe algoritma kompresi ,antara lain: Huffman, LIFO, LZHUF,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.

disini saya akan membahas beberapa algoritma saja, yaitu :

* 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 diberikan pada Gambar 1.

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:

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”

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

* 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 diberikan pada Gambar 1.

Gambar 1. 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”. Tahapan proses kompresi ditunjukkan pada Tabel 3. 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. Hasil proses kompresi ditunjukkan pada Gambar 2.

Tabel 1. Tahapan proses kompresi LZW

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.

Gambar 3. Algoritma dekompresi LZW

Tabel 2. Tahapan proses dekompresi LZW

* Algoritma Shannon-Fano

Teknik coding ini dikembangkan oleh dua orang dalam dua buah proses yang berbeda, yaitu Claude Shannon di Bell Laboratory dan R.M. Fano di MIT, namun karena memiliki kemiripan maka akhirnya teknik ini dinamai dengan mengggabungkan nama keduanya. Pada dasarnya proses coding dengan algoritma ini membutuhkan data akan frekuensi jumlah kemunculan suatu karakter pada sebuah pesan. Tiga prinsip utama yang mendasari algoritma ini adalah:

a. Simbol yang berbeda memiliki kode yang berbeda

b. Kode untuk symbol yang sering muncul memiliki jumlah bit yang lebih sedikit dan sebaliknya symbol yang

    jarang muncul memiliki kode dengan jumlah bit lebih besar.

c. Walaupun berbeda jumlah bit-nya tetapi kode harus tetap dikodekan secara pasti (tidak ambigu).

Berikut adalah langka-langkah Algoritma Shannon-Fano

1. Buatlah tabel yang memuat frekuensi kemunculan dari tiap karakter.

2. Urutkan berdasar frekuensi tersebut dengan karakter yang frekuensinya paling sering muncul berada

    diatas dari daftar (descending).

3. Bagilah 2 tabel tersebut dengan jumlah total frekuensi pada bagian atas mendekati jumlah total frekuensi

    pada bagian bawah (lihat tabel 3).

4. Untuk bagian paro atas berikan kode 0 dan pada paro bawah berikan kode

5. Ulangi langkah 3 dan 4 pada masing-masing paro tadi hingga seluruh symbol selesai dikodekan.

Tabel 1 Langkah Pertama Algoritma Shannon Fano

Tabel 2 Langkah Awal Algoritma Shannon Fano

Dari proses pengkodean tersebut kita mendapatkan serangkaian kode untuk merepresentasikan kelima simbol A, B, C, D, E sebagai berikut:

A = 00 ; B = 01; C = 10 ; D = 110 ; dan E = 111.

Kesimpulan dari Hasil Kompresi dari Algotrima tersebut sebagai berikut :

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. Untuk file teks yang memiliki jumlah jenis karakter yang lebih banyak dengan tingkat pengulangan karakter yang lebih kecil, algoritma Shannon Fano memiliki rasio kompresi yang lebih tinggi. Algoritma Shannon fano juga membutuhkan waktu kompresi dan dekompresi yang lebih sedikit.

Referensi :

www.Google.com

www.Ilmukomputer.com

www.Scribd.com