kompresi data - intanparlina.files.wordpress.com · hasil kompresi mirip dengan sinyal ......
TRANSCRIPT
Kompresi Data
KONSEP
Tujuan Kompresi:
Mengurangi ukuran file
Hasil kompresi mirip dengan sinyal (file) asli
Algoritma kompresi dapat di implementasi dengan mudah
Handal/ tidak mudah berubah (robust)
KOMPRESI DATA
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”
Syarat:
Pengiriman data hasil kompresi dapat dilakukan jika
pihak pengirim / yang melakukan kompresi dan pihak
penerima memiliki aturan yang sama dalam hal
kompresi data.
KOMPRESI DATA
Pihak pengirim harus menggunakan algoritma
kompresi (di-kode-kan) 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.
KOMPRESI DATA
Teknik kompresi bisa dilakukan terhadap data:
teks,
audio (MP3),
gambar (JPEG),
video (MPEG)
JENIS KOMPRESI DATA
Metode
Lossy format : ada bagian yang dihilangkan
Loseless format : tidak ada bagian yang hilang
JENIS KOMPRESI DATA
Lossy Compression
Teknik kompresi dimana data hasil dekompresi
tidak sama dengan data sebelum kompresi namun
sudah ”cukup” untuk digunakan.
ada bagian yang dihilangkan
Contoh: MP3, JPEG, MPEG.
Kelebihan: ukuran file jauh lebih kecil dibandingkan
aslinya, namun masih memenuhi syarat untuk
digunakan (informasi utama tidak hilang).
JENIS KOMPRESI DATA
Biasanya teknik kompresi dengan metode Lossy:
membuang bagian-bagian data yang sebenarnya
tidak begitu berguna, tidak begitu dirasakan, tidak
begitu dirasa oleh indera manusia sehingga
manusia masih beranggapan bahwa data tersebut
masih bisa digunakan walaupun sudah dikompresi.
JENIS KOMPRESI DATA
Loseless Compression
Teknik kompresi dimana ketika data hasil kompresi, dilakukan dekompres lagi maka hasilnya tepat sama seperti data sebelum proses kompresi.
Teknik ini digunakan jika diperlukan data yang setelah dikompresi harus dapat diekstrak/ di-dekompres lagi, harus tepat sama.
KRITERIA ALGORITMA DAN APLIKASI
KOMPRESI DATA
Kualitas data hasil enkoding: ukuran lebih kecil,
data tidak rusak (kompresi lossy)
Ketepatan proses dekompresi data: data hasil
dekompresi tetap sama dengan data sebelum
dikompres (kompresi loseless)
Kecepatan, ratio, dan efisiensi proses kompresi –
dekompresi
Teknik Kompresi Teks
CONTOH-CONTOH TEKNIK KOMPRESI TEKS
Run-Length-Encoding (RLE)
Kompresi data teks dilakukan jika ada beberapa
huruf yang sama ditampilkan berturut-turut:
Misalnya:
Data:
ABCCCCCCCCDEFGGGG = 17 karakter
RLE tipe 1 (min. 4 huruf sama) :
ABC!8DEFG!4 = 11 karakter
Best case:
untuk RLE adalah ketika terdapat 127 karakter
yang sama sehingga akan dikompres menjadi 2
byte saja.
Worst case:
untuk RLE adalah ketika terdapat 127 karakter
yang berbeda semua, maka akan terdapat 1 byte
tambahan sebagai tanda jumlah karakter yang tidak
sama tersebut.
CONTOH-CONTOH TEKNIK KOMPRESI TEKS
Algoritma Lempel-Ziv-Welch (LZW)
Menggunakan teknik yang berbasiskan “kamus”
Pendahulu LZW adalah LZ-77 dan LZ-78 yang
dikembangkan oleh Jacob Ziv dan Abraham Lempel pada
tahun 1977 dan 1978.
Terry Welch mengembangkan teknik tersebut pada tahun
1984.
LZW banyak dipergunakan pada UNIX, GIF, modem V.42
CONTOH-CONTOH TEKNIK KOMPRESI TEKS
Shannon-Fano Algorithm
Dikembangkan oleh Shannon (Bell Labs) dan Robert
Fano (MIT)
Contoh :
H E L L O
Simbol H E L O
Jumlah 1 1 2 1
CONTOH-CONTOH TEKNIK KOMPRESI TEKS
CONTOH-CONTOH TEKNIK KOMPRESI TEKS
Misalnya:
MAMA SAYA
Total = 8 karakter
Frekuensi karakter dari string yang akan dikompres
dianalisa terlebih dahulu.
A = 4 4/8 = 0.5
M = 2 2/8 = 0.25
S = 1 1/8 = 0.125
Y = 1 1/8 = 0.125
HUFFMAN TREE
CONTOH-CONTOH TEKNIK KOMPRESI TEKS
HUFFMAN TREE
p(Y)=0.125 p(S)=0.125
p(YS)=0.25 p(M)=0.25
p(YSM)=0.5 p(A)=0.5
p(YSMA)=1
0
01
0
1
1
Selanjutnya dibuat pohon huffman yang merupakan pohon biner
CONTOH-CONTOH TEKNIK KOMPRESI TEKS
TEKNIK KOMPRESI AUDIO
KOMPRESI AUDIO MP3
Asal-usul MP3 dimulai dari penelitian IIS-FHG (Institut
Integriette Schaltungen-Fraunhofer Gesellschaft), sebuah
lembaga penelitian terapan di Munich, Jerman dalam
penelitian coding audio perceptual. (1991)
Penelitian tersebut menghasilkan suatu algoritma yang
menjadi standard sebagai ISO-MPEG Audio Layer-3
(MP3)
TABEL KOMPRESI AUDIO MP3
Tabel kemampuan kompresi MPEG Layer 3 dengan kualitas suara yang dihasilkan
Fungsi masing-masing lapisan adalah sebagai berikut:
Lapisan 1: fungsi dari lapisan ini adalah melakukan penyaringan dengan Model DCT dan melakukan pengelompokan terhadap sinyal yang mempunyai bandwidth yang sama
Lapisan 2 dan 3: membuat critical band yang paling baik untuk frekuensi yang tidak sama dengan menggunakan model psychoacoustic yang didalamnya terdapat efek masking, dan kemudian menggunakan Huffman coder
TEKNIK KOMPRESI MP3 (1)
Critical band :
merupakan daerah frekuensi tertentu dimana pendengaran manusia lebih peka pada frekuensi-frekuensi rendah, sehingga alokasi bit dan alokasi sub-band pada filter critical band lebih banyak dibandingkan frekuensi lebih tinggi.
TEKNIK KOMPRESI MP3 (2)
Model Psikoakustik
Karakteristik dari MP3 yang memanfaatkan kelemahan pendengaran manusia.
Model yang menggambarkan karakteristik pendengaran manusia.
Salah satu karakteristik pendengaran manusia adalah memiliki batas frekuensi 20 Hz ... 20 kHz, dimana suara yang memiliki frekuensi yang berada di luar ambang batas ini tidak dapat didengar oleh manusia, sehingga suara seperti itu tidak perlu dikodekan.
TEKNIK KOMPRESI MP3 (3)
Auditory Masking :
Manusia tidak mampu mendengarkan suara pada suatu
frekuensi dengan amplitudo tertentu jika pada frekuensi
di dekatnya terdapat suara dengan amplitudo yang jauh
lebih tinggi.
TEKNIK KOMPRESI GAMBAR
MODEL WARNA
Model yang digunakan untuk menentukan warna dalam
komputer adalah:
RGB model - Metodologi 24-bit di mana warna ditetapkan dalam
hal nilai merah, hijau, dan biru mulai dari 0 hingga 255
HSB /HSL dan HSV model - Warna ditentukan sebagai sudut 0-
360 derajat pada roda warna
CMYK (untuk media cetak/tinta)
YIQ (NTSCUS, Japan),
YUV (PALAustralia, Europe),
xvYCC (YCbCr/YPbPr +RGB)
CIE (International Commision Illumination, France, 1931)
≈ KOMPRESI GAMBAR (JPEG)
SPATIAL REDUNDANCY REDUCTION
Run-
length
coding
Quantization• major reduction
• controls „quality‟
YUV
YCRCB
TEKNIK KOMPRESI VIDEO
???
APLIKASI KOMPRESI
ZIP File Format
Ditemukan oleh Phil Katz untuk program PKZIP
kemudian dikembangkan untuk WinZip
Berekstensi *.ZIP
Dapat menggabungkan dan mengkompresi
beberapa file sekaligus menggunakan bermacam-
macam algoritma, namun paling umum
menggunakan Katz’s Deflate Algorithm.
APLIKASI KOMPRESI
Beberapa method Zip:
Deflate : menggunakan LZW
Shrinking : merupakan metode variasi dari LZW
Reducing : merupakan metode yang mengkombinasikan
metode same byte sequence based dan probability based
encoding.
Imploding : menggunakan metode byte sequence based
dan Shannon-Fano encoding.
Bzip2
Aplikasi: WinZip oleh Nico-Mak Computing
APLIKASI KOMPRESI
RAR File Format
Ditemukan oleh Eugene Roshal,
sehingga RAR merupakan singkatan dari Roshal
Archive pada 10 Maret 1972 di Rusia.
Berekstensi *.RAR
Proses kompresi lebih lambat dari ZIP tapi ukuran file
hasil kompresi lebih kecil.
Aplikasi: WinRAR yang mampu menangani RAR dan
ZIP, mendukung volume split, enkripsi AES.