Metode LZW

Algoritma LZW 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.

Kelebihan algoritma ini yaitu cepat dalam implementasi dan kekurangannya kurang optimal karena hanya melakukan analisis terbatas pada data. Algoritma ini melakukan kompresi dengan menggunakan kamus, di mana fragmen-fragmen teks digantikan dengan indeks yang diperoleh dari sebuah “kamus”. Algoritma LZW secara lengkap:

1.      Kamus diinisialisasi dengan semua karakter dasar yang ada : {‘A’..’Z’,’a’..’z’,’0’..’9’}.

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 :

i.     Output sebuah kode untuk menggantikan string P

ii.   Tambahkan string (P + C) ke dalam dictionary dan berikan nomor/kode berikutnya yang belum digunakan dalam dictionary untuk string tersebut.

iii. 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).

Metode RLE

Kompresi RLE adalah jika data d terjadi sebanyak n kali pada aliran data input, maka kejadian n akan diganti dengan nd. Data yang terjadi berurutan n kali disebut run length dari n, dan pada kompresi disebut run-length encoding atau RLE.

Contoh kompresi RLE pada 8-bit bitmap grayscale

Data asli : 12 12 12 34 55 55 55 55 11 11 11 11 11 34 34 34

Data encoded : (3,12)(1,34)(4,55)(5,11)(3,34)

Metode Huffman

Metode Huffman merupakan salah satu teknik kompresi dengan cara melakukan pengkodean dalam bentuk bit untuk mewakili data karakter. Cara kerja atau algoritma metode ini adalah sebagai berikut:

1.      Menghitung banyaknya jenis karakter dan jumlah dari masing-masing karakter yang terdapat dalam sebuah file

2.      Menyusun setiap jenis karakter dengan urutan jenis karakter yang jumlahnya paling sedikit ke yang jumlahnya paling banyak

3.      Membuat pohon biner berdasarkan urutan karakter dari yang jumlahnya terkecil ke yang terbesar, dan memberi kode untuk tiap karakter

4.      Mengganti data yang ada dengan kode bit berdasarkan pohon biner

5.      Menyimpan jumlah bit untuk kode bit yang terbesar, jenis karakter yang diurutkan dari frekuensi keluarnya terbesar ke terkecil beserta data yang sudah berubah menjadi kode bit sebagai data hasil kompresi

Kompresi Citra

Kompresi pada file citra digital dilakukan dengan tujuan untuk mengurangi redundansi dari data-data yang terdapat dalam citra sehingga dapat disimpan atau ditransmisikan secara efisien. Ada empat pendekatan untuk kompresi citra, yaitu:

1.      Statistical Compression, yaitu proses kompresi citra berdasarkan pada gray level dari pixel-pixel dalam keseluruhan image

2.      Spatial Compression, yaitu proses kompresi citra berdasarkan pada hubungan spasial antara pixel-pixel dari type yang sama secara predictable (dapat diperkirakan)

3.      Quantizing Compression, yaitu proses kompresi citra dengan mengurangi resolusi atau jumlah gray level yang ada pada citra

4.      Fractal Compression, yaitu proses kompresi citra dengan mengkodekan citra sebagai himpunan dari parameter-parameter pembangkitan fractal.

Beberapa teknik kompresi citra yang ada berdasarkan output yang dihasilkan antara lain:

1.      Lossy Compression:

Lossy compression akan memperkecil ukuran file citra dengan menghilangkan beberapa informasi dalam citra asli. Teknik ini mengubah detail dan warna pada file citra menjadi lebih sederhana tanpa terlihat perbedaan yang mencolok dalam pandangan manusia, sehingga ukurannya menjadi lebih kecil. Biasanya digunakan pada citra foto atau image lain yang tidak terlalu memerlukan detail citra, di mana kehilangan bit rate foto tidak berpengaruh pada citra. Beberapa teknik loseless antara lain color reduction, chroma subsampling dan transform coding

2.      Lossless Compression:

Teknik kompresi citra dimana tidak ada satupun informasi citra yang dihilangkan. Teknik ini biasa digunakan pada citra medis. Beberapa metode loseless antara lain Run Length Encoding (RLE), Huffman, Aritmatik dan Lempel–Ziv–Welch (LZW)

