Teknik Algoritma dan Komprensi Data

TEKNIK KOMPRESI DATA

  • Definisi Kompresi Data

Kompresi data merupakan proses pengkodean Informasi  menggunakan bit atau  information-bearing unit yang lain yang lebih rendah dari pada representasi data yang tidak terkodekan dengan suatu system encoding  tertentu.

Ada beberapa pendapat yang mengemukakan mengenai definisi dari Kompresi data,diantaranya :

Menurut  Ida Mengyi Pu (2006:1)  kompresi data adalah ilmu atau seni merepresentasikan informasi dalam  bentuk yang lebih compact.

David Salomon (2007:2) mengatakan bahwa data kompresi adalah proses mengkonversikan sebuah input data  stream (streamsumber, atau data mentah asli) menjadi data  stream lainnya (bitstream hasil,  atau  stream yang telah terkompresi) yang berukuran lebih kecil.

 (Salomon, 2007).Kompresi data adalah proses yang dapat mengubah sebuah aliran data masukan (sumber atau data asli) ke dalam aliran data yang lain (keluaran atau data yang dimampatkan) yang memiliki ukur an yang lebih kecil .

Tujuan dari kompresi data adalah untuk merepresentasikan suatu data digital dengan sesedikit mungkin bit, tetapi tetap mempertahankan kebutuhan minimum untuk membentuk kembali data aslinya. Data digital ini dapat berupa  text, gambar, suara, dan kombinasi dari ketiganya, seperti video.

Contoh kompresi sederhana  yang biasa kita lakukan misalnya adalah menyingkat kata-kata yang sering digunakan tapi sudah memiliki konvensi umum.

Misalnya: kata “yang” dikompres menjadi kata “yg”.Untuk membuat suatu data menjadi lebih kecil ukurannya daripada data asli,  diperlukan tahapan-tahapan (algoritma) untuk mengolah data tersebut. Menurut  Thomas H. Cormen  (2001:2) algoritma adalah suatu prosedur komputasi yang didefinisikan secara baik, membutuhkan sebuah atau sekumpulan nilai sebagai input, dan menghasilkan sebuah atau sekumpulan nilai sebagai  output. Dalam algoritmakompresi data, tidak ada algoritma yang cocok untuk semua jenis data. Hal ini disebabkan karena data yang akan dimampatkan harus dianalisis terlebih dahulu, dan berharap menemukan pola tertentu yang dapat digunakan untuk memperoleh data dalam ukuran yang lebih kecil. Karena itu, muncul banyak algoritma-algoritma kompresi data.Kompresi data sangat populer sekarang ini karena dua alasan yaitu (Salomon, 2007) :

1. Orang – orang lebih suka mengumpulkan data. Tidak peduli seberapa besar media penyimpanan yang dimilikinya. Akan tetapi cepat atau lambat akan terjadi overflow.

2. Orang  –  orang benci menunggu waktu yang lama untuk memindahkan data. Misalnya ketika duduk di depan komputer untuk menunggu halaman Web terbuka atau men-download sebuah file.

 

  • Jenis-Jenis Komprensi Data Berdasarkan Output

Lossy Compression

  • Ddata hasil dekompresi tidak sama dengan data sebelum kompresi namun sudah “cukup” untuk digunakan. Contoh: Mp3, streaming media, JPEG, MPEG, dan WMA.
  • Kelebihan: ukuran file lebih kecil dibanding loseless namun masih tetap memenuhi syarat untuk digunakan.

 

Teknik

 membuang bagian data yang tidak berguna, tidak dirasakan, tidak dilihat oleh manusia sehingga manusia masih beranggapan bahwa data tersebut masih bisa digunakan walaupun sudah dikompresi.

Misal :  image asli berukuran 12,249 bytes,  dilakukan kompresi dengan JPEG kualitas 30 dan berukuran 1,869 bytes : berarti image tersebut 85% lebih kecil dan ratio kompresi 15%.

              Loseless

  • Data hasil kompresi dapat didekompres lagi dan hasilnya tepat sama seperti data sebelum proses kompresi. Contoh aplikasi: ZIP, RAR, GZIP, 7-Zip
  • Teknik ini digunakan jika dibutuhkan data setelah dikompresi harus dapat diekstrak/dekompres lagi tepat sama. Contoh pada data teks, data program/biner, beberapa image seperti GIF dan PNG.
  • Kadangkala ada data-data yang setelah dikompresi dengan teknik ini ukurannya menjadi lebih besar atau sama.

 

 

 

 

