Algoritma Lempel-Ziv

Algoritma Lempel-Ziv merupakan suatu variable-to-fixed length code. Secara mendasar, ada dua versi dari algoritma ini yang biasanya terdapat dalam literatur: versi teoritis dan versi praktek. Secara teoritikal, kedua versi tersebut menunjukkan cara kerja yang sama. Bagaimanapun juga, bukti dari optimalitas asymptotic dari versi teoritikal lebih mudah. Dalam prakteknya, versi praktek lebih mudah diimplementasi dan sedikit lebih efisien. Berikut ini merupakan algoritma versi praktek yang dijelaskan dalam buku oleh Gersho dan Gray dan dalam paper oleh

Ide dasar adalah menguraikan input sequence menjadi blok yang tidak saling menimpa dari panjang yang berbeda sementara membentuk suatu “kamus” dari blok tersebut.

Algoritma Encoding Lempel-Ziv

1. Inisialisasi “kamus” yang terdiri dari semua blok dengan panjang satu karakter (D = {a, b})
2. Lakukan pencarian untuk blok yang paling panjang W yang mana muncul pada kamus
3. Encode W dengan indeksnya dalam kamus
4. Tambahkan W diikuti dengan simbol pertama dari blok berikutnya dari kamus tersebut
5. Lakukan lagi langkah ke-2
   Contoh berikut mengilustrasikan bagaimana cara kerja dari encoding Lempel-Ziv.

• Secara teoritikal, ukuran dari kamus dapat berkembang secara besar menuju tak berhingga 
• Dalam prakteknya, ukuran kamus terbatas. Sekali limit tersebut dicapai, tidak ada lagi entri yang ditambahkan. Welch merekomendasikan sebuah kamus dengan ukuran 4096. Ini berkorespondensi dengan 12 bit per indeks. 
• Panjang dari indeks boleh beragam. Sebagai contoh, dalam blok ke-n, ukuran kamusnya adalah n + 1 (asumsi bahwa limit tidak pernah dicapai). Oleh karena itu, dapat dilakukan encoding pada blok indeks n menggunakan [log2(n +1)] bit (dibulatkan hingga integer terdekat). Sebagai contoh, indeks pertama dapat direpresentasikan dengan 1 bit, kedua dan ketiga oleh tiap 2 bit, keempat, kelima, keenam, dan ketujuh tiap 3 bit, dan seterusnya. Ini merupakan versi variable-variable length dari algoritma Lempel-Ziv 
• Untuk ukuran kamus yang maksimum yaitu 2m, variable-length encoding dari indeks menghemat dengan tepat hingga 2m−1 bit dibandingkan dengan fixed-length encoding. 
• Contoh di atas, seperti kebanyakan contoh ilustrasi pada literatur, tidak menghasilkan kompresi yang sebenarnya. Sebenarnya, lebih bit yang dipakai untuk merepresentasi indeks daripada data asli. Ini disebabkan oleh panjang dari input data dalam contoh yang terlalu pendek. 
• Dalam prakteknya, algoritma Lempel-Ziv bekerja dengan baik (sesuai dengan kompresi aktual) hanya ketika input data cukup besar dan ada cukup redundansi dalam data. 
• Proses dekompresi bekerja dengan urutan yang terbalik. Decode mengetahui simbol terakhir yang paling baru di entri kamus adalah simbol pertama dari penguraian blok berikutnya. Pengetahuan ini dipakai untuk memecahkan kembali konflik yang mungkin ada pada decoder. 
• Banyak program populer (seperti Unix Compress dan Uncompress, Gzip, dan GunZip, dan Windows Winzip) berdasarkan pada algoritma Lempel-Ziv. 
• Nama “Ziv-Lempel” lebih tepat daripada “Lempel-Ziv” 
• Tabel berikut ini membandingkan versi Adaptif dari Huffman Code (diimplementasikan pada program Unix “compact”) dan Algoritma Lempel-Ziv (pada program Unix “compress”).

Tabel Perbandingan Algoritma Huffman vs Lempel-Ziv

Teks file yang memiliki ukuran besar dalam distribusi statistikal teks Inggris (terdiri atas tujuh buku klasik dengan dua puluh tujuh alphabet Inggris) mempunyai rasio kompresi 36,3% (ukuran data asli 5.086.936 byte, ukuran setelah dikompresi 1.846.919 byte, menggunakan program “Gzip” Linux). Korespondensi dengan hasil tersebut adalah laju kompresi 2,9 bits/character − dibandingkan dengan entropy rate 2,3 bits/character yang diprediksi oleh Shannon. Kehilangan optimalitas ini dikarenakan oleh ukuran dari kamus.