Algoritma Lempel Ziv Welch (LZW)

           Algoritma Lempel Ziv Welch (LZW)

Algoritma LZW dikembangkan dari metode kompresi yang dibuat oleh Ziv dan Lempel pada tahun 1977. algoritma ini melakukan kompresi dengan menggunakandictionary. Pendekatan ini bersifat adaptif dan efektif. Prinsip kompresi tercapai jika referensi dalam bentuk pointer dapat disimpan dalam jumlah bit yang lebih sedikit dibandingkan string aslinya. The Lempel-Ziv  (LZ) metode kompresi adalah salah satu algoritma paling populer untuk penyimpanan lossless. mengempis  adalah variasi LZ yang dioptimalkan untuk kecepatan dekompresi dan rasio kompresi, sehingga kompresi ini bisa lambat. Deflate digunakan dalam PkZip  , gzip  dan PNG . LZW  (Lempel-Ziv-Welch) digunakan dalam gambar GIF. Juga patut diperhatikan adalah LZR (LZ-Renau) metode, yang melayani sebagai dasar dari metode Zip. metode LZ memanfaatkan model kompresi berbasis tabel di mana entri tabel diganti untuk string data yang diulang. Untuk metode yang paling LZ, tabel ini dihasilkan secara dinamis dari data sebelumnya dalam input. Tabel sendiri sering Huffman dikodekan  (misalnya Shri, LZX). berdasarkan skema coding LZ arus yang baik adalah melakukan LZX  , digunakan dalam Microsoft CAB  format.

Yang sangat kompresor terbaik menggunakan model probabilistik, di mana prediksi yang digabungkan dengan algoritma yang disebut aritmatika coding . Arithmetic coding, diciptakan oleh Jorma Rissanen  , dan berubah menjadi metode praktis oleh Witten, Neal, dan Cleary, mencapai kompresi lebih unggul dari algoritma Huffman dikenal-baik, dan cocok terutama baik untuk konteks data kompresi adaptif tugas dimana prediksi sangat- tergantung. Pengkodean aritmatika digunakan dalam standar kompresi gambar-bilevel JBIG  , dan dokumen-standar kompresi DjVu  . Entri teks sistem, Dasher  , adalah-terbalik aritmatika-coder.

Algoritma kompresi LZW

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

Sebagai contoh, string “ABBABABAC” akan dikompresi dengan LZW. Isi dictionary pada awal proses diset dengan tiga karakter dasar yang ada: “A”, “B”, dan “C”. Tahapan proses kompresi ditunjukkan pada Tabel 3. Kolom posisi menyatakan posisi sekarang dari stream karakter dan kolomkarakter menyatakan karakter yang terdapat pada posisi tersebut.  Kolom dictionary menyatakan stringbaru 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.

  

                          

Flowchart Algoritma LZW

                        Jika dialgoritmakan mejadi kompresi bisa berbentuk seperti ini:

            BEGIN

            S = next input character;

            While not EOF

            {

                        C = next input character;

                        If s + c exists in the diactionary

                                    S = s + c

                        Else

                        {

                                    Output the code for s;

                                    Add string s + c to the dictionary with a new code

                                    S = c;

                        }

            }

END

                        Jika algoritma dekompresinya adalah seperti dibawah ini :

            BEGIN

            S = NULL;

            While not EOF

            {

                        K = NEXT INPUT CODE;

                        Entry = dictionary entry for K;

                        Ouput entry;

                        If (s != NULL)

                                    add string s + entry[0] to dictionary with new code

                        S = Entry;

            }

END

  Contoh Penerapan Simulasi Algoritma Lempel Ziv Welch (Lzw) Guna Mengkompresi Data Text Pada Komunikasi Data Real Time

2.3.2       Proses Kompresi Pada Server

 

Proses Dekompes Pada Client

 

Sumber

1.      Halvsorson Michael, 2000. Microsoft Visual Basic 6.0 Step By Step. Jakarta; PT. Elex Media Komputindo

2.      Bell, Timothy C., Cleary, John G., Witten, Ian H, (1990) “Text Compression”, Prentice Hall, Englewood NJ

3.      Torer, J.A., (1988) “Data Compression”,  Computer Science Press, Rockville, MD Witten, Ian H., Neal, Radford M.

4.      Nelson, Mark (1987) “  LZW Data Compression “ , Doctor Dobb’s Journal, October.

Mata kuliah : Pengembangan Teknologi Media dan Digital 
I Putu Agus Eka Pratama, S.T., M.T.
ITB
( Nama : Andre Octavianus Sitepu & NIM : 1312006 ) 

Posted in: Pengembangan Teknologi Media Digital