PENDAHULUAN
Kompresi Data merupakan cabang ilmu komputer yang
bersumber dari Teori Informasi. Teori Informasi sendiri adalah salah satu
cabang Matematika yang berkembang sekitar akhir dekade 1940-an. Tokoh utama
dari Teori Informasi adalah Claude Shannon dari Bell Laboratory.
Teori Informasi mengfokuskan pada berbagai metode
tentang informasi termasuk penyimpanan dan pemrosesan pesan. Teori Informasi
mempelajari pula tentang redundancy (informasi tak berguna) pada pesan. Semakin
banyak redundancy semakin besar pula ukurang pesan, upaya mengurangi redundancy
inilah yang akhirnya melahirkan subyek ilmu tentang Kompresi Data.
Teori Informasi menggunakan terminologi entropy
sebagai pengukur berapa banyak informasi yang dapat diambil dari sebuah pesan.
Kata “entropy” berasal dari ilmu termodinamika. Semakin tinggi entropy dari
sebuah pesan semakin banyak informasi yang terdapat di dalamnya. Entropy dari
sebuah simbol didefinisikan sebagai nilai logaritma negatif dari probabilitas
kemunculannya. Untuk menentukan konten informasi dari sebuah pesan dalam jumlah
bit dapat digunakan rumus sebagai berikut:
number of bits = -log base 2 (probability)
Entropy dari keseluruhan pesan adalah jumlah dari
keseluruhan entropy dari seluruh symbol.
PENGERTIAN KOMPRESI DATA
- Kompresi
berarti memampatkan / mengecilkan ukuran
- Kompresi
data adalah proses mengkodekan informasi menggunakan bit atau
information-bearing unit yang lain yang lebih rendah daripada representasi
data yang tidak terkodekan dengan suatu sistem enkoding tertentu.
- 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”
- Pengiriman
data hasil kompresi dapat dilakukan jika pihak pengirim/yang melakukan
kompresi dan pihak penerima memiliki aturan yang sama dalam hal kompresi
data
- Pihak
pengirim harus menggunakan algoritma kompresi data yang sudah baku dan
pihak penerima juga menggunakan teknik dekompresi data yang sama dengan
pengirim sehingga data yang diterima dapat dibaca / di-dekode kembali
dengan benar
- Kompresi
data menjadi sangat penting karena memperkecil kebutuhan penyimpanan data,
mempercepat pengiriman data, memperkecil kebutuhan bandwidth
- Teknik
kompresi bisa dilakukan terhadap data teks/biner, gambar (JPEG, PNG,
TIFF), audio (MP3, AAC, RMA, WMA), dan video (MPEG, H261, H263)
Jenis Kompresi Data
Berdasar mode penerimaan data yang
diterima manusia :
- Dialoque
Mode: yaitu proses penerimaan data dimana pengirim dan penerima seakan
berdialog (real time), seperti pada contoh video conference. Dimana
kompresi data harus berada dalam batas penglihatan dan pendengaran
manusia. Waktu tunda (delay) tidak boleh lebih dari 150 ms, dimana
50 ms untuk proses kompresi dan dekompresi, 100 ms mentransmisikan data
dalam jaringan
- Retrieval
Mode: yaitu proses penerimaan data tidak dilakukan
secara real time
Dapat dilakukan fast
forward dan fast rewind di client
Dapat dilakukan random access terhadap data dan
dapat bersifat interaktif
Kompresi Data Berdasarkan Output :
- Lossy
Compression
Teknik kompresi dimana data 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.
Biasanya teknik ini membuang bagian-bagian data yang
sebenarnya tidak begitu berguna, tidak begitu dirasakan, tidak begitu dilihat
oleh manusia sehingga manusia masih beranggapan bahwa data tersebut masih bisa
digunakan walaupun sudah dikompresi.
Misal terdapat image asli berukuran 12,249
bytes, kemudian dilakukan kompresi dengan JPEG kualitas 30 dan berukuran 1,869
bytes berarti image tersebut 85% lebih kecil dan ratio kompresi 15%
- Loseless
Teknik kompresi dimana 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
Berdasarkan tipe peta kode yang digunakan untuk
mengubah pesan awal (isi file input) menjadi sekumpulan codeword,
metode kompresi terbagi menjadi dua kelompok, yaitu :
(a) Metode statik :
menggunakan peta kode yang selalu sama. Metode
ini membutuhkan dua fase (two-pass): fase pertama untuk menghitung
probabilitas kemunculan tiap simbol/karakter dan menentukan peta kodenya, dan
fase kedua untuk mengubah pesan menjadi kumpulan kode yang akan ditransmisikan.
Contoh: algoritma Huffman statik.
(b) Metode dinamik (adaptif) :
menggunakan peta kode yang dapat berubah dari waktu
ke waktu. Metode ini disebut adaptif karena peta kode mampu beradaptasi
terhadap perubahan karakteristik isi file selama proses kompresi berlangsung.
Metode ini bersifat onepass, karena hanya diperlukan satu kali
pembacaan terhadap isi file. Contoh: algoritma LZW dan DMC.
Klasifikasi Teknik Kompresi
- Entropy
Encoding
Bersifat loseless
Tekniknya tidak
berdasarkan media dengan spesifikasi dan karakteristik tertentu namun
berdasarkan urutan data.
Statistical encoding, tidak memperhatikan semantik
data.
Mis: Run-length coding, Huffman coding, Arithmetic
coding
- 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
Secara umum kompresi data terdiri dari dua kegiatan
besar, yaitu Modeling dan Coding. Proses dasar dari kompresi data adalah
menentukan serangkaian bagian dari data (stream of symbols) mengubahnya menjadi
kode (stream of codes). Jika proses kompresi efektif maka hasil dari stream of
codes akan lebih kecil dari segi ukuran daripada stream of symbols. Keputusan
untuk mengindentikan symbols tertentu dengan codes tertentu adalah inti dari
proses modeling. Secara umum dapat diartikan bahwa sebuah model adalah kumpulan
data dan aturan yang menentukan pasangan antara symbol sebagai input dan code
sebagai output dari proses kompresi. Sedangkan coding adalah proses untuk
menerapkan modeling tersebut menjadi sebuah proses kompresi data.
I.Coding
Melakukan proses encoding dengan menggunakan ASCII
atau EBDIC yang merupakan standar dalam proses komputasi memberikan kelemahan
mendasar apabila dilihat dari paradigma kompresi data. ASCII dan EBDIC
menggunakan jumlah bit yang sama untuk setiap karakter, hal ini menyebabkan
banyak bit yang ”terbuang” untuk merepresentasikan karakter-karakter yang
sebenarnya jarang muncul pada sebuah pesan.
Salah satu cara mengatasi permasalahan di atas
adalah dengan menggunakan Huffman-coding. Huffman-coding yang dikembangkan oleh
D.A. Huffman mampu menekan jumlah redundancy yang terjadi pada sebuah pesan
yang panjangnya tetap. Huffman-coding bukanlah teknik yang paling optimal untuk
mengurangi redundancy tetapi Huffman-coding merupakan teknik terbaik untuk
melakukan coding terhadap symbol pada pesan yang panjangnya tetap. Permasalahan
utama dengan Huffman-coding adalah hanya bisa menggunakan bilangan bulat untuk
jumlah bit dari setiap code. Jika entropy dari karakter tersebut adalah 2,5
maka apabila melakukan pengkodean dengan Huffman-coding karakter tersebut harus
terdiri dari 2 atau 3 bit. Hal tersebut membuat Huffman-coding tidak bisa
menjadi algoritma paling optimal dalam mengatasi redundancy ini.
Huffman-coding memang kurang efisien karena untuk
melakukan pengkodean kita harus menggunakan bilangan bulat. Walaupun demikian
Huffman-coding sangat mudah digunakan dan sampai awal era 90-an di mana
prosesor komputer masih sulit untuk melakukan komputasi bilangan pecahan
Huffman-coding dianggap paling rasional untuk diaplikasikan pada proses
kompresi data. Setelah kelahiran prosesor yang mampu melakukan operasi bilangan
pecahan dengan cepat maka banyak algoritma coding baru bermunculan dan salah
satunya adalah Arithmatic-coding.
Arithmatic coding lebih kompleks dan rumit
dibandingkan Huffman-coding, tetapi di sisi lain Arithmatic-coding memberikan
optimalisasi yang lebih tinggi. Arithmatic-coding memungkinkan jumlah bit dalam
pecahan karena arithmatic coding tidak bekerja per karakter dari pesan tetapi
langsung pada keseluruhan pesan. Misalnya entropy dari karakter e pada pesan
adalah 1,5 bit maka pada output code pun jumlah bit-nya adalah 1,5 dan bukan 1
atau 2 seperti pada Huffman-coding.
ALGORITMA KOMPRESI DATA
Algoritma Shannon-Fano dan Algortima Huffman.
Walaupun saat ini sudah bukan lagi proses coding yang menghasilkan kompresi
paling optimal namun algoritma Shannon-Fano dan Algoritma Huffman adalah dua
algoritma dasar yang sebaiknya dipahami oleh mereka yang mempelajari tentang
kompresi data.
1.
Algoritma Shannon-Fano
Teknik coding ini dikembangkan oleh dua orang dalam
dua buah proses yang berbeda, yaitu Claude Shannon di Bell Laboratory dan R.M.
Fano di MIT, namun karena memiliki kemiripan maka akhirnya teknik ini dinamai
dengan mengggabungkan nama keduanya. Pada dasarnya proses coding dengan
algoritma ini membutuhkan data akan frekuensi jumlah kemunculan suatu karakter
pada sebuah pesan. Tiga prinsip utama yang mendasari algoritma ini adalah:
a. Simbol yang berbeda memiliki kode yang
berbeda
b. Kode untuk symbol yang sering muncul memiliki
jumlah bit yang lebih sedikit dan sebaliknya symbol yang jarang muncul
memiliki kode dengan jumlah bit lebih besar.
c. Walaupun berbeda jumlah bit-nya tetapi kode harus
tetap dikodekan secara pasti (tidak ambigu).
Berikut adalah langka-langkah Algoritma Shannon-Fano
:
1. Buatlah tabel yang memuat frekuensi kemunculan
dari tiap karakter.
2. Urutkan berdasar frekuensi tersebut dengan
karakter yang frekuensinya paling sering muncul berada di atas dari daftar
(descending).
3. Bagilah 2 tabel tersebut dengan jumlah total
frekuensi pada bagian atas mendekati jumlah total frekuensi pada bagian bawah
(lihat tabel 3).
4. Untuk bagian paro atas berikan kode 0 dan pada
paro bawah berikan kode
5. Ulangi langkah 3 dan 4 pada masing-masing paro
tadi hingga seluruh symbol selesai dikodekan.
2.
Algoritma Huffman
Algoritma Huffman memiliki kemiripan karakteristik
dengan Algoritma Shannon-Fano. Masing-masing simbol dikodekan dengan deretan
bit secara unik dan simbol yang paling sering muncul mendapatkan jumlah bit
yang paling pendek. Perbedaan dengan Shannon-Fano adalah pada proses
pengkodean. Jika algoritma Shannon-Fano membangun tree dengan pendekatan
top-down, yaitu dengan memberikan bit pada tiap-tiap simbol dan melakukannya
secara berurutan hingga seluruh leaf mendapatkan kode bit masing-masing.
Sedangkan algoritma Huffman sebaliknyamemberikan kode mulai dari leaf secara
berurutan hingga mencapai root.
Prosedur untuk membangun tree ini sederhana dan
mudah dipahami. Masing-masing simbol diurutkan sesuai frekuensinya, frekuensi
ini dianggap sebagai bobot dari tiap simbol, dan kemudian diikuti dengan
langkah-langkah sebagai berikut:
1. Dua node bebas dengan bobot terendah dipasangkan.
2. Parent node untuk kedua node pada langkah
sebelumnya dibuat. Jumlahkan frekuensi keduanya dan gunakan sebagai bobot.
3. Sekarang parent node berperan sebagai node bebas.
4. Berikan kode 0 untuk node kiri dan 1 untuk node
kanan.
5. Ulangi langkah di atas sampai hanya tersisa satu
node. Sisa satu node inilah yang disebut sebagai root.
II. Modeling
Jika coding adalah roda dari sebuah mobil maka
modeling adalah mesinnya. Sebaik apapun algoritma untuk melakukan coding tanpa
model yang baik kompresi data tidak akan pernah terwujud. Kompresi Data
Lossless pada umumnya diimplementasikan menggunakan salah satu dari dua tipe
modeling, yaitu statistical atau dictionary-based. Statistical-modeling
melakukan prosesnya menggunakan probabilitas kemunculan dari sebuah symbol
sedangkan dictionary-based menggunakan kode-kode untuk menggantikan sekumpulan
symbol.
1. Statistical Modeling
Pada bentuk paling sederhananya,
statistical-modeling menggunakan tabel statis yang berisi probabilitas
kemunculan suatu karakter atau symbol. Tabel ini pada awalnya bersifat
universal, sebagai contoh pada bahasa Inggris karakter yang paling sering
muncul adalah huruf “e” maka karakter ini memiliki 9 probabilitas tertinggi
pada file teks yang berbahasa Inggris.
Menggunakan tabel universal pada akhirnya tidak
memuaskan para ahli kopresi data karena apabila terjadi perubahan pada subyek yang
dikompresi dan tidak sesuai dengan tabel universal maka akan terjadi penurunan
rasio kompresi secara signifikan. Akhirnya muncul modeling dengan menggunakan
tabel yang adaptif, di mana tabel tidak lagi bersifat statis tetapi bisa
berubah sesuai dengan kode. Pada prinsipnya dengan model ini, sistem melakukan
penghitungan atau scan pada keseluruhan data setelah itu barulah membangun
tabel probabilitas kemunculan dari tiap karakter atau symbol.
Model ini kemudian dikembangkan lagi menjadi
adaptive statistical modeling di mana sistem tidak perlu melakukan scan ke
seluruh symbol untuk membangun tabel statistik, tetapi secara adaptif melakukan
perubahan tabel pada proses scan karakter per karakter.
2. Dictionary Based Modeling
Jika statistical model pada umumnya melakukan proses
encode simbol satu per satu mengikuti siklus: baca karakter à
hitung probabilitas à buat kodenya maka dictionary-based
modeling menggunakan mekanisme yang berbeda. Dictionary-based modeling membaca
input data dan membandingkannya dengan isi dictionary. Jika sekumpulan string
sesuai dengan isi dictionary maka indeks dari dictionary entry lah yang
dikeluarkan sebagai output dan bukan kodenya. Sebagai perumpamaan dari
dictionary-based dapat digunakan makalah ilmiah sebagai contoh. Saat kita
membaca makalah ilmiah kita sering membaca nomor-nomor referensi yang bisa kita
cocokkan dengan daftar pustaka di belakang. Hal ini mirip dengan proses pada
dictionary-based modeling.
PERBANDINGAN ALGORITMA PADA KOMPRESI
DATA
Symbol
|
Jumlah
|
Kode
Shannon
Fano
|
Kode
Huffman
|
Ukuran
Shannon-
Fano
|
Jumlah
Bit
Shannon-
Fano
|
Ukuran
Hufman
|
Jumlah
Bit
Huffman
|
A
|
15
|
00
|
0
|
2
|
30
|
1
|
15
|
B
|
7
|
01
|
100
|
2
|
14
|
3
|
21
|
C
|
6
|
10
|
101
|
2
|
12
|
3
|
18
|
D
|
6
|
110
|
110
|
3
|
18
|
3
|
18
|
E
|
5
|
111
|
111
|
3
|
15
|
3
|
15
|
TOTAL BIT
|
89
|
87
|
KESIMPULAN
Berdasarkan penjelasan di atas, kita dapat
menyimpulkan bahwa Kompresi Data dapat mempermudahkan dalam hal penyimpanan
file yang begitu besar. Dan media penyimpanan kita bisa menampung data
sebanyak- banyaknya.
REFERENSI
Nelson, M., Gailly, J.L., The Data Compression Book,
Second Edition. M&T Books, New
York, 1996
www.google.com
0 komentar:
Posting Komentar