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 teknik kompresi :
Terdapat berbagai macam teknik teknik kompresi yang diantaranya akan dijelaskan berikut ini.
1. huffman coding
Pada tahun 1951, David A. Huffman dalam kelas Informasi Teori di MIT diberikan pilihan untuk
membuat sebuah term paper atau mengikuti ujian akhir. Pada saat itu pilihan term paper yang diberikan
profesor Robert M. Fano adalah tentang menemukan kode biner yang paling efisien. Tidak dapat membuktikan kode apapun yang paling efisien, Huffman hampir menyerah dan mulai belajar untuk
mengikuti ujian akhir saja, ketika ia menemukan ide untuk menggunakan pohon biner dengan pengurutan berdasarkan kekerapan dan berhasil membuktikan bahwa cara ini adalah yang paling efisien.
Apa yang dilakukan Huffman melampaui profesornya sendiri, yang bekerja sama dengan pencipta bidang teori informasi Claude Shannon mengembangkan kode yang mirip. Huffman menghindari kesalahan besar dari kode Shannon-Fano yang kurang optimal dengan membangun pohon binernya dari bawah ke atas dan bukan dari atas ke. Makalah berjudul “A Method for the Construction of Minimum Redundancy Codes” tersebut lalu dipublikasikan oleh Huffman pada tahun 1952 dalam sebuah jurnal profesional untuk Institute of Radio Engineers.
CONTOH :
Terdapat sumber lima lambang dengan kemungkinan 0.3, 0.2, 0.2, 0.2, 0.1.
Entropy dari sumber ini adalah H = −[0.3 log 0.3 + (3 × 0.2) log 0.2 + 0.1 log 0.1] = 2.246.
Terdapat dua phase dalam menyusun kode huffman yaitu :
a). reduction phase
merupakan phase pengurangan, dimana bila terdapat beberapa simbol kemudian 2 simbol yang memiliki probabilitas paling kecil digabungkan menjadi satu simbol dengan probabilitas sama dengan jumlah probabilitas dari kedua simbol tersebut. Simbol hasil reduksi kemudian diperlakukan seperti simbol yang lain dan dilakukan reduksi lagi hingga mendapatkan 2 buah simbol dengan probabilitas yang tinggi.
Contoh
Terdapat beberapa simbol dengan peluang :
S1 = 0.3, S2 = 0.2, S3 = 0.2, S4 = 0.2, S5 = 0.1
Jika dilakukan reduction phase maka :
S1 = 0.3, S2 = 0.3, S3 = 0.2, S4 = 0.2
Kemudian
S1 = 0.4, S2 = 0.3, S3 = 0.3
Dan
S1 = 0.6, S2 = 0.4
Gambar diagramnya seperti berikut ini :
b). splitting phase
Merupakan phase pembalikan dari reductions phase. Dua simbol dengan probabilitas tinggi hasil reductions phase direpresentasikan kedalam satu komponen dengan code 1 dan O. Kemudian ambil mundur simbol sebelumnya dan representasikan kedalam dua komponen dengan code 00, 01, 10 dan 11. Begitu seterusnya hingga semua simbol sebelum direduksi telah direpesentasikan kedalam code.
Contoh
Hasil splitting phase dari simbol simbol diatas :
0.6 = 0, 0.4 = 1
Kemudian
0.4 = 1, 0.3 = 00, 0.3 = 01
Kemudian
0.3 = 00, 0.3 = 01, 0.2 = 10, 0.2 = 11
Dan
0.3 = 00, 0.2 = 10, 0.2 = 11, 0.2 = 0.10, 0.1 = 011
Gambar diagramnya seperti berikut ini :
Dengan panjang rata rata nya (L)
L = (2 × 0.3) + (2 × 0.2) + (2 × 0.2) + (3 × 0.2) + (3 ×0 .1) = 2.3
Representasi dari Huffman Code tree contoh diatas adalah :
2. Lemvel Ziv Coding
Algoritma LZW dikembangkan dari metode kompresi yang dibuat oleh Ziv dan Lempel pada tahun 1977. Algoritma ini melakukan kompresi dengan menggunakan dictionary, di mana fragmen-fragmen teks digantikan dengan indeks yang diperoleh dari sebuah “kamus”. Prinsip sejenis juga digunakan dalam kode Braille, di mana kode-kode khusus digunakan untuk merepresentasikan kata-kata yang ada. Pendekatan ini bersifat adaptif dan efektif karena banyak karakter dapat dikodekan dengan mengacu pada string yang telah muncul sebelumnya dalam teks. Prinsip kompresi tercapai jika referensi dalam bentuk pointer dapat disimpan dalam jumlah bit yang lebih sedikit dibandingkan string aslinya. Algoritmanya sebagai berikut:
1. Dictionary diinisialisasi dengan semua karakter dasar yang ada :
2. P = karakter pertama dalam stream karakter.
3. C = karakter berikutnya dalam stream karakter.
4. Apakah string (P + C) terdapat dalam dictionary ?
Jika ya, maka P = P + C (gabungkan P dan C menjadi string baru).
Jika tidak, maka :
- Output sebuah kode untuk menggantikan string P.
- Tambahkan string (P + C) ke dalam dictionary dan berikan nomor/kode berikutnya yang belum digunakan dalam dictionary untuk string tersebut.
- P = C.
5. Apakah masih ada karakter berikutnya dalam stream karakter ?
Jika ya, maka kembali ke langkah 2.
Jika tidak, maka output kode yang menggantikan string P, lalu terminasi proses (stop).
Proses dekompresi pada LZW dilakukan dengan prinsip yang sama seperti proses kompresi. Pada awalnya, dictionary diinisialisasi dengan semua karakter dasar yang ada. Lalu pada setiap langkah, kode dibaca satu per satu dari stream kode, dikeluarkan string dari dictionary yang berkorespondensi dengan kode tersebut, dan ditambahkan string baru ke
dalam dictionary. Metode LZW yang diterapkan dalam penelitian ini bertipe dinamik, dimana hanya dilakukan satu kali pembacaan (one-pass) terhadap file yang akan dikompresi. Pengkodean data dilakukan secara on the fly, bersamaan dengan proses penambahan string baru ke dalam dictionary. Algoritma dekompresinya sebagai berikut:
1. Dictionary diinisialisasi dengan semua karakter dasar yang ada :
2. CW = kode pertama dari stream kode (menunjuk ke salah satu karakter dasar).
3. Lihat dictionary dan output string dari kode tersebut (string.CW) ke stream karakter.
4. PW = CW; CW = kode berikutnya dari stream kode.
5. Apakah string.CW terdapat dalam dictionary ?
Jika ada, maka :
- output string.CW ke stream karakter
- P= string.PW
- C = karakter pertama dari string.CW
- tambahkan string (P+C) ke dalam dictionary
Jika tidak, maka :
- P =string.PW
- C = karakter pertama dari string.PW
- output string (P+C) ke stream karakter dan tambahkan string tersebut ke dalam dictionary (sekarang berkorespondensi dengan CW);
6. Apakah terdapat kode lagi di stream kode ?
Jika ya, maka kembali ke langkah 4.
Jika tidak, maka terminasi proses (stop).
References :
http://budiastika.blogspot.com/2008/07/kompresi-pada-citra-digital-dengan.html
3. Run length Encoding
Merupakan kompresi data teks yang dilakukan jika terdapat beberapa huruf yang sama ditampilkan secara berturut-turut. Terdapat dua tipe RLE yaitu RLE tipe 1 dan RLE tipe 2.
Contoh :
Data; ABCCCCCCCCDEFGGGG = 17 karakter
Dengan RLE tipe 1 (min. 4 huruf sama) ditulis; ABC8!DEFG!4 = 11 karakter
Dalam RLE tipe 1 ini terdapat suatu karakter yang tidak digunakan dalam teks seperti tanda ‘!’ yang digunakan untuk menandai. Teknik kompresi RLE tipe 1 ini memiliki kelemahan yaitu jika terdapat karakter angka, mana tanda mulai dan tanda akhir? Maka dalam RLE tipe 2 digunakanlah flag bilangan negatif untuk menandai batas sebanyak jumlah karakter tersebut.
Contoh:
Data; ABCCCCCCCCDEFGGGG = 17 Karakter
Dengan RLE tipe 2; -2AB8CDEF4G = 12 Karakter
Contoh:
Data; AB12CCCCDEEEF = 13 Karakter
Dengan RLE tipe 2; -4AB124CD3EF = 12 Karakter
Teknik kompresi dengan RLE ini berguna untuk data yang banyak memiliki kesamaan, misal teks ataupun grafik seperti icon atau gambar garis-garis yang banyak memilki kesamaan pola.
4. Shanon Fano Algoritma
Pada prinsipnya algoritma ini menggunakan pendekatan top down dalam penyusunan binary tree. Metode ini sangat efisien untuk mengompresi file text yang berukuran besar.
Langkah langkah kompresinya adalah :
- Mengurutkan karakter berdasarkan probabilitasnya yang terbesar.
- Membagi menjadi 2 berdasarkan selisih paling sedikit dari nilai dua kelompok karakter yang terurut tadi.
- Secara rekursif dibagi menjadi 2 bagian, setiap bagian memiliki nilai yang sama atau dengan selisih paling sedikit.
- Mengasign nilai 1 kekanan dan 0 ke kiri pada pohon biner.
Contoh :
Source = {A, B, C, D, E }
Peluang={0.35, 0.17, 0.17, 0.16, 0.15}
Membagi menjadi 2 kelompok besar:
- kelompok 1 = A dengan total peluang 0.35 kelompok 2 = B, C, D, E dengan total peluang 0.65 selisih kel 1 dan 2 = 0.30
- kelompok 1 = A, B dengan total peluang 0.52 kelompok 2 = C, D, E dengan total peluang 0.48 selisih kel 1 dan 2 = 0.04 –> paling sedikit
- kelompok 1 = A , B, C dengan total peluang 0.69 kelompok 2 = D, E dengan total peluang 0.31 selisih kel 1 dan 2 = 0.38
Jadi yang digunakan AB dan CDE, dengan tree awalnya yaitu :
Kemudian dari 2 leaf yang terbentuk dilakukan proses pembagian lagi seperti diatas sampai tidak bisa dibagi lagi. Sehingga menghasilkan tree yang lengkap seperti berikut :
Setelah Tree lengkap telah terbentuk maka dilakukan pembacaan dari root sampai ke karakter pada leaf. Dari pembacaan dihasilkan codeword sebagai berikut :
- A = 00 –> 2 bit
- B = 01
- C = 10
- D = 110 –>3bit
- E = 111
Dari code word diatas diperoleh panjang rata-ratanya :
Lavg = 0.35*2 + 0.17*2 + 0.17*2 + 0.16*3 + 0.15 * 3 = 2,31 bit/char
Nilai entropinya yaitu :
H( S ) = H( P1, P2, P3, P4, P5)
=-P1 log P1 -P2 log P2 – P3 log P3 – P4 log P4 – P5 log P5 –> log basis 2
= 2,23 bit/char
Jadi Efisiensinya = H(s)/Lavg = 2,232/2,31=96,67%
Jadi dengan metode ini akan terasa sangat efektif jika banyak terjadi perulangan karakter pada text.
References :
http://www.cs.cf.ac.uk/Dave/Multimedia/node209.html#SECTION04242000000000000000
5. Algoritma Adaptive Huffman Coding
Adaptive Huffman coding pertama kali diperkenalkan oleh Faller dan Gallager (Faller 1973; Gallaber 1978). Knuth memberikan kontribusi dengan peningkatan pada algoritmanya (Knuth 1985) dan menghasilkan algoritma yang dikenal dengan algoritma FGK. Versi terbaru dari adaptive Huffman Coding diperkenalkan oleh Vitter (Vitter 1987). Semua metode yang ditemukan merupakan skema define-word tabf menentukan mapping dari pesan sumber menjadi codeword didasari pada perkiraan probabilitas pesan sumber. Kode bersifat adaptive, berganti sesuai dengan perkiraan optimalnya pada saat itu. Dalam hal ini, Adaptive Huffman Code merespon lokalitas. Dalam pengertian, encoder mempelajari karakteristik dari sumber. Dekoder harus mempelajari bersamaan dengan encoder dengan selalu memperbaharui Huffman tree sehingga selalu sinkron dengan encoder.
Keuntungan lain dari system ini adalah kebutuhan akan lewatnya data, data akan lewat hanya sekali (tanpa table statistic). Tentu saja, metode one-pass tidak akan menarik apabila jumlah bit yang ditransmisikan lebih besar dari metoda twopass. Namun, performa dari metode ini, dalam ruang lingkup jumlah bit yang ditransmisikan, dapat lebih baik daripada static Huffman coding. Permasalahan ini tidak kontradiktif dengan optimalisasi pada metode statis, karena metode ini optimal hanya [ada metode yang mengasumsikan mapping berdasarkan time-variant. Kinerja dari metode adaptive dapat lebih buruk daripada metode static. Metode adaptive Faller, Gallager dan Knuth merupakan dasar dari UNIX utility compact. Kinerja compact ini termasuk bagus, karen factor kompresinya mencapai 30-40%.
Dasar dari algoritma FGK adalah adanya sibling (factor turunan) property, didefinisikan oleh Gallager [Gallager 1978]: binary code tree mempunyai sibling apabila setiap node )kecuali root) mempunyai sebuah sibling dan apabila node-node tersebut dapat diurutkan dalam weight dengan setiap node berhubungan dengan siblingnya masing-masing. Gallager membuktikan bahwa sebuah code prefik biner
merupakan Huffman code jika dan hanya jika code tree mempunyai sibling property. Dalam algoritma FGK, baik pengirim dan penerima menangani perubahan dinamis dari Huffman code tree. Daun dari setiap pohon Huffman code merepresentasikan pesan sumber dan berat dari setiap daun merepresentasikan hitungan frekuensi untuk setiap pesan. Pada titik manapun dalam satuan waktu, k dari kemungkinan n pesan sumber terdapat pada susunan pesan.
Gambar 3. Algoritma FGK
Pada Gambar 3, Algoritma FGK mengolah susunan EXAMPLE (a) Pohon setelah memproses “aa bb“; 11 akan ditransmisikan untuk b selanjutnya. (b) Setelah b ketiga; 101 akan ditransmisikan untuk tempat selanjutnya; pohon tidak berubah; 100 akan ditransmisikan untuk c pertama. (c) Pohon setelah diperbaharui dengan c pertama.
Pada awalnya, the code tree consists of a single leaf node, yang disebut 0- node. 0-node digunakan untuk menggambarkan pesan n-k yang tidak digunakan. Untuk setiap pesan yang ditransmisikan, kedua bagian harus menambahkan weight dan menghitung kembali code tree untuk mempertahankan simbling property. Pada titik dalam satuan waktu dimana t pesan telah ditransmisikan. Pada titik dimana t pesan telah ditransmisikan, k dari mereka berbeda, dan k < n, pohon merupakan Huffman tree asli dengan daun sebanyak k+1, 1 yaitu k pesan dan 0-node. Apabila pesan ke (t+1) adalah salah satu dari k, maka algoritma mentrasmisikan code ke a(t+1), menaikkan counter dan menghitung kembali pohon. Apabila terdapat pesan yang tidak digunakan, 0-node dipisah untuk membuat 2 pasang daun, satu untuk
a(t+1), dan siblingnya adalah 0-node yang baru. Sekali lagi dalam proses ini, pohon diperhitungkan kembali. Dalam kasus ini, kode untuk 0-node dikirimkan; sebagai tambahan, penerima harus memberitahukan pesan n-k mana yang tidak digunakan yang muncul. Pada setiap node, penyimpanan perhitngan dari pesan yang muncul dilakukan. Node diberikan nomor untuk mengindikasikan posisi mereka dalam urutan sibling propertinya. Pembaharuan dari pohon dapat dilakukan dalam sebuah single traversal dari node a(t+1) sampai dengan root-nya. Traversal ini harus meningkatkan perhitungan untuk node a(t+1) dan untuk setiap bagian atas dari node tersebut. Node boleh berubah untuk memelihara sibling property-nya, namun perubahan membutuhkan keterlibatan node pada path a(t+1) ke root-nya.
6. Dictionary Based Coding Algoritma
Lempel-Ziv-Welch (LZW) 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 Kompresi :
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
· 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
References :
http://www.ics.uci.edu/~dan/pubs/
http://ics.uci.edu/~dan/pubs/Data Compression.html
kompresi dibagi kedalam beberapa jenis yaitu :
Jenis Kompresi Data Berdasarkan Mode Penerimaan Data oleh Manusia
1. 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.
2. 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
Jenis Kompresi Data Berdasarkan Output
1. 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%.
2. Loseless 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
- 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.
Klasifikasi Teknik Kompresi
Teknik kompresi di klasifikasikan kedalam beberapa kategori, yaitu :
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
Kriteria Algoritma dan Aplikasi Kompresi Data
- 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).
Aplikasi Kompresi
Kompresi memberikan banyak sekali keuntungan dalam dunia teknologi informasi, terbukti dengan munculnya berbagai macam aplikasi yang menggunakan metode kompresi ini. contohnya antara lain :
- 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, namun paling umum menggunakan Katz’s Deflate Algorithm.
# Beberapa 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
- Bzip2, dan lain-lain
# Aplikasi: WinZip oleh Nico-Mak Computing
- RAR File Format
# Ditemukan oleh Eugene Roshal, sehingga RAR merupakan singkatan dari Roshal Archive pada 10 Maret 1972 di Rusia.
# Berekstensi .rar dan 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.
Sumber:
http://blog.unila.ac.id/muh47ir/2008/12/26/teori-informasi/#comment-126
