Algoritma LZW (Lempel-Ziv-Welch)

Algoritma LZW (Lempel-Ziv-Welch) 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. Dengan metode ini banyak string yang dapat dikodekan dengan mengacu pada string yang telah muncul sebelumnya dalam teks.



Algoritma kompresi LZW secara lengkap :

1. Dictionary (kamus) diinisialisasi dengan semua karakter dasar yang ada : {‘A’..’Z’,’a’..’z’,’0’..’9’}.
2. W <- karakter pertama dalam stream karakter.
3. K <- karakter berikutnya dalam stream karakter.
4. Lakukan pengecekan apakah (W+K) terdapat dalam Dictionary
a. Jika ya, maka W <- W + K (gabungkan W dan K menjadi string baru).
b. 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.
5. Lakukan pengecekan apakah masih ada karakter berikutnya dalam stream karakter.
a. Jika ya, maka kembali ke langkah 2.
b. Jika tidak, maka output kode yang menggantikan string W, lalu terminasi proses (stop).

                                                                  Flowchart Algoritma LZW

Sebagai contoh, string “ABBABABAC” akan dikompresi dengan LZW. Isi pada dictionary diset dengan tiga karakter dasar yang ada yaitu: “A”, “B”, dan “C”.
                                                                   Tahapan Kompresi LZW

Kolom posisi menyatakan posisi sekarang dari stream karakter dan kolom karakter menyatakan karakter yang terdapat pada posisi tersebut. Kolom dictionary menyatakan string baru yang sudah ditambahkan ke dalam dictionary dan nomor indeks untuk string tersebut ditulis dalam kurung siku. Kolom output menyatakan kode output yang dihasilkan oleh langkah kompresi.

Hasil Proses Kompresi

 

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 tabel dictionary ke dalam data kompresi.

Berikut algoritma dekompresi LZW :

1. Dictionary diinisialisasi dengan semua karakter dasar yang ada : {‘A’..’Z’,’a’..’z’,’0’..’9’}.
2. CW kode pertama dari stream 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 ?
a. 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
b. Jika tidak, maka :
- P <- string.PW
- C <- karakter pertama dari string.PW
-Output string (P+C) ke stream tambahkan string tersebut ke dalam (sekarang berkorespondensi dengan CW)
6. Apakah terdapat kode lagi di stream code?
a. Jika ya, maka kembali ke langkah 4.
b. Jika tidak, maka terminasi proses (stop).

Sumber : http://knxbmt.blogspot.com/2010/06/algoritma-lzw.html