Minggu, 09 Oktober 2011

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

Tidak ada komentar:

Posting Komentar