Contoh :

 

  • Kriteria Algoritma Dan Aplikasi Komprensi Data.

 

ü  Kualitas data hasil enkoding: ukuran lebih kecil, data tidak rusak untuk kompresi lossy.

ü  Kecepatan, ratio, dan efisiensi proses kompresi dan dekompresi

ü  Ketepatan proses dekompresi data: data hasil dekompresi tetap sama dengan data sebelum dikompres (kompresi loseless)

 

ü  Source Coding

  • Bersifat lossy
  • Berkaitan dengan data semantik (arti data) dan media.
  • Mis : Prediction (DPCM, DM), Transformation (FFT, DCT), Layered Coding (Bit position, subsampling, sub-band coding), Vector Quantization

ü  Hybrid Coding

  • Gabungan antara lossy + loseless
  • Mis : JPEG, MPEG, H.261, DVI

 

 

  • Contoh Teknik Komprensi Teks

ü  Run-Length-Encoding (RLE)

ü  Kompresi data teks dilakukan jika ada beberapa huruf yang sama yang ditampilkan berturut-turut :

                        Misal : Data: ABCCCCCCCCDEFGGGG = 17 karakter

                        RLE tipe 1 (min. 4 huruf sama) : ABC!8DEFG!4 = 11 karakter

ü  RLE ada yang menggunakan suatu karakter yang tidak digunakan dalam teks tersebut seperti misalnya ‘!’ untuk menandai.

ü  Kelemahan? Jika ada karakter angka, mana tanda mulai dan akhir?

Misal data : ABCCCCCCCCDEFGGGG = 17 karakter

RLE tipe 2 : -2AB8C-3DEF4G = 12 karakter

Misal data : AB12CCCCDEEEF = 13 karakter

RLE tipe 2: -4AB124CD3EF = 12 karakter

 

n  Static Huffman Coding

ü  Dibuat oleh seorang mahasiswa MIT bernama David Huffman pada tahun 1952

ü  Salah satu metode paling lama dan paling terkenal dalam kompresi teks.

Algoritma Huffman menggunakan prinsip pengkodean mirip dengan kode Morse :  tiap karakter (simbol) dikodekan  dengan rangkaian beberapa bit ; karakter yang sering muncul dikodekan dengan rangkaian bit yang pendek dan karakter yang jarang muncul dikodekan.dengan rangkaian bit yang lebih panjang

ü  Frekuensi karakter dari string yang akan dikompres dianalisa terlebih dahulu. Selanjutnya dibuat pohon huffman yang merupakan pohon biner dengan root awal yang diberi nilai 0 (sebelah kiri) atau 1 (sebelah kanan), sedangkan selanjutnya untuk dahan kiri selalu diberi nilai 1 (kiri) – 0 (kanan) dan di dahan kanan diberi nilai 0 (kiri) – 1 (kanan).

ü  A bottom-up approach = frekuensi terkecil dikerjakan terlebih dahulu dan diletakkan ke dalam leaf (daun).

ü  Kemudian leaf-leaf akan dikombinasikan dan dijumlahkan probabilitasnya menjadi root diatasnya.

 

n  Shannon-Fano Algorithm

ü  Dikembangkan oleh Shannon (Bell Labs) dan Robert Fano (MIT)

ü  Algoritma :

ü  Urutkan simbol berdasarkan frekuensi kemunculannya

ü  Bagi simbol menjadi 2 bagian secara rekursif, dengan jumlah yang kira-kira sama pada kedua bagian, sampai tiap bagian hanya terdiri dari 1 simbol.

ü  Cara yang paling tepat untuk mengimplementasikan adalah dengan membuat binary tree.

n  DICTIONARY-BASED CODING

