Berbagai
Teknik Kompresi Data
Seiring
dengan perkembangan informasi yang sangat cepat dan juga perkembangan teknologi
multimedia yang sangat pesat, maka data yang berkembang di seluruh dunia
akan terus bertambah dan ukuran dari data-data yang dihasilkan juga terus
meningkat. Hal ini juga didukung oleh semakin lebar dan murahnya bandwidthinternet. Akan tetapi, tempat (storage) yang tersedia untuk menyimpan data saat ini
masih terbatas dan juga internet yang murah dan cepat tidak dimiliki oleh semua
orang, sehingga untuk melakukan transfer data yang besar melalui jaringan internet
cukup sulit dilakukan.
Mengingat
hal di atas, banyak orang yang berfikir bagaimana caranya untuk melakukan
efisiensi penyimpanan data pada tempat penyimpanan yang terbatas. Hingga saat
ini, sudah sangat banyak metode/algoritma yang dapat digunakan untuk melakukan
kompresi/pemampatan pada data. Pada tulisan ini, saya akan membahas beberapa
teknik kompresi data untuk data dengan tipe Text, Image, Audio, dan Video.
Sebelum
membahas tentang berbagai algoritma tersebut, perlu diketahui bahwa pada
kompresi data terdapat jenis kompresi Lossless Compression dan Lossy Compression.
Lossless
Compression
Lossless
Compression merupakan metode kompresi data dimana data
yang sudah dikompresi dapat dikembalikan ke bentuk semula secara utuh. Kompresi
jenis lossless compression biasanya melakukan kompresi
dengan dua buah langkah: langkah pertama yaitu membangkitkan model statistik
dari data yang dimasukkan, dan langkah kedua adalah menggunakan model tersebut
untuk memetakan data yang dimasukan kedalam rangkaian bit dimana data/simbol
yang memiliki frekuensi tertinggi akan menghasilkan keluaran (output) yang paling pendek. Salah satu implementasi
dari lossless compression adalah Kode Huffman (Huffman Coding) yang merupakan bagian dari kompresi
data/file dengan format ZIP.
Lossy
Compression
Lossy
Compression merupakan kebalikan dari Lossless Compression dimana data yang sudah
dikompresi akan sulit atau bahkan tidak mungkin dikembalikan ke bentuk semula
secara utuh. Biasanya kompresi jenis ini melakukan kompresi data dengan cara
menghilangkan/membuang sebagian data dan tidak akan memberikan perubahan yang
besar pada data tersebut.
1. Kompresi
data tipe 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 :
1.
Hitung frekuensi kemunculan setiap simbol.
2.
Pilih dua buah simbol dengan frekuensi
terkecil, lalu gabungkan dalam satu tangkai.
3.
Ulangi langkah kedua hingga tidak ada lagi
tangkai yang dapat digabungkan.
Misalnya, terdapat
sebuah pesan : “ABABAAAADDDCCCFBB”. Pesan tersebut berukuran 17 byte (termasuk
spasi).
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%) !!!.
2.
Kompresi data tipe Image
Kompresi
pada jenis data Image biasanya dilakukan dengan metode kompresi lossy compression dimana terdapat beberapa
informasi yang dihilangkan untuk mengurangi ukuran dari informasi yang ada.
Contoh
penerapan kompresi data pada Image adalah JPEG dan Quantizing Compression.
Teknik
kompresi Quantizing Compression bersifat lossy dan digunakan untuk mereduksi data dengan
asumsi bahwa perubahan data tidak akan berpengaruh banyak
pada informasi. Kompresi ini dilakukan dengan menggunakan matrik
kuantisasi.
Contoh
:
Hasil
Reduksi :
Sedangkan
untuk tipe data JPEG, kompresi data dapat dilakukan
dengan tiga buah model :
a. Sequential:
kompresi dilakukan secara top-down, left-right menggunakan proses
single-scan dan algoritma Huffman Encoding 8 bit secara sekuensial.
b. Progressive: kompresi
dilakukan dengan multiple-scan secara progresif, sehingga kita dapat
mengira-ira gambar yang akan kita download.
c. Hierarchical:
super-progressive mode, dimana image akan dipecah-pecah menjadi sub image yang
disebut frame. Frame pertama akan membentuk image dalam resolusi rendah hingga
berangsur-angsur ke resolusi tinggi.
3. Kompresi
data tipe Audio
Kompresi
data jenis audio juga biasanya bersifat lossy. Salah satu implementasi
dari kompresi data audio adalahMP3. MP3 merupakan salah satu format file audio yang
sangat sering kita temui. MP3 didapat dari proses kompresi data hasil rekaman
dan memanfaatkan kelemahan pendengaran manusia dalam proses kompresinya.
Kompresi data pada file MP3 dilakukan dengan cara :
1. Menghilangkan
informasi-informasi audio yang tidak dapat didengar oleh manusia (frekuensi
suara yang diluar jangkauan indera pendengaran manusia).
2. Manusia
tidak mampu mendengarkan suara pada frekuensi tertentu dengan amplitude
tertentu jika pada frekuensi di dekatnya terdapat suara dengan amplitude yang
jauh lebih tinggi. Oleh karena itu, informasi audio tersebut tidak perlu
dikodekan.
3. Terkadang
dual-channel stereo mengirimkan informasi yang sama. Informasi tersebut cukup
ditempatkan dalam salah satu channel saja dengan ditambah beberapa informasi
tertentu.
4. Kompresi
data tipe Video
Video
dapat dikompresi dengan metode lossless compression maupun lossy compression. Dengan menggunakanlossless compression seperti huffman coding atau arithmetic coding, maka data video dapat dikembalikan
secara utuh seperti semula. Data video juga dapat dikompresi dengan menggunakan
metode lossy compression, contohnya dengan menghilangkan
beberapa frame pada video tersebut.
Video
memiliki format yang beragam, dan masing-masing format tersebut
menggunakan codec yang berbeda dan
memiliki skema kompresi yang berbeda pula. Salah satu format file video hasil
kompresi adalah MPEG.
5. Kelebihan dan kekurangan
berbagai macam metode kompresi data
Setelah
melihat beberapa pembahasan diatas, kita dapat mengetahui bahwa kompresi lossless menggunakan algoritma RLE dan Huffman Coding akan
tergantung pada data yang akan dikompresi. Contohnya, dalam algoritma RLE (Run Length Encoding), jika dalam runtunan,
karakter yang muncul berbeda-beda maka ukuran file akan menjadi dua kali lipat
atau bahkan lebih. Dalam penerapan Huffman Coding juga
ukuran file outputtergantung pada file input, terkadang juga dapat terjadi hasil kompresi
memiliki ukuran yang lebih besar dari ukuran semula dan juga penerapan Huffman Coding membutuhkan tempat pada awal (header) file untuk menyimpan informasi yang diperlukan
untuk proses dekompresi (decoding).
Kompresi
pada data audio, image, dan video juga
sebenarnya dapat menggunakan metode general purposeseperti
Huffman Coding, RLE, dan algoritma kompresi lossless lainnya.
Selain itu, tipe data audio, image, danvideo juga
dapat dikompresi menggunakan metode kompresi lossy seperti
menghilangkan beberapa informasi yang tidak dibutuhkan, tetapi, hasil dari
kompresi tersebut akan menurunkan kualitas dari data dan tidak akan dapat
dikembalikan seperti semula secara utuh.
6. Format
file hasil kompresi
Sebenarnya,
format file hasil kompresi dapat dibuat sesuai dengan keinginan pembuat software kompresi, seperti yang terdapat pada
software Winzip yang akan menghasilkan format hasil
kompresi ZIP dan Winraryang dapat
menghasilkan format hasil kompresi berekstensi RAR.
0 komentar:
Posting Komentar