Kompresi Data Dengan Algoritma LZW

LZW Data Compression

Untuk algoritma kompresi data dengan metode LZW dapat dijelaskan  bahwa, Algoritma LZW merupakan algoritma kompresi yang bersifat lossless dan menggunakan metode dictionary. Algoritma ini ditemukan oleh Lemple, Ziv, dan Welch pada tahun 1984.Secara umum algoritma kompresi LZW akan membentuk dictionary selama proses kompresinya belangsung kemudian setelah selesai maka dictionary tersebut tidak ikut disimpan dalam file yang telah terkompresi. Prisinp kompresi akan terjadi ketika besar bit untuk dictionary yang telah ditentukan menggantikan deretan karakter atau string yang terbentuk sedangkan dalam proses dekompresinya untuk memperoleh hasil yang sama dengan file sebelum dikompresi LZW akan membuat kembali dictionary selama proses dekompresinya berlangsung.

Sehingga dapat dijelaskan bahwa 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. Dibawah merupakan pseudocode kompresi algoritma LZW.

a= NIL

while (ada inputan kemudian baca sebuah karakter x)

if (ax ada dalam kamus)

then a = ax

else

add ax to the dictionary

output indek untuk a

a = x

Dari algoritma LZW dapat dijelaskan bahwa :

1. Inisialisasi input stream yang mengandung karakter-karekter dasar.
2. Membaca karakter dari input stream jika EOF maka menuju langkah 5.
3. Gabungkan karater awal dengan karakter yang dibaca selanjutnya menjadi sebuah string.
4. jika string baru ini tidak ada dalam dictionary maka
   • Buat indek baru untuk string baru tersebut.
   • Menuju Langkah 2.
5. Jika string yang terbentuk telah mempunyai indek di dalam dictionary maka
   • Gabungkan karakter sebelumnya dengan karakter yang dibaca atau string yang telah terbentuk menjadi sebuah string baru.
   • Menuju langkah 2.
6. Tulis output kode.

Untuk contoh dari algoritma diatas dapat dibuat implementasi pada contoh dibawah ini :

Input string : TES_TEA_EAT_MEET_SLEEP

bit dictionary : 9 bit

Total awal bit disimpan tanpa kompresi = Total input * bit dictionary = 22 * 9 = 198 bit

Besar file setelah dikompresi = Total output * bit dictionary = 19 * 9 = 171 bit

Input stream: TES_<256>A_EAT_MEE<265>SL<268>P.

Jadi dapat ditarik sebuah kesimpulan mengenai algoritma kompresi data menggunakan LZW ialah :

“Kecepatan kompresi algoritma LZW secara signifikan berkurang pada file UNIX, file  executable, file gambar, file multimedia, dan file hasil kompresi tetapi dibandingkan beberapa algoritma yang ada, data kompresi dengan algoritma LZW memiliki waktu yang tersingkat.

Dapat disimpulkan lagi dari penjelasan algoritma diatas, Proses penambahan indek dari string baru yang terbentuk akan dilakukan jika dictionary tidak penuh dan string tersebut belum ada di dictionary. Pencarian tempat bagi indek pada indek-indek array yang masih kosong diperlukan untuk menentukan tempat yang sesuai bagi indek untuk string baru yang terbentuk. Cara pencarian array based dictionary sesuai dengan pendekatan brute force dimulai dari indek pertama hingga indek terakhir dari string yang telah ada di dictionary.

From   : http://web.diegm.uniud.it/Utenti/pierluca/public_html/teaching/fpac/documentazione_tecnica/tecniche_di_compressione/lzw/lzw.pdf