BAB II
PEMBAHASAN
2.1 Penfertian 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)
2.2 Jenis Kompresi Data
A. 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
B. 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.
2.3 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.
2.4 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
hitungàencode
simbol satu per satu mengikuti siklus: baca karakter buat kodenya maka dictionary-based modeling
menggunakanàprobabilitas 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.
