Algoritma LZW (Lempel-Ziv-Welch)
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.
Fungsi/Cara Kerja :
Algoritma kompresi LZW secara lengkap :
- KAMUS diinisialisasi dengan semua karakter dasar yang ada : {‘A’..’Z’,’a’..’z’,’0’..’9’}.
- W <-- karakter pertama dalam stream karakter.
- K <-- karakter berikutnya dalam stream karakter.
- Lakukan pengecekan apakah (W+K) terdapat dalam KAMUS. Jika ya, maka W ß W + K (gabungkan W dan K menjadi string baru).
Jika tidak, maka :
- Output sebuah kode untuk menggantikan stringW.
- Tambahkan string (W+ K) ke dalam dictionary dan berikan nomor/kode
berikutnya yang belum digunakan dalam dictionary untuk string tersebut.
- W <-- K.
- Lakukan pengecekan apakah masih ada karakter berikutnya dalam stream karakter
- Jika ya, maka kembali ke langkah 2.
- 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 dictionary
pada diset dengan tiga karakter dasar yang ada: “A”, “B”, dan “C”.
Tahapan proses kompresi ditunjukkan pada Tabel dibawah ini:
Tahapan Kompresi LZW :
Langkah Posisi Karakter Dictionary Output
1 1 A [4] A B [1]
2 2 B [5] B B [2]
3 3 B [6] B A [2]
4 4 A [7] A B A [4]
5 6 A [8] A B A C [7]
6 9 C - [3]
Hasil Proses Kompresi
Kesimpulan :
Secara rata-rata algoritma LZW membutuhkan waktu kompresi yang
tersingkat (kecepatan kompresinya = 1139 KByte/sec ± 192,5), diikuti
oleh algoritma Huffman (555,8 KByte/sec ± 55,8), dan terakhir DMC (218,1
KByte/sec ± 69,4). DMC mengorbankan kecepatan kompresi untuk
mendapatkan rasio hasil kompresi yang baik. File yang berukuran sangat
besar membutuhkan waktu yang sangat lama bila dikompresi dengan DMC.
Pengembangan Teknologi Media Digital
I Putu Agus Eka Pratama, ST MT
Institut Teknologi Harapan Bangsa
I Putu Agus Eka Pratama, ST MT
Institut Teknologi Harapan Bangsa
Sumber :
Tidak ada komentar:
Posting Komentar