10/3/2011
1
Kompresi Bahan Kuliah : Sistem Multimedia PS TI – Undip Gasal 2011/2012
2
Definisi Kompresi • Memampatkan/mengecilkan ukuran • Proses mengkodekan informasi menggunakan bit yang lain yang lebih rendah daripada representasi data yang tidak terkodekan dengan suatu sistem enkoding (penyandian) tertentu. • Contoh kompresi p sederhana yyang g biasa kita lakukan misalnya adalah menyingkat kata-kata yang sering digunakan tapi sudah memiliki konvensi umum. Misalnya: kata “yang” dikompres menjadi kata “yg”.
1
10/3/2011
3
Aturan Kompresi • Pengiriman g data hasil kompresi p dapat p dilakukan jika pihak pengirim (yang melakukan kompresi) dan pihak penerima (yang melakukan dekompresi) 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
4
Keuntungan Kompresi • Kompresi p data menjadi j sangat g p penting g karena memperkecil kebutuhan penyimpanan data, mempercepat pengiriman data, memperkecil kebutuhan lebar-bidang (bandwidth). • Teknik kompresi bisa dilakukan terhadap data teks/biner (zip), gambar (JPEG, PNG, TIFF), audio (MP3, AAC, RMA, WMA), dan video (MPEG, H261, H263).
2
10/3/2011
5
Metode Kompresi Data
6
Jenis Kompresi • Lossyy Compression p (Kompresi Berugi)
• Lossless Compression (Kompresi Tak-Berugi)
3
10/3/2011
7
Lossy Compression • Teknik kompresi dimana data hasil dekompresi tidak sama dengan data sebelum kompresi namun sudah “cukup” untuk digunakan. • Membuang bagian-bagian data yang tidak begitu berguna, tidak begitu dirasakan, tidak begitu dilihat oleh manusia Æ masih beranggapan g bahwa data masih bisa digunakan. • Kelebihan: ukuran file lebih kecil dibanding loseless namun masih tetap memenuhi syarat untuk digunakan.
8
• Contoh : MP3, streaming media, JPEG, MPEG, d WMA dan • Image asli berukuran 12,249 bytes, kompresi JPEG kualitas 30 dan berukuran 1,869 bytes Æ image 85% lebih kecil dan ratio kompresi 15%.
4
10/3/2011
9
Lossless Compression • Teknik kompresi p dimana data hasil kompresi p dapat didekompres lagi dan hasilnya tepat sama seperti data sebelum proses kompresi. • Contoh aplikasi: ZIP, RAR, GZIP, 7-Zip, beberapa image seperti GIF dan PNG
10
Kriteria Kompresi • Kualitas data hasil enkoding : ukuran lebih kecil, d t tidak data tid k rusak k untuk t k kompresi k i lossy. l • Kecepatan, ratio, dan efisiensi proses kompresi dan dekompresi •K Ketepatan t t proses dekompresi d k i data: d t d data t hasil h il dekompresi tetap sama dengan data sebelum dikompres (kompresi loseless)
5
10/3/2011
11
Teknik Kompresi • • • •
Run-Length-Encoding g g ((RLE)) Static Huffman Coding Shannon-Fano Algorithm Dictionary-based Coding : LZW (Lempel, Ziv, and Welch)
12
RLE (Run-Length-Encoding) • Kompresi data teks dilakukan jika ada beberapa huruf yang sama yang ditampilkan berturutturut ▫ Contoh ABCCCCCCCCDEFGGGG = 17 karakter ▫ RLE tipe 1 (min. 4 huruf sama) : ABC!8DEFG!4 = 11 karakter
• RLE ada yang menggunakan suatu karakter yang tidak digunakan dalam teks tersebut seperti misalnya ‘!’ untuk menandai. • Kelemahan? Jika ada karakter angka, mana tanda mulai dan akhir?
6
10/3/2011
13
• Misal data : ABCCCCCCCCDEFGGGG = 17 karakter • RLE tipe 2: -2AB8C-3DEF4G = 12 karakter • Misal data : AB12CCCCDEEEF = 13 karakter • RLE tipe 2: -4AB124CD3EF = 12 karakter • RLE ada yang menggunakan flag bilangan negatif untuk menandai batas sebanyak jumlah karakter tersebut.
14
• Berguna untuk data yang banyak memiliki kesamaan, misal teks ataupun grafik seperti icon atau gambar garis garisgaris yang banyak memiliki kesamaan pola. • Best case: untuk RLE tipe 2 adalah ketika terdapat 127 karakter yang sama sehingga akan dikompres menjadi 2 byte saja. • Worst case: untuk RLE tipe 2 adalah ketika terdapat 127 k kt yang berbeda karakter b b d semua, maka k akan k terdapat t d t 1 byte b t tambahan sebagai tanda jumlah karakter yang tidak sama tersebut. • Menggunakan teknik loseless
7
10/3/2011
15
• Contoh untuk data image:
16
Static Huffman Coding • Frekuensi karakter dari string yang akan dik dikompres di dianalisis li i terlebih l bih dahulu. d h l Selanjutnya dibuat pohon huffman yang merupakan pohon biner dengan root awal yang diberi nilai 0 (sebelah kiri) atau 1 (sebelah kanan), sedangkan selanjutnya untuk dahan kiri selalu diberi nilai 1(kiri) 0(kanan) dan di dahan kanan diberi nilai 0(kiri) – 1(kanan)
8
10/3/2011
17
• A bottom-up approach = frekuensi terkecil dikerjakan terlebih dahulu dan diletakkan ke dalam leaf(daun). • Kemudian leaf-leaf akan dikombinasikan dan dijumlahkan probabilitasnya menjadi root di atasnya.
18
Teks : “MAMA SAYA” A = 4 -> 4/8 = 0.5 M = 2 -> 2/8 = 0.25 S = 1 -> 1/8 = 0.125 Y = 1 -> > 1/8 = 0.125 0 125 : 8 karakter
Contoh Huffman
1
9
10/3/2011
19
Huffman : "this is a test" Karakter t s (spasi) i e h a
Frekuensi 3 3 3 2 1 1 1
20
Encoding
10
10/3/2011
21
Shannon-Fano Algorithm • Dikembangkan oleh Shannon (Bell Labs) dan R b t Fano Robert F (MIT) • Contoh : “H E L L O”
22
Algoritma : 1 Urutkan simbol berdasarkan frekuensi 1. kemunculannya 2. Bagi simbol menjadi 2 bagian secara rekursif, dengan jumlah yang kira-kira sama pada kedua bagian, sampai tiap bagian hanya terdiri dari 1 simbol. • Cara yang paling li tepat untuk k mengimplementasikan adalah dengan membuat binary tree.
11
10/3/2011
23
24
12
10/3/2011
25
LZW (Lempel-Ziv-Welch) • Menggunakan gg teknik adaptif p dan berbasiskan “kamus”. • Pendahulu LZW adalah LZ77 dan LZ78 yang dikembangkan oleh Jacob Ziv dan Abraham Lempel pada tahun 1977 dan 1978. • Terry Welch mengembangkan teknik tersebut pada tahun 1984. 1984 • LZW banyak dipergunakan pada UNIX, GIF, V.42 untuk modem
26
Algoritma Kompressi LZW BEGIN s = next input character; while not EOF { c = next input character; if s + c exists in the diactionary s=s+c else { Output the code for s; Add string s + c to the dictionary with a new code s = c; } } END
13
10/3/2011
27
Contoh Kompresi LZW Code String 1 2 3
A B C
28
Data : ABABBABCABABBA
14
10/3/2011
29
Algoritma Dekompresi BEGIN S = NULL;; while not EOF{ K = NEXT INPUT CODE; Entry = dictionary entry for K; Ouput entry; if(s != NULL) add string s + entry[0] to dictionary with new code S = Entry; } END
30
Dekompresi : 124523461
Output : ABABBABCABABBA
15
10/3/2011
31
Aplikasi Kompresi • ZIP File Format ▫ Ditemukan oleh Phil Katz untuk program PKZIP kemudian dikembangkan untuk WinZip, WinRAR, 7-Zip. ▫ Berekstensi *.zip dan MIME application/zip ▫ Dapat menggabungkan dan mengkompresi b b beberapa fil sekaligus file k li menggunakan k bermacamb macam algoritma.
32
Aplikasi Kompresi • Method Zip ▫ 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 Shannon-Fano Fano encoding. encoding ▫ Deflate : menggunakan LZW
16
10/3/2011
33
Aplikasi Kompresi • Oleh Eugene Roshal, pada 10 Maret 1972 di Rusia • RAR Æ Roshal Archive. • Berekstensi .rar dan MIME (Multipurpose Internet Mail Extensions-MIME) application/xrar-compressed • Proses kompresi lebih lambat dari ZIP tapi p lebih kecil. ukuran file hasil kompresi • Aplikasi: WinRAR yang mampu menangani RAR dan ZIP, mendukung volume split, enkripsi AES.
34
• Ada pertanyaan?? • .. • ..
17
