BAB 2 Tinjauan Teoritis

BAB 2 Tinjauan Teoritis


2.1

Tinjauan Kepustakaan Topik kompresi data ini pernah dikerjakan oleh salah satu mahasiswa Politeknik Negeri Bandung angkatan 2007 yaitu Andini

Ramika Sari [4]. Proses kompresi data dilakukan menggunakan

pengembangan metode deflate yaitu kombinasi metode LZSS dan metode

Huffman Coding. Namun sesuai perkembangan teknologi, muncul metode baru yang lebih memperkecil ukuran data sehingga lebih menghemat

pemakaian bandwidth. Sehingga pada proyek akhir ini akan dibuat kompresi data dengan menggunakan metode Lempel Ziv Welch (LZW) yang merupakan pengembangan dari metode LZSS. Untuk menunjang pembuatan proyek akhir ini, diadakan studi literatur dari berbagai sumber yang diantaranya adalah: 1. David Solomon, Data Compression The Complete Reference Fourth Edition. Buku ini berisi tentang kumpulan metode kompresi data baik teks, gambar, suara maupun video [1]. 2. Roy Indra Haryanto, Kompresi Data dengan Algoritma Huffman dan Perbandingannya dengan Algoritma LZW dan DMC. Makalah ini berisi tentang metode kompresi teks dengan menggunakan algoritma Huffman, LZW dan DMC berikut dengan kelebihan dan kekurangan masing-masing metode [2]. 3. Oky Dwi Nurhayati, ST, MT, Kompresi Data. Power point bahan kuliah Universitas Diponogoro yang diambil dari internet berisi tentang penjelasan dari kompresi data, jenis-jenis kompresi serta metode-metode kompresi [3].

2.2

Kompresi Data Kompresi berarti memampatkan/mengecilkan ukuran. 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 encoding tertentu.

Susan Dwi Marcia (091331059) Laporan Proyek Akhir

5


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 kompresi bisa dilakukan terhadap data teks/biner, gambar (JPEG, PNG, TIFF), audio (MP3, AAC, RMA, WMA), dan video (MPEG, H261, H263). Sebagai contoh untuk kompresi data teks : 

1 karakter = 2 bytes (termasuk karakter ASCII Extended)



Setiap karakter ditampilkan dalam 8x8 pixel



Jumlah karakter yang dapat ditampilkan per halaman = 640 x 480 8X8



= 4800 karakter

Kebutuhan tempat penyimpanan per halaman = 4.800×2 byte = 9.600 byte = 9.375 Kbyte

2.3

Jenis Kompresi Data Berdasarkan Output 

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.


6


 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%. 

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.  Kadang kala ada data-data yang setelah dikompresi dengan teknik ini ukurannya menjadi lebih besar atau sama [3].

2.4

Metoda Kompresi LZW Algoritma LZW dikembangkan oleh Terry A.Welch dari metode kompresi sebelumnya yang ditemukan oleh Abraham Lempel dan Jacob Ziv pada tahun 1977. Algortima ini menggunakan teknik dictionary dalam kompresinya. Dimana string karakter digantikan oleh kode table yang dibuat setiap ada string yang masuk. Tabel dibuat untuk referensi masukan string selanjutnya. Ukuran tabel dictionary pada algoritma LZW asli adalah 4096 sampel atau 12 bit, dimana 256 sampel pertama digunakan untuk table karakter single (Extended ASCII), dan sisanya digunakan untuk pasangan karakter atau string dalam data input. Algoritma LZW melakukan kompresi dengan mengunakan kode table 256 hingga 4095 untuk mengkodekan pasangan byte atau string.


7


Dengan metode ini banyak string yang dapat dikodekan dengan mengacu

pada string yang telah muncul sebelumnya dalam teks [1].

2.4.1

Cara Kerja Algoritma LZW Prinsip umum kerja algoritma LZW adalah mengecek setiap karakter yang muncul kemudian menggabungkan dengan karakter

selanjutnya menjadi sebuah string jika string baru tersebut tidak berada

dalam dictionary atau belum diindekkan maka string baru tersebut

akan diindekkan ke dalam dictionary. Sebagai contoh, string “BABAABAAA” akan dikompresi dengan LZW. Isi dictionary pada diset dengan jumlah karakter ASCII yaitu sebanyak 255. Tahapan proses kompresi ditunjukkan pada Gambar 1. dan Tabel 1. Gambar 1. Tahapan Penggabungan Karakter LZW

Tabel 1. Tahapan Kompresi LZW

Kolom dictionary menyatakan kamus baru yang dihasilkan dari penggabungan karakter pada Gambar 1. dan kolom string menyatakan karakter yang telah digabung sesuai metode LZW. Kolom code word menyatakan nomor indeks untuk string tersebut ditulis dalam bentuk numeric. Kolom output menyatakan kode output yang dihasilkan oleh langkah proses kompresi ditunjukkan pada Tabel 1. Proses dekompresi data pada algoritma LZW tidak jauh berbeda dengan proses kompresinya. Pada dekompresi LZW, juga dibuat tabel dictionary dari data input kompresi, sehingga tidak diperlukan penyertaan


8


tabel dictionary ke dalam data kompresi. Proses dekompresi dapat dilihat

pada Gambar 2. di bawah ini:

Gambar 2. Tahapan Dekompresi LZW [5]

Proses Encoding

Proses Decoding start

start

Input CW

Input P

PW = CW

Input C CW = byte berikutnya

(P+C) ada di tabel? N

Y CW ada di tabel? N

Output kode = P

Y

P = P+C

Masukkan P+C ke tabel

P=C

P = string PW

Output CW ke tabel

C = karakter pertama PW

P= String PW

Output (P+C) ke tabel

C= karakter pertama CW

P+C = CW

Outtput (P+C) ke tabel

Byte ada lagi? Byte ada lagi?

Output kode = P

Stop

Output kode = CW

Stop

Gambar 3. Proses Encoding dan Decoding LZW Susan Dwi Marcia (091331059) Laporan Proyek Akhir

9


2.4.2 Algoritma LZW

Algoritma untuk kompresi LZW adalah sebagai berikut : 1.

{„A‟..‟Z‟,‟a‟..‟z‟,‟0‟..‟9‟}.

KAMUS diinisialisasi dengan semua karakter dasar yang ada :

2.

W ← karakter pertama dalam stream karakter.

3.

K ← karakter berikutnya dalam stream karakter.

4.

Lakukan pengecekan apakah (W+K) terdapat dalam KAMUS



Jika ya, maka W

W + K (gabungkan W dan K menjadi

string baru). 

Jika tidak, maka :  Output sebuah kode untuk menggantikan string W.

 Tambahkan string (W+ K) ke dalam dictionary dan berikan nomor/kode berikutnya yang belum digunakan dalam dictionary untuk string tersebut.  W ← K. 

Lakukan pengecekan apakah masih ada karakter berikutnya dalam stream karakter  Jika ya, maka kembali ke langkah 2.  Jika tidak, maka output kode yang menggantikan string W, lalu terminasi proses (stop).

Algoritma untuk dekompresi LZW adalah sebagai berikut : 1.

Dictionary diinisialisasi dengan semua karakter dasar yang ada : {„A‟..‟Z‟,‟a‟..‟z‟,‟0‟..‟9‟}.

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


10


 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

6.

dalam

dictionary

(sekarang

Apakah terdapat kode lagi di stream kode ? 

Jika ya, maka kembali ke langkah 4.



Jika tidak, maka terminasi proses (stop) [2].


ke

berkorespondensi dengan CW)

tersebut

11

BAB 2 Tinjauan Teoritis

Recommend Documents