Pada masa modern ini, seiring dengan berkembangnya teknolo-gi, orang-orang menyukai segala sesuatu dengan kualitas terbaik. Seperti halnya pada gambar, musik, video, dsb. Sayangnya, sema-kin tinggi kualitas suatu data maka semakin tinggi pula ukuran data tersebut. Dengan terbatasnya ruang penyimpanan data yang dimiliki atau terbatasnya kuota internet untuk melakukan proses sharing dan upload, maka alangkah baiknya bila dapat dilakukan kompresi data. Contoh kompresi data yang paling sering digunakan pada banyak sistem operasi seperti Windows, Macintosh, Ubuntu, bahkan Android adalah ZIP. Salah satu algoritma yang diterapkan dalam ZIP dan variannya adalah LZ77. Algoritma ini ditemukan oleh Jacob Ziv dan Abraham Lempel pada 1977.

1.2.3.

Bagaimana konsep algoritma LZ77 dalam proses kompresi data?Bagaimana output yang dihasilkan oleh algoritma LZ77?Apakah dapat dilakukan proses dekompresi pada output hasil kompresi algoritma LZ77?

Algoritma LZ77 menggunakan konsep dasar Dictionary-based Compression. Ide dalam konsep ini adalah menggantikan pengula-ngan suatu frasa khusus atau kelompok byte dalam suatu data dengan referensi yang merujuk pada frasa atau kelompok byte yang sudah muncul sebelumnya. Pada LZ77, pengulangan digantikan dengan kode pendek. Berikut ini akan dijelaskan cara kerja LZ77 yang sederhana dengan menggunakan frasa:the brown fox jumped over the brown foxy jumping frog Frasa tersebut terdiri dari 53 karakter (termasuk karakter spasi) atau dengan kata lain memiliki panjang 424 bit. Awalnya, setiap karakter dipetakan ke dalam pola 9-bit yang berupa angka 1 dan representasi karakter dalam 8-bit kode ASCII. Algoritma akan men-cari pengulangan barisan kata. Ketika ditemukan pengulangan, maka algoritma akan melakukan proses scan hingga pengulangan berakhir. Barisan pertama adalah the brown fox yang kembali muncul pada posisi setelah 26 karakter dari yang sebelumnya (terhitung dari karakter pertama barisan) dan panjang barisan tersebut adalah 13 karakter. Ada dua pilihan dalam proses encoding; 8-bit pointer dan 4-bit panjang atau 12-bit pointer dan 6-bit panjang; serta 2-bit header yang menunjukkan pilihan manakah yang digunakan, 00 untuk pilihan pertama dan 01 untuk pilihan kedua. Sehingga hasil encoding encoding the brown fox adalah <00b> <26d> <13d> atau 00 00011010 1101. Barisan kedua adalah jump (termasuk karakter spasi sebelum kata jump) yang kembali muncul pada posisi setelah 27 karakter dari yang sebelumnya dan panjang barisan tersebut adalah 5 karak-ter. Hasil encoding jump adalah <00b> <27d> <5d> atau 00 00011011 0101.

Pesan yang telah dikompres tersebut terdiri dari 35 karakter 9-bit dan 2 kode, dengan total 35x9+2x14=343 bit.

Struktur umum algoritma LZ77 menggunakan dua buffer, yaitu sliding history buffer dan look-ahead buffer. Sliding history buffer me-ngandung N karakter source yang telah diproses, sedangkan look-ahead buffer mengandung L karakter source yang akan diproses.

the brown fox jumped over the brown foxy jumping frog

the brown fox jumped over the brown foxy jumping frog00b 26d 13d 00b 27d 5d

2627

13 5

the brown fox jumped over the brown foxy

rown fox jumped over the brown foxy jump ing frog

jumping frog

sliding history buffer

Figure 1.A

Figure 1.B

Figure 1.C

look-ahead bufferdiscard source

outputcompressed text

shift source text

1.

2.

3.

Konsep algoritma LZ77 dalam proses kompresi adalah mengu-bah frasa yang terulang dengan kode pendek berupa pointer dan panjang frasa tersebut.Output yang dihasilkan oleh algoritma LZ77 memiliki ukuran lebih kecil dari ukuran data aslinya.Proses dekompresi dapat dilakukan pada output hasil kompresi algoritma LZ77.

Stallings, William. 2005. Cryptography and Network Security : Principles and Practices 4th Edition. Prentice Hall.

http://cs.stanford.edu/people/eroberts/courses/soco/projects/-data-compression/lossless/lz77/index.htm