1

PTKI A: File Compression

Kompresi File

Introduksi Jika anda mendownload banyak program dan file dari Internet, tentunya anda sudah pernah bertemu dengan file ZIP. Jenis sistem kompresi ini sangat berguna, khususnya para pengguna Web, karena:

memungkinkan untuk mengurangi jumlah keseluruhan bit dan Byte di dalam sebuah file, sehingga

dapat ditransmisikan lebih cepat lewat Internet dan memakan ruang lebih kecil di disk

Setelah anda mendownload file, komputer yang anda gunakan melakukan ekspansi file tersebut ke ukuran normalnya dengan mempergunakan aplikasi seperti WinZip, WinRar, 7Zip, atau Stuffit. Jika semua berjalan lancar, maka file yang diekspansi akan identik dengan file asli sebelum dikompresi. Secara sekilas, ini tampaklah misterius. Bagaimana anda dapat mereduksi sejumlah bit dan Byte, kemudian menambahkan jumlah bit tersebut? Ide dasar dibalik proses tersebut adalah sederhana. Sebagian besar file komputer cukup redundan (berulang) memiliki informasi yang sama yang terdaftar secara berulang. Program kompresi file menghilangkan redundansi. Sebuah program kompresi file mendaftarkan informasi hanya sekali, dan kemudian mengacu kepada informasi tersebut kapan pun informasi muncul di dalam program. Sebuah contoh: kata. Dalam pidato inaugurasi John F. Kennedy, pada tahun 1961, Beliau mengucapkan sebuah kalimat terkenal:

"Ask not what your country can do for you - ask what you can do for your country." Kutipan ini memiliki 17 kata, yang tersusun atas :

61 huruf, 16 spasi, satu tanda sambung, dan satu titik. Jika setiap hutuf, spasi, atau tanda baca memerlukan ruang sebanyak 1 unit di memori, kita akan mendapatkan total 79 unit memori. Untuk menurunkan ukuran file, maka kita harus mencari redundansi. Secara singkat, kita dapat melihat bahwa:

"ask" muncul sebanyak dua kali "what" muncul sebanyak dua kali "your" muncul sebanyak dua kali "country" muncul sebanyak dua kali "can" muncul sebanyak dua kali "do" muncul sebanyak dua kali "for" muncul sebanyak dua kali "you" muncul sebanyak dua kali

Dengan mengabaikan perbedaan huruf kecil dan kapital, secara kasar setengah frasa adalah berulang. Kesembilan kata - ask, not, what, your, country, can, do, for, you memberikan hampir semua yang kita perlukan untuk keseluruhan kutipan.

2

PTKI A: File Compression

Redundansi dan Algoritma Sebagian besar program kompresi menggunakan sebuah variasi LZ adaptive dictionary-based algorithm untuk mengurangi ukuran file. LZ adalah singkatan Lempel-Ziv, para pencipta algoritma. Dan Algorithm adalah metode untuk melakukan katalog atas pecahan data. Sistem untuk mengatur dictionary bervariasi, tetapi juga dapat sesederhana seperti sebuah daftar bernomor. Ketika kita mengamati kutipan pidato Kennedy, kita dapat mengambil kata berulang dan memasukkan ke dalam indeks bernomor. Kemudian, kita dapat menulis nomor, bukannya seluruh kata. Jadi, inilah dictionary kita:

1. ask 2. what 3. your 4. country 5. can 6. do 7. for 8. you

Kalimat kita sekarang dibaca:

"1 not 2 3 4 5 6 7 8 -- 1 2 8 5 6 7 3 4"

Jika anda tahu sistem yang digunakan, maka anda dapat melakukan rekonstruksi kalimat asli menggunakan dictionary ini dan pola nomor. Inilah yang dilakukan oleh program ekspansi pada komputer anda. Anda juga mungkin akan menjumpai sebuah file terkompresi yang dapat membuka dirinya sendiri. Untuk menciptakan file semacam ini, programmer memasukkan program ekpansi dengan file terkompresi. Program tersebut akan melakukan rekonstruksi otomatis setelah file selesai didownload. Hmm., tapi seberapa banyak ruang yang kita bisa hemat dengan sistem ini?

"1 not 2 3 4 5 6 7 8 -- 1 2 8 5 6 7 3 4" tentunya jelas lebih singkat daripada

"Ask not what your country can do for you; ask what you can do for your country;" tetapi kita hasrus ingat bahwa kita perlu menyimpan dictionary bersama dengan file. Kita sudah melihat, bahwa frasa lengkap memakan ruang sebanyak 79 unit. Kalimat terkompresi (spasi termasuk di dalamnya) menghabiskan 37 unit, dan dictionary juga menghabiskan 37 unit. Ini menghasilkan sebuah file berukuran 74 unit, jasi kita belum mereduksi file dengan jumlah banyak. Akan tetapi, ini Cuma satu kalimat saja. Dapat anda bayangkan jika program kompresi bekerja atas keseluruhan pidato Kennedy, akan terdapat lebih banyak pengulangan kata.

3

PTKI A: File Compression

