KULIAH PTMD : ALGORITMA LZW (LEMPEL-ZIV-WELCH)

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

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 :
i. output string.CW ke stream karakter
ii. P= string.PW
iii. C = karakter pertama dari string.CW
iv. tambahkan string (P+C) ke dalam dictionary
Jika tidak, maka : 

i. P =string.PW
ii. C = karakter pertama dari string.PW
iii. 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.
- ika tidak, maka terminasi proses (stop)

SUMBER :

- budiastika.blogspot.com

- http://sheunyil.blogspot.com