Sekilas tentang Bitmap

Bitmap adalah gambar bertipe raster. Mengandalkan jumlah pixel dalam satu satuan tertentu. Semakin rapat pixel maka semakin baik kualitas gambar. Sebaliknya jika dipaksa diperbesar akan terlihat pecah. Besar file yang dihasilkan cenderung besar.

Suatu foto atau gambar bisa direpresentasikan dengan format bitmap dalam ribuan titik warna-warni yang membentuk suatu pola. Pada file bitmap dikenal dua istilah penting, yaitu :

1.    1. Resolusi atau jumlah titik persatuan luas, yang akan mempengaruhi ketajaman dan detil file bitmap. Biasanya dinyatakan dalam satuan dpi (dot per inch)

2. Intensitas atau kedalaman warna, yang akan menentukan kualitas warna gambar secara keseluruhan. Biasanya dikenal istilah 256 warna, high color, true color, gradasi abu-abu (grayscale), serta hitam-putih (black & white).
Format citra digital pada umumnya terdiri dari header berkas, header bitmap, informasi palet warna dan isi dari data bitmap itu sendiri

Daftar Isi

Berikut daftar isi dari tugas Jarinfo saya:

Judul
Abstraksi
Bab 1. Pendahuluan
Bab 2. Dasar Teori
2.1. Teori Kompresi
2.2. File Bitmap
2.3. Kompresi Citra
2.4. Metode Huffman
2.5. Metode Run Length Encoding (RLE)
2.6. Metode Lempel–Ziv–Welch (LZW)
2.7. Rasio Kompresi
Bab 3. Model Konseptual dan Pengujian Model
Daftar Pustaka

Sekilas tentang Kompresi

Kompresi merupakan suatu teknik yang digunakan untuk melakukan proses encoding ulang terhadap sebuah data agar resource yang dibutuhkan untuk menampung data tersebut menjadi lebih sedikit. Kompresi sering digunakan pada jaringan agar proses pengiriman menjadi lebih cepat.
Berdasarkan tipe peta kode yang digunakan untuk mengubah data, algoritma kompresi dapat dibagi menjadi dua kategori, yakni:
1. Metode statik, yakni metode kompresi yang menggunakan peta kode yang selalu sama. Metode ini terdiri dari dua tahap, yakni tahap menghitung probabilitas kemunculan tiap karakter pada data awal kemudian menentukan peta kodenya dan tahap mengubah data awal menjadi data yang terkompresi, contohnya algoritma Huffman statik
2. Metode dinamik, yakni metode kompresi yang menggunakan peta kode yang dapat berubah dari waktu ke waktu. Metode ini terdiri dari satu tahap yakni satu kali pembacaan terhadap isi data, contohnya algoritma LZW
Berdasarkan teknik pengkodeannya, algoritma kompresi dapat dibagi menjadi tiga kategori, yakni:
1. Metode symbolwise, yakni metode kompresi yang menghitung peluang kemunculan dari tiap karakter pada data awal, lalu mengkodekan satu karakter dalam satu waktu, di mana karakter yang lebih sering muncul dikodekan dengan kode yang lebih pendek dibandingkan dengan karakter yang jarang muncul, contohnya algoritma Huffman
2. Metode predictive, yakni metode kompresi yang menggunakan model finite-state untuk memprediksi distribusi probabilitas dari simbol-simbol selanjutnya, contohnya algoritma DMC
3. Metode dictionary, yakni metode kompresi yang menggantikan karakter dalam data awal dengan indeks lokasi dari karakter tersebut dalam sebuah kamus (dictionary), contohnya algoritma LZW
Berdasarkan hasil outputnya, algoritma komresi dapat dibagi menjadi dua kategori, yakni:
1. Lossy, yakni metode kompresi yang saat dilakukan proses dekompresi datanya tidak sama dengan data sebelum kompresi namun masih dapat ditoleransi oleh indera manusia, contohnya algoritma kompresi untuk MP3, JPEG, MPEG, dan WMA
2. Loseless, yakni metode kompresi yang saat dilakukan proses dekompresi datanya sama dengan data sebelum kompresi, contohnya algoritma kompresi untuk ZIP dan RAR