Pemampatan file dengan menggunakan metode LZSS (lempel-ziv-Strer-Szymanski)

Abstract

Algoritma LZSS (Lempel-Ziv-Storer-Szymanski) merupakan perubahan dari algoritıma LZ77 yang dilakukan oleh James Storer dan Thomas Szymanski pada tahun 1982. LZSS juga merupakan salah satu bagian dari pemampatan model kamus, yang menggunakan simbol baru untuk menggantikan string data. Output LZSS terdiri dari sebuah literal bytes atau pasangan (offset, len). Literal bytes merupakan input byte sederhana yang dikopikan secara langsung ke output. Pasangan (offset, len) menjelaskan proses kembali (back) ke jarak offset suatu input data yang nantinya akan ditemukan sebuah match length (len) dari data tersebut. Dalam penelitian ini data dibedakan berdasarkan dua faktor yaitu jenis file dan ukuran file (bytes). Jenis file yang diujicobakan terdiri dari lima jenis file dengan ekstensi yang berbeda yaitu .c, .txt, .exe, .h, dan.doc. Untuk file berekstensi doc dibedakan menjadi dua file yaitu file bahasa Indonesia dan file bahasa Inggris. Ukuran dari masing-masing file dibedakan menjadi tiga bagian yaitu < 10000, 10000 - 60000, dan > 60000 bytes, yang masing-masing file dilakukan pengulangan sebanyak 2 kali. Secara keseluruhan ada 32 file yang diujicobakan dalam penelitian ini. Program pemampatan file dengan menggunakan metode LZSS ini dikembangkan dengan menggunakan Turbo C dan output dari sistem ini berupa file terkompresi yang disimpan dalam file .car. Hasil dekompresi dikembalikan ke bentuk asalnya melalui program dekompresi yang dikembangkan oleh Nelson dan Gailly (1996), dengan perbandingan antara file hasil dekompresi dengan file asli adalah sama. Pada setiap percobaan dilakukan pengamatan terhadap kebutuhan ruang penyimpanan, penghitungan blok CRC-32, dan analisis kompleksitas program. Hasil dari penelitian menunjukkan bahwa rasio pemampatan untuk kelima jenis file berbeda-beda tergantung jenis dan ukuran file. Rasio pemampatan yang rendah dihasilkan dari file berekstensi .exe, berkisar antara 24% 59%, dengan rata-rata rasio pemampatannya yaitu 42.67%. Hal ini disebabkan file .exe merupakan file aplikasi. Sedangkan rasio pemampatan yang tinggi dihasilkan dari file berekstensi .h, berkisar antara 64% - 85%, dengan rata-rata rasio pemampatannya yaitu 74.67%, disebabkan pada file .h terjadi penggunaan syntaks yang berulang. Rata-rata rasio pemampatan untuk file yang berekstensi .txt dengan menggunakan metode LZSS yaitu 63.32%, sedangkan dengan metode Huffman 43.72% dan metode LZW 50.6%. Setiap file yang liujicobakan memiliki CRC-32 yang unik. Kompleksitas algoritma untuk LZSS dihitung berdasarkan waktu terburuk yaitu O(n³), sedangkan untuk Huffman O(n + a²) dan LZW O(n).