Definisi Kompresi
>> Kompresi data dalam ilmu komputer adalah sebuah cara untuk memadatakan data sehingga hanya memerlukan ruangan penyimpanan lebih kecil sehingga lebih efisien dalam menyimpannya atau mempersingkat waktu pertukaran data tersebut.
Kompresi data bertujuan untuk mengurangi ukuran data tanpa merusak tujuan dari data tersebut. Kompresi data menggunakan sedikit disk space. Kompresi data percepat akses, kompresi data dapat membuat lebih efisien.
>> Kompresi Data adalah salah satu subyek di bidang teknologi informasi yang saat ini telah diterapkan secara luas. Gambar-gambar yang anda dapatkan di berbagai situs internet pada umumnya merupakan hasil kompresi ke dalam format GIF atau JPEG. File video MPEG adalah hasil proses kompresi pula. Penyimpanan data berukuran besar pada server pun sering dilakukan melalui kompresi.
Ada beberapa format file yang digunakan untuk membuat file archive. Misalnya Unix Archiver (.a, .ar), Tape Archiver (.tar), LBR (.lbr). Unix Archiver digunakan pada platform Unix-like, merupakan format archive tradisional yang sekarang hanya digunakan untuk membuat static libraries. Tape Archiver, juga digunakan pada platform Unix-like, yang merupakan format archive yang umum digunakan. Sedangkan LBR digunakan pada platform MS-DOS.
Format file compression:
Untuk mengkompres data, ada beberapa format file yang digunakan seperti bzip2 (.bz2), gzip (.gz), lzma (.lzma), lzo (.lzo), pack (.z), compress (.Z). Perbedaan masing-masing format kompresi ini adalah algoritma yang digunakan. Seperti bzip2 yang menggunakan Burrows-Wheeler transform diikuti dengan move-to-front transform dan terakhir Huffman coding. Format gzip yang menggunakan algoritma DEFLATE untuk kompresi data, lzma menggunakan algoritma 7-zip, lzo menggunakan algoritma LZO. Beberapa dari format kompresi data ini digunakan bersama-sama ketika meng-archive file. Seperti Tape Archiver (.tar) yang digunakan bersama bzip2 (ekstensi file menjadi .tar.bz2), gzip (ekstensi file menjadi .tar.gz) atau compress (ekstensi file menjadi .tar.Z).
File archive + compression
Sekarang ini sudah banyak format file yang menawarkan archive+compression. Seperti ARC (.arc), ARJ (.arj), Cabinet (.cab), ZIP (.zip), Jar (.jar), Tar dengan GZip, BZip2, Compress, LZMA (.tar.gz, .tgz, .tar.bz2, .tar.Z, .tar.lz, .tlz). Jenis-jenis format ini “boleh” di-restore dengan software gratisan (tanpa perlu lisensi dari si pembuat format file tersebut). Sedangkan format file seperti WinACE (.ace), RAR (.rar), StuffIt (.sit, .sitx) hanya “boleh” di-restore oleh software tertentu (software yang telah mendapat lisensi untuk me-restore/ekstrak file dari si pembuat format file tersebut).
File-file yang telah di-archive+compress biasanya sering dijumpai di Internet. Karena, untuk pertukaran data yang cepat, diperlukan sebuah metode untuk mengirimkan data dalam jumlah yang sedikit dan dengan ukuran yang kecil.
Teknik Kompresi Data
1. Losseles Compression, Teknik kompresi yang tidak mengurangi ukuran aslinya. Losseles artinya tidak ada data yang hilang, menggunakan algortima tertentu untuk mengompres data (compress) dan mengembalikan ke ukuran semula (decompress), dipakai untuk mengompres data dan program.
2. Lossy Compression, Teknik kompresi yang mengurangi ukuran aslinya. Lossy artinya ada data yang hilang, bertujuan untuk mengefisienkan data,biasanya dipakai untuk mengompres data multimedia.
Kompresi data sangat populer sekarang ini karena dua alasan yaitu (Salomon, 2007) :
-Orang – orang lebih suka mengumpulkan data. Tidak peduli seberapa besar media penyimpanan yang dimilikinya. Akan tetapi cepat atau lambat akan terjadi overflow.
- 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.
Defenisi Algoritma :
1. Algoritma adalah urutan langkah – langkah berhingga untuk memecahkan masalah logika atau matematika
2. Algoritma adalah logika, metode dan tahapan (urutan) sistematis yang digunakan untuk memecahkan suatu permasalahan
3. Algoritma adalah urutan langkah – langkah logis penyelesaian masalah yang disusun secara sistematis dan logis.
Algoritma Huffman
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 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), 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.
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.
Algoritma LZW (Lempel-Ziv-Welch)
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 :
KAMUS diinisialisasi dengan semua karakter dasar yang ada : {‘A’..’Z’,’a’..’z’,’0’..’9’}.
W = karakter pertama dalam stream karakter.
K = karakter berikutnya dalam stream karakter.
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 dictionarypada awal proses diset dengan 3 karakter dasar yang ada: “A”, “B”, dan “C”. Tahapan proses kompresi ditunjukkan pada Tabel 2.
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 tabel dictionary ke dalam data kompresi. Berikut algoritma dekompresi LZW :
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 :
- Output string.CW ke stream karakter
- P = string.PW
- C = karakter pertama dari string.CW
- Tambahkan string (P+C) ke dalam
* Jika tidak, maka :
- P = string.PW
- C = karakter pertama dari string.PW
- 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).