Mencari Pola Pada contoh sebelumnya, kita mengambil semua kata terulang dan meletakkan ke sebuah dictionary. Bagi kita, ini adalah cara paling mungkin dalam menulis sebuah dictionary. Tetapi sebuah program kompresi memandang dengan cara yang berbeda:

Program tidak memiliki konsep kata yang terpisah hanya mencari pola (pattern) Untuk mereduksi ukuran file, maka dengan hati-hati memilih pola yang akan dimasukkan ke

dalam dictionary.

"Ask not what your country can do for you - ask what you can do for your country."

Melalui pendekatan ini, kita akan dapat melihat sebuh dictionary yang jauh berbeda. Jika program kompresi melakukan scan terhadap frasa di atas, maka akan langsung menemui redundansi.

1. Di dalam "ask not what your", ada pengulangan dari huruf t yang diikuti dengan sebuah spasi pada not dan what . Jika program kompresi menulis ke dalam dictionary, maka akan langsung menulis sebuah angka 1 setiap kali sebuah t diikuti dengan sebuah spasi. Akan tetapi, melihat ukuran kalimatnya, maka kemungkinan program tidak akan melakukannya.

2. Hal berikut yang akan dikenali program adalah ou, yang terdapat pada your dan country. Jika kalimatnya lebih panjang, maka menuliskan pola ini ke dalam dictionary akan dapat menghemat banyak tempat. ou adalah sebuah kombinasi yang umum di dalam Bahasa Inggris.

3. Tidak hanya ou yang diulangi, keseluruhan kata your dan country diulang, biasanya diulang secara bersamaan seperti frasa your country. Maka kemungkinan program akan menggantikan ou dengan your country ke dalam dictionary.

4. Frasa "can do for" juga terulang. Sebanyak satu kali, diikuti dengan your dan diikuti dengan satu kali oleh you yang menghasilkan pola terulang " can do for you. Hal ini memungkinkan kita menulis 15 karakter dengan 1 angka nilai, sedangkan your country hanya memungkinkan menulis 13 karakter dengan 1 angka nilai.

Maka program akan melakukan overwrite terhadap entry "your country" sebagai "r country", dan kemudian

menulis sebuah entry terpisah untuk can do for you. 5. Program terus bekerja seperti ini, mengambil semua bit informasi yang terulang, dan melakukan

kalkulasi pola mana yang harus ditulis ke dalam dictionary. Jadi , anda bisa lihat bahwa cara program melakukan ini cukup rumit.

Tidak masalah cara tertentu yang anda pergunakan, sistem pencarian in-depth memungkinkan anda melakukan kompresi lebih efisien. Dengan mempergunakan pola diatas, dan menambahkan "__" untuk spasi, kita mendapatkan dictionary:

1. ask__ 2. what__ 3. you 4. r__country 5. __can__do__for__you

Dan kalimat lebih singkatnya:

"1not__2345__--__12354"

Sentence = 18 unit memori. Dictionary = 41 unit. Total = 59 unit terkompresi, dari 79 unit.

4

PTKI A: File Compression

Ini adalah salah satu cara kompresi terhadap frasa, dan mungkin bukan cara yang paling efisien. Jadi sebaik apakah sistem ini? Ratio reduksi-file bergantung kepada sejumlah faktor, termasuk tipe file, ukuran dan skema kompresi.

Pada sebagian besar bahasa di dunia, huruf dan kata tertentu seringkali muncul bersamaan di dalam pola yang sama. Karena tingkat redundansi yang tinggi, maka file teks terkompresi sangat baik. Reduksi sebesar 50 persen atau lebih adalah rata-rata yang baik.

Sebagian besar bahasa pemrograman juga sangat redundan karena menggunakan kumpulan perintah yang relatif kecil, yang seringkali muncul bersamaan di dalam sekumpulan pola.

File yang berisi banyak informasi yang unik, seperti gambar dan file MP3, tidak dapat banyak terkompresi dengan sistem ini karena tidak banyak terdapat perulangan pola.

Jika sebuah file memiliki banyak pola terulang, tingkat reduksi biasanya meningkat. Hal itu dapat kita lihat pada contoh terdahulu. Jika kita meneliti lebih banyak pidato Kennedy, kita dapat mengacu ke pola lebih sering, dan tentu saja dapat membebaskan lebih banyak ruang kosong.

Kompresi Lossy dan Lossless Jenis kompresi yang telah kita bahas tadi disebut sebagai Kompresi Lossless, karena memungkinkan anda menciptakan ulang (re-kreasi) sesuai file aslinya. Semua kompresi ini memiliki dasar gagasan memecah file ke dalam bentuk lebih kecil untuk transmisi (pengiriman) atau juga penyimpanan, lalu kemudian menyatukannya kembali di ujung lain sehingga dapat dipergunakan lagi. Kompresi Lossy bekerja dengan cara yang sangat berbeda. Program ini menghilangkan bit yang tidak diperlukan ("unnecessary bits) dari informasi, membuat ukuran file menjadi lebih kecil. Kompresi jenis ini dbanyak digunakan untuk mengurangi ukuran file berjenis bitmap, yang cenderung berukuran besar. Tentu saja dengan Kompresi Lossy, anda tidak dapat file asli setelah dikompresi.