Algoritma Lempel-Ziv-Welch (LZW) menggunakan teknik adaptif dan berbasiskan “kamus” Pendahulu LZW adalah LZ77 dan LZ78 yang dikembangkan oleh Jacob Ziv dan Abraham Lempel pada tahun 1977 dan 1978. Terry Welch mengembangkan teknik tersebut pada tahun 1984. LZW banyak dipergunakan pada UNIX, GIF, V.42 untuk modem

 

Aplikasi Komprensi Data

 

n  ZIP File Format

ü  Ditemukan oleh Phil Katz untuk program PKZIP kemudian dikembangkan untuk WinZip, WinRAR, 7-Zip.

ü  Berekstensi *.zip dan MIME application/zip

ü  Dapat menggabungkan dan mengkompresi beberapa file sekaligus menggunakan bermacam-macam algoritma, namun paling umum menggunakan Katz’s Deflate Algorithm.

                              Beberapa method Zip :

ü  Shrinking : merupakan metode variasi dari LZW

ü  Reducing : merupakan metode yang mengkombinasikan metode same byte sequence based dan probability based encoding.

ü  Imploding : menggunakan metode byte sequence based dan Shannon-Fano encoding.

ü  Deflate : menggunakan LZW

ü  Bzip2, dan lain-lain

 

 

n  RAR File

ü  Ditemukan oleh Eugene Roshal, sehingga RAR merupakan singkatan dari Roshal Archive pada 10 Maret 1972 di Rusia.

ü  Berekstensi .rar dan MIME application/x-rar-compressed

ü  Proses kompresi lebih lambat dari ZIP tapi ukuran file hasil kompresi lebih kecil.

ü  Aplikasi: WinRAR yang mampu menangani RAR dan ZIP, mendukung volume split, enkripsi AES.

 

 

 

 

 

 

Kesimpulan :

 Kompresi data merupakan proses pengkodean Informasi  menggunakan bit atau  information-bearing unit yang lain yang lebih rendah dari pada representasi data yang tidak terkodekan dengan suatu system encoding  tertentu.

Tujuan dari kompresi data adalah untuk merepresentasikan suatu data digital dengan sesedikit mungkin bit, tetapi tetap mempertahankan kebutuhan minimum untuk membentuk kembali data aslinya. Data digital ini dapat berupa  text, gambar, suara, dan kombinasi dari ketiganya, seperti video.

Jenis-jenis komprensi data berdasarkan Output
Lossy Compression

  • Ddata hasil dekompresi tidak sama dengan data sebelum kompresi namun sudah “cukup” untuk digunakan. Contoh: Mp3, streaming media, JPEG, MPEG, dan WMA.
  • Kelebihan: ukuran file lebih kecil dibanding loseless namun masih tetap memenuhi syarat untuk digunakan.

Teknik

 membuang bagian data yang tidak berguna, tidak dirasakan, tidak dilihat oleh manusia sehingga manusia masih beranggapan bahwa data tersebut masih bisa digunakan walaupun sudah dikompresi.

Misal :  image asli berukuran 12,249 bytes,  dilakukan kompresi dengan JPEG kualitas 30 dan berukuran 1,869 bytes : berarti image tersebut 85% lebih kecil dan ratio kompresi 15%.

    Loseless

 

Kriteria Algoritma Dan Aplikasi Komprensi Data.

 

ü  Kualitas data hasil enkoding: ukuran lebih kecil, data tidak rusak untuk kompresi lossy.

ü  Kecepatan, ratio, dan efisiensi proses kompresi dan dekompresi

ü  Ketepatan proses dekompresi data: data hasil dekompresi tetap sama dengan data sebelum dikompres (kompresi loseless)

 

ü  Source Coding

ü  Hybrid CodingMis

 

Sumber :

 

–          Adi Nugroho,ST.,MMsi.2004 Konsep pengembangan Basis Data Informatika

–          http://www.ziddu.com/download/14332980/pengantar kompresidata.rar.htm

 

Tinggalkan Balasan

Isikan data di bawah atau klik salah satu ikon untuk log in:

Logo WordPress.com

You are commenting using your WordPress.com account. Logout / Ubah )

Gambar Twitter

You are commenting using your Twitter account. Logout / Ubah )

Foto Facebook

You are commenting using your Facebook account. Logout / Ubah )

Foto Google+

You are commenting using your Google+ account. Logout / Ubah )

Connecting to %s