Pengertian Kompresi dan Dekompresi
Kompresi data (data compression) adalah
sebuah proses yang mengubah streamdata input menjadi stream data output dengan
ukuran yang lebih kecil.
dekompresi (decompression)
adalah Proses pembalian data yang sudah dikompres menjadi data seperti semula.
Aturan Kompresi
Pengiriman data hasil kompresi dapat
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
Aplikasi: WinRAR yang mampu menangani
RAR dan ZIP, mendukung volume split, enk
Dasar-dasar teknik kompresi
Sumber kompresi adalah lossy, yang
berarti terjadi beberapa bagian komponen dari data yang hilang akibat dari
proses kompresi.
Kompresi entropy adalah lossless, yang
berarti tidak ada data yang hilang selama proses kompresi (huffman coding).
Hybrid merupakan kombinasi lossy dan
lossless
Kompresi entropy adalah media yg bebas
mengambil secara urutan data per bit (byte stream)
Huffman coding adalah contoh yg
menggunakan teknik kompresi entropy.
Entropy yang berasal dari sumber
informasi menurut Shannon :
Dimana pi = nilai
probabilitas Si
mengindikasikan adanya jumlah
informasi yg terdapat di Si, yaitu banyak bit yg diperlukan untuk dikodekan mjd
Si
contoh
: tingkat intensitas gray, pi = 1/256 shg jumlah bit yg diperlukan untuk
mengkodekan tingkatan masing gray adalah 8 bit. Entropy dari gambar tersebut
adalah 8 bit.
Diagram alir pemrosesan kompresi
Teknik Entropy Encoding
- Run-length Encodin
- Repetition Suppression
- Pattern Substitution
- Huffman Coding
Keuntungan Kompresi
Kompresi data menjadi sangat penting
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).
http://en.wikipedia.org/wiki/Audio_codec
Jenis Kompresi
Lossy Compression
(Kompresi Berugi)
Lossless Compression
(Kompresi Tak-Berugi)
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 bahwa data masih
bisa digunakan.
Kelebihan: ukuran file lebih kecil
dibanding loseless namun masih tetap memenuhi syarat untuk digunakan.
Contoh: MP3, streaming media, JPEG, MPEG, dan
WMA
Image asli berukuran 12,249 bytes,
kompresi JPEG kualitas 30 dan berukuran 1,869 bytes à image 85% lebih kecil dan ratio
kompresi 15%.
Lossless Compression
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,
beberapa image seperti GIF dan PNG
Kriteria Kompresi
Kualitas data hasil enkoding: ukuran
lebih kecil, data tidak rusak untuk kompresi lossy.
Kecepatan, ratio, dan efisiensi proses
kompresi dan dekompresi
Ketepatan proses dekompresi data: data
hasil dekompresi tetap sama dengan data sebelum dikompres (kompresi loseless)
Teknik Kompresi
Kompresi teks : RLE, kode huffman statik
Kompresi gambar : JPEG, PNG, BMP, TIF,
dan JPEG 2000
Kompresi video : H261, H262, dan MPEG
RLE (Run-Length-Encoding)
Kompresi data teks dilakukan jika ada
beberapa huruf yang sama yang ditampilkan berturut-turut
Contoh ABCCCCCCCCDEFGGGG = 17 karakter
RLE tipe 1 (min. 4 huruf sama) :
ABC!8DEFG!4 = 11 karakter
Run-length Encoding
Beberapa elemen angka yang sama
diwakilkan dengan satu buah elemen angka yang diberikan jumlahnya
contoh:
111333322222211111 Þ (1,3),(3,4),(2,6),(1,5)
111333322222211111 Þ (1,3),(3,4),(2,6),(1,5)
atau
dengan contoh yang lain
10000001
dikompresi menjadi 10!61
Repetition Suppression
Mengubah angka atau hurup yang
berulang-ulang diwakilkan dengan satu hurup dengan jumlahnya
Example:
984000000000000000000000000 = 984A24
984000000000000000000000000 = 984A24
Pattern Substitution
Melakukan subtitusi kata-kata menjadi
hurup maupun simbol
contoh:
This book is an exemplary example of a book….
This Þ 1、is Þ2、an Þ3、of Þ4、a Þ5
book Þb*….
This book is an exemplary example of a book….
This Þ 1、is Þ2、an Þ3、of Þ4、a Þ5
book Þb*….
1b*23exemplary
example45b*
Pattern Substitution
This book is an exemplary example of a book
on multimedia and networking. Nowhere else will you find this kind of coverage
and completeness. This is truly a one-stop-shop for all that you want to know
about multimedia and networking.
a:1, about:2, all:3, an:4, and:5, for:6,
is:7, of:8, on:9, that:+, this:&, to:=, will:#
& b o o k 7 4 e x
e m p l a
r y sp
e x a
m p l
e 81 b
o o k
9 m* 5
n* . N
o w h
e r e
sp e l
s e # y o…
129 : 193 = 0.6684 à 33.16% compression
Huffman Coding
Berdasarkan frekuensi kejadian pada
karakter yang diberikan
A:13, B:4, C:7 Þ A®1,
B ®00,
C ®01
Pemampatan Data dengan Algoritma Huffman
Prinsip
kode Huffman:
-
karakter yang paling sering muncul di
dalam data dengan kode yang lebih
pendek;
-
sedangkan karakter yang relatif jarang
muncul dikodekan dengan kode yang
lebih panjang.
Fixed-length code
Karakter
a
b c d e f
----------------------------------------------------------------
Frekuensi 45% 13%
12% 16% 9%
5%
Kode 000 001
010 011 100
111
‘bad’ dikodekan sebagai ‘001000011’
Pengkodean
100.000 karakter membutuhkan 300.000 bit.
Variable-length code (Huffman code)
Karakter
a
b c d e
f
------------------------------------------------------------------------
Frekuensi 45% 13%
12% 16% 9%
5%
Kode 0 101
100 111 1101
1100
‘bad’ dikodekan sebagai ‘1010111 ’
Pengkodean 100.000 karakter membutuhkan
(0,45 ´
1 + 0,13 ´
3 + 0,12 ´
3 + 0,16 ´
3 +
0,09 ´
4 + 0,05 ´
4) ´
100.000 = 224.000 bit
Nisbah pemampatan:
(300.000 – 224.000)/300.000 ´
100% = 25,3%
Algoritma
Greedy untuk Membentuk Kode Huffman:
- Baca semua karakter di dalam data untuk menghitung frekuensi kemunculan setiap karakter. Setiap karakter penyusun data dinyatakan sebagai pohon bersimpul tunggal. Setiap simpul di-assign dengan frekuensi kemunculan karakter tersebut.
- Terapkan strategi greedy sebagai berikut: gabungkan dua buah pohon yang mempunyai frekuensi terkecil pada sebuah akar. Akar mempunyai frekuensi yang merupakan jumlah dari frekuensi dua buah pohon penyusunnya.
- Ulangi langkah 2 sampai hanya tersisa satu buah pohon Huffman.
Kompleksitas algoritma Huffman: O(n
log n) untuk n karakter.
Contoh:
Karakter a b c d e f
-------------------------------------------------------Frekuensi 45 13 12 16 9 5
Huffman Coding
Static Huffman Coding
Frekuensi karakter dari string yang akan
dikompres dianalisis
terlebih dahulu. 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)
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.
Proses Encoding
LZW (Lempel-Ziv-Welch)
Menggunakan teknik adaptif 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.
LZW banyak dipergunakan pada UNIX, GIF,
V.42 untuk modem
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
Contoh Kompresi LZW
Data : ABABBABCABABBA
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
Dekompresi : 124523461
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
beberapa file sekaligus menggunakan bermacam-macam algoritma.
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-Fano encoding.
Deflate : menggunakan LZW
Aplikasi Kompresi
Oleh Eugene Roshal, pada 10 Maret 1972
di Rusia
RAR à Roshal Archive.
Berekstensi .rar dan MIME (Multipurpose
Internet Mail Extensions-MIME) application/x-rar-compressed
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.
Tidak ada komentar:
Posting Komentar