PENGERTIAN KOMPRESI DAN DEKOMPRESI

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 p_i = nilai probabilitas S_i  

                                       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)

            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

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*….

                                                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:

1. 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.
2. 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. 

3. 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.