Kompresi File Text
Seiring berkembangnya teknologi informasi, produk-produk multimedia berkembang dengan pesat. Semakin berkembangnya produk multimedia, maka dibutuhkan ukuran data yang besar. Meskipun bandwith internet semakin lebar, tapi bagi yang memiliki akses internet lambat akan kesulitan mendapatkan informasi dari produk multimedia itu membutuhkan ukuran besar sehingga membutuhkan waktu untuk mendapatkan informasi secara penuh.
Oleh karena itu saya akan membahas cara untuk melakukan efisiensi penyimpanan data untuk tempat atau penyimpanan terbatas. Saya akan bahas kompresi untuk file text.
Didalam representasi data pada komputer, text merupakan kumpulan dari karakter/simbol yang dapat dibaca baik oleh manusia maupun oleh komputer. Satu buah karakter/simbol biasanya berukuran 1 byte / 8 bit.
Untuk melakukan kompresi data jenis text, kita harus menggunakan metode lossless compression karena data berjenis text harus dapat dikembalikan ke bentuk semula secara utuh untuk dapat kembali dibaca.
Metode kompresi RLE (Run Length Encoding) dan Huffman Coding adalah metode kompresi untuk data berjenis text yang akan saya jelaskan pada tulisan ini.
RLE (Run Length Encoding)
Misalkan, ada seseorang yang alay berteriak :
“AAAAAKUUUUU CHAYYYYYAAAAANK KAAAAMUUUUUUUUUUUUUUUUUUUUUUUU !!!!!!”
Pesan diatas akan sangat cocok jika dikompresi menggunakan metode kompresi RLE karena kompresi RLE menghitung jumlah kemunculan simbol lalu menuliskan simbol tersebut sebanyak satu kali diikuti dengan jumlah kemunculannya. Data diatas berukuran 66 byte, dan kita akan melakukan kompresi RLE terhadap data tersebut :
- Ubah data dalam bentuk sekuensial
Data teks diatas sudah dalam bentuk sekuensial :
AAAAAKUUUUU CHAYYYYYAAAAANK KAAAAMUUUUUUUUUUUUUUUUUUUUUUUU!!!!!!
- Hitung jumlah kemunculan karakter
(A,6) (K,1) (U,5) (spasi,1) (C,1) (H,1) (A,1) (Y,5) (A,5) (N,1) (K,1) (spasi,1) (K,1) (A,5) (M,1) (U,24)(!,6)
- Tulis hasil kompresi
A6K1U5 1C1H1A1Y5A5N1K1 1K1A5M1U24!6
Setelah proses kompresi, maka data yang dihasilkan akan berukuran 35 byte. Dengan proses kompresi tersebut, kita telah menghemat tempat penyimpanan sebesar 31 byte (47%) !!.
Huffman Coding
Kompresi dengan algoritma Huffman Coding dilakukan dengan cara :
- Hitung frekuensi kemunculan setiap simbol.
- Pilih dua buah simbol dengan frekuensi terkecil, lalu gabungkan dalam satu tangkai.
- Ulangi langkah kedua hingga tidak ada lagi tangkai yang dapat digabungkan.
Pertama, kita akan menghitung kemunculan setiap karakter :
Simbol
|
Kemunculan
|
A
|
6
|
B
|
4
|
C
|
3
|
D
|
3
|
F
|
1
|
Pilih dua buah simbol dengan frekuensi terkecil, yaitu simbol F dan D, lalu gabungkan.
Simbol
|
Kemunculan
|
A
|
6
|
B
|
4
|
C
|
3
|
(D,F)
|
4
|
Pilih kembali dua buah simbol dengan frekuensi terkecil, lalu gabungkan. Ulangi hal ini hingga tidak dapat lagi digabungkan.
Simbol
|
Kemunculan
|
A
|
6
|
B
|
4
|
(C,(D,F))
|
7
|
Simbol
|
Kemunculan
|
(A,B)
|
10
|
(C,(D,F))
|
7
|
Simbol
|
Kemunculan
|
((A,B), (C,(D,F)))
|
17
|
Pembentukan pohon Huffman :
Dari pohon diatas, maka huruf ‘D’ dapat kita kodekan dengan : 000. Berikut ini merupakan tabel lengkap hasil pengkodean seluruh simbol :
Simbol
|
Kode
|
A
|
10
|
B
|
11
|
C
|
00
|
D
|
010
|
F
|
011
|
Berdasarkan tabel diatas, maka “ABABAAAADDDCCCFBB” dapat kita kodekan menjadi seperti berikut : 101110111010101001001001000000001101111. Data hasil kompresi berukuran 29 bit / 4 byte. Dengan demikian, kita telah menghemat sebanyak 13 byte (76%) !!!.
Sumber:
http://alan.blog.widyatama.ac.id/2012/04/16/tugas-pengantar-multimedia-16-april-2012/