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

8 responses to this post.

  1. Posted by harold on January 28, 2011 at 1:15 pm

    bro algo LZW dapar menerima input berupa bit atau teks ? contoh disinikan berupa teks bagaimana klo input berupa file audio / gambar apakah bisa diencode krn keduanya tidak mengandung teks tolong pencerahannya…

    Reply

  2. Posted by M Rizki Dwi A on February 5, 2011 at 2:44 pm

    Mas….ad Source code atau contoh prog.ny nggak dg Java nggak???saya dapet dg C Builder cuma rada nggak ngerti dg alur Prog.Ny…Ada gabung ma assembler pla….Ane rencanany mau buat versi mobile dgn J2ME…Trus kalo d banding dgn algoritma RLE lebih efektif mana,,trus klo dari segi keruwetan atau keribetan,,mna yg lebih rumit prosesny…Mhn Pencerahanny Mas..Thanks Before….

    Reply

  3. Posted by sarah on April 29, 2011 at 9:45 am

    mas klu source code dg delphi ada agk?alx saya byk dpt yg c++ m java…
    thanks

    Reply

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: