EVALUASI KINERJA ALGORITMA LEMPEL-ZIV STORER SZYMANSKI TERHADAP DATA TEKS DAN GAMBAR
LAPORAN TUGAS AKHIR
JUDUL
Prima Even Ramadhan 13203076/Teknik Telekomunikasi
PROGRAM STUDI TEKNIK ELEKTRO SEKOLAH TEKNIK ELEKTRO DAN INFORMATIKA INSTITUT TEKNOLOGI BANDUNG 2007
HALAMAN PENGESAHAN
ii
ABSTRAK Perkembangan dunia yang menuju ke arah serba dijital menghadirkan suatu trend baru dengan bermunculannya file-file teks yang berukuran besar seperti ebook dan jurnal elektronik. Algoritma Lempel-Ziv Storer Szymanski (LZSS) merupakan suatu bentuk algoritma yang cocok untuk kompresi jenis file tersebut. Algoritma ini bekerja berdasarkan suatu prinsip kompresi yang disebut dengan string compression. Prinsip ini menyebabkan algoritma tersebut dapat bekerja sangat baik ketika digunakan untuk kompresi file dengan ukuran besar, khususnya file yang berbentuk teks karena akan banyak sekali terjadi match dalam proses encoding-nya. Dengan dasar demikian, maka penulis tertarik untuk melakukan evaluasi secara umum terhadap algoritma LZSS, yang dilakukan dengan cara membandingkan hasil kompresi algoritma tersebut terhadap hasil dari program-program kompresi existing yang banyak digunakan (terutama program Pack dan Compress yang banyak digunakan pada UNIX), serta mencari bentuk-bentuk file teks dan gambar yang akan memberikan hasil kompresi yang baik ketika dikompresi dengan menggunakan algoritma LZSS Evaluasi
kinerja
algoritma
tersebut
dilakukan
dengan
cara
mengimplementasikan algoritma LZSS menjadi sebuah program yang dibuat menggunakan bahasa Java. Kemudian program tersebut dicoba untuk melakukan kompresi terhadap data training set yang telah ditentukan. Hasil yang diperoleh menunjukkan bahwa secara umum algoritma LZSS menduduki posisi pertengahan ketika diperbandingkan dengan program kompresi lain. Algoritma LZSS memiliki rasio kompresi terbaik sebesar 12% untuk data teks maupun gambar.
Kata Kunci: kompresi, algoritma LZSS, Java.
iii
ABSTRACT The world’s development into the digital era has produced an emerging trend with the use of huge size text files as ebooks or electronic journals. The Lempel-Ziv Storer Szymanski (LZSS) is a type of compression algorithm that is suitable to compress those kinds of files. This algorithm works based on a principle which is called string compression. This principle made LZSS algorithm works very well when used to compress huge size files, especially text files. This happens because in big files, the occurrence of matching between the dictionary buffer and the look-ahead buffer would be very often during the encoding process. Based on these facts, the writer is interested to do a general evaluation of the algorithm which is done by comparing its compression ratio to the compression ratio of the existing compression programs (especially Pack and Compress, which are used in UNIX). The optimum type of text files and images are also evaluated in this Final Project. The evaluation is carried by implementing the LZSS algorithm into a program using Java programming language. The program made then is used to compress the selected data training set. The overall results show that the algorithm is often ranked in the middle of the table when compared to the existing compression programs. Also, for the optimum file type, the algorithm gets the best compression ratio of 12% for both text and image.
Keywords: compression, LZSS algorithm, Java
iv
KATA PENGANTAR Segala puji dan syukur saya ucapkan bagi Allah Subhanahu wa Ta’ala, sholawat dan salam semoga selalu tercurah kepada Rasulullah Shalallahu ‘alaihi wa sallam. Tanpa karunia dan rahmat Allah Subhanahu wa Ta’ala tidak mungkin laporan Tugas Akhir ini dapat diselesaikan. Laporan Tugas Akhir ini dibuat dengan tujuan untuk memenuhi prasyarat kelulusan menjadi Sarjana Teknik Elektro. Laporan Tugas Akhir ini berisi penjelasan tentang suatu algoritma yang memiliki potensi yang sangat besar untuk kompresi file teks dengan ukuran tertentu yang saat ini banyak digunakan di dunia dijital. Pada kesempatan ini penulis ingin mengucapkan terima kasih yang sebesarbesarnya kepada : 1. Ibu, Bapak, dan Adik-Adik tercinta yang tiada hentinya memberikan dukungan kepada penulis untuk menyelesaikan studi di Teknik Elektro ITB dengan baik, 2. Bapak Dr. Hendrawan selaku pembimbing Tugas Akhir ini yang selalu membantu penulis dalam mengerjakan Tugas Akhir ini, 3. Humala, paman yang selalu memberikan semangat kepada penulis, 4. Andi, yang telah memberikan ide bagi penulis mengenai Tugas Akhir ini, 5. Deny dan Novi, teman yang selalu membantu penulis dalam mengerjakan Tugas Akhir ini, 6. Seluruh teman-teman Teknik Elektro yang telah membantu Penulis dalam menyelesaikan Tugas Akhir ini. Penulis laporan Tugas Akhir ini menyadari sepenuhnya bahwa laporan Tugas Akhir ini bukanlah merupakan sebuah karya sempurna karena kesempurnaan hanyalah milik Allah Subhanahu wa Ta’ala. Dan penulis menyadari bahwa karya yang dihasilkan dari Tugas Akhir ini masih sangat perlu mengalami pengembangan dan penyempurnaan
v
lebih lanjut. Oleh karena itu, saran dan kritik yang membangun sangat diharapkan penulis. Penulis berharap agar karya yang dihasilkan oleh Tugas Akhir ini menjadi karya yang dapat memberikan manfaat bagi penulis sendiri, kedua orang tua penulis, bagi kampus ITB, dan bagi bangsa Indonesia pada umumnya.
Penulis,
Prima Even Ramadhan
vi
DAFTAR ISI JUDUL .................................................................................................................. i HALAMAN PENGESAHAN ............................................................................. ii ABSTRAK .......................................................................................................... iii ABSTRACT ........................................................................................................ iv KATA PENGANTAR ..........................................................................................v DAFTAR ISI...................................................................................................... vii DAFTAR GAMBAR ............................................................................................x DAFTAR TABEL ............................................................................................... xi BAB I PENDAHULUAN .....................................................................................1 1.1 Latar Belakang ................................................................................................1 1.2 Perumusan Masalah ....................................................................................2 1.3 Tujuan Penelitian ........................................................................................2 1.4 Batasan Masalah .........................................................................................2 1.5 Metodologi Penelitian .................................................................................3 1.6 Sistematika Penulisan .................................................................................3 BAB II TEKNIK KOMPRESI DATA .................................................................5 2.1 Pendahuluan ....................................................................................................5 2.1.1 Kompresi Lossless ...............................................................................5 2.1.2 Kompresi Lossy ...................................................................................5 2.2 Teknik Dictionary Coding ..........................................................................6 2.2.1 Algoritma Lempel-Ziv 77 ....................................................................6 2.2.2 Algoritma Lempel Ziv Storer Szymanski ............................................8 2.2.2.1 Perbedaan LZSS Dengan Algoritma LZ77 ...................................9 2.2.1.1.1 Penggunaan Circular queue ...................................................9 2.2.2.1.2 Penggunaan Binary-Search Tree .........................................10 2.2.2.1.3 Perbedaan Dalam Penggunaan Token .................................10 2.2.2.2 Contoh Kasus Operasi Algoritma LZSS .....................................11 2.2.3 Algoritma Lempel-Ziv 78 ..................................................................13 2.2.4 Algoritma Lempel-Ziv Welch............................................................16 2.3 Huffman Coding .......................................................................................20 2.4 Data Training Set ......................................................................................22 2.4.1 Corpus ................................................................................................23 2.4.1.1 Calgary Corpus ...........................................................................23 2.4.1.2 Canterbury Corpus ......................................................................25 2.4.3 Data Dari Archieve Comparison Test ................................................25
vii
2.4.3.1 Kompresi Teks ............................................................................26 2.4.3.2 Kompresi TIFF............................................................................26 2.3.4 Data Milik Penulis .............................................................................28 2.3.4.1 File Teks......................................................................................28 2.3.4.2 File Gambar ................................................................................29 2.4 Program Kompresi Existing......................................................................29 2.5.1 WinZip ...............................................................................................30 2.5.2 WinRAR ............................................................................................30 2.5.3 Compress............................................................................................30 2.5.4 Gzip ....................................................................................................31 2.5.5 Prediction by Partial Matching ..........................................................31 2.5.6 Pack ....................................................................................................31 BAB III IMPLEMENTASI ALGORITMA LZSS .............................................33 3.1 Program Implementasi LZSS ........................................................................33 3.2 Pemilihan Algoritma LZSS ......................................................................33 3.3 Prosedur ....................................................................................................34 BAB IV EVALUASI KINERJA ALGORITMA LZSS .....................................36 4.1 Kompresi Maksimal Algoritma LZSS ......................................................36 4.1.1 Kompresi Maksimal Data Teks .........................................................36 4.1.2 Kompresi Maksimal Data Gambar ....................................................38 4.2 Hasil Kompresi Calgary Corpus ...............................................................40 4.2.1 Evaluasi Hasil ....................................................................................40 4.2.2 Perbandingan Dengan Metode Existing.............................................43 4.3 Hasil Kompresi Canterbury Corpus ..........................................................45 4.3.1 Evaluasi Hasil ....................................................................................45 4.3.2 Perbandingan Dengan Metode Existing.............................................48 4.4 Hasil Kompresi Data Archieve Comparison Test.....................................50 4.4.1 Kompresi Teks ...................................................................................50 4.4.1.1 Evaluasi Hasil .............................................................................50 4.4.1.2 Perbandingan Dengan Metode Existing......................................52 4.4.2 Pengompresian File TIFF ..................................................................53 4.4.2.1 Evaluasi Hasil .............................................................................53 4.4.2.2 Perbandingan Dengan Metode Existing......................................54 4.5 Hasil Kompresi Data Milik Penulis ..........................................................55 4.5.1 Teks ....................................................................................................55 4.5.1.1 Evaluasi Hasil .............................................................................55 4.5.2 Pengompresian File Gambar ..............................................................58 4.5.2.1 Evaluasi Hasil .............................................................................58
viii
BAB V KESIMPULAN DAN SARAN .............................................................62 5.1 Kesimpulan ...............................................................................................62 5.2 Saran .........................................................................................................63 DAFTAR PUSTAKA .........................................................................................64 LAMPIRAN ........................................................................................................65 Pack.java.........................................................................................................65 LZSSoutputstream.java ...................................................................................68 LZSSinputstream.java .....................................................................................76
ix
DAFTAR GAMBAR Contoh proses encoding algoritma LZ77 [1]. ...............................7 Pseudocode algoritma LZSS [8]. ..................................................9 Circular queueI [1] . ...................................................................10 Gambar adalah sebuah binary-search tree [1]. ...........................10 Contoh operasi algoritma LZ78 [8]. ...........................................14 Pseudocode algoritma LZW [8]. .................................................17 Huffman tree. ..............................................................................22 Clegg.TIFF [6]. ...........................................................................27 Frymire.TIFF [6]. ........................................................................27 Lena.TIFF [6]..............................................................................27 Monarch.TIFF [6]. ......................................................................27 Peppers.TIFF [6]. ........................................................................27 Sail.TIFF [6]. ..............................................................................27 Serrano.TIFF [6]. ........................................................................28 Tulips.TIFF [6]. ..........................................................................28 Ilustrasi proses kompresi di lingkungan DOS. ...........................35 Ilustrasi proses dekompresi di lingkungan DOS. ........................35 Grafik rasio kompresi terhadap jumlah input (file teks) yang memberikan kompresi maksimal. ...............................................37 Gambar 4.2. Grafik rasio kompresi terhadap jumlah input (file gambar) yang memberikan kompresi maksimal. ......................................39 Gambar 4.3. Grafik rasio kompresi terhadap jumlah masukkan pada kompresi terhadap Calgary Corpus. ...........................................42 Gambar 4.4. Grafik rasio kompresi terhadap jumlah masukkan pada kompresi terhadap Canterbury Corpus. ......................................47 Gambar 4.5. Grafik rasio kompresi terhadap jumlah masukkan pada kompresi terhadap file teks dari ACT. ........................................51 Gambar 4.6. Rasio kompresi LZSS terhadap jumlah masukkan pada kelompok file teks buku teknik. ..................................................55 Gambar 4.7. Rasio kompresi LZSS terhadap jumlah masukkan pada kelompok file teks buku non-teknik. ...........................................56 Gambar 4.8. Rasio kompresi LZSS terhadap jumlah masukkan pada kelompok file teks artikel bahasa Indonesia. ..............................57 Gambar 4.9. File gambar nomor 9. ..................................................................60 Gambar 4.10. File gambar nomor 11. ................................................................60 Gambar 4.11. File gambar nomor 10. ................................................................61 Gambar 2.1. Gambar 2.2. Gambar 2.3. Gambar 2.4. Gambar 2.5. Gambar 2.6. Gambar 2.7. Gambar 2.8. Gambar 2.9. Gambar 2.10 Gambar 2.11. Gambar 2.12. Gambar 2.13. Gambar 2.14. Gambar 2.15. Gambar 3.1. Gambar 3.2. Gambar 4.1.
x
DAFTAR TABEL Tabel II-1. Tabel II-2. Tabel II-3. Tabel II-4. Tabel II-5. Tabel II-6. Tabel II-7. Tabel IV-1. Tabel IV-2. Tabel IV-3. Tabel IV-4. Tabel IV-5. Tabel IV-6. Tabel IV-7. Tabel IV-8. Tabel IV-9.
Proses pengkodean LZSS [8]. ........................................................12 Contoh proses encoding algoritma LZW [8]. ................................17 Hasil perhitungan peluang kemunculan simbol. ............................21 Daftar file Calgary Corpus ............................................................24 File-File yang digunakan dalam Canterbury Corpus. ...................25 File benchmarking teks yang digunakan ACT ..............................26 Atribut file gambar yang digunakan oleh ACT..............................26 Hasil kompresi LZSS terhadap Calgary Corpus. ..........................40 Perbandingan hasil kompresi LZSS terhadap program kompresi lainnya. ...........................................................................................43 Hasil kompresi LZSS terhadap Canterbury Corpus. .....................45 Perbandingan kompresi LZSS dengan program lainnya. ..............48 Hasil kompresi LZSS terhadap file teks dari ACT. .......................50 Perbandingan hasil kompresi LZSS dengan program lain terhadap file teks ACT. ..................................................................52 Hasil kompresi file TIFF. ...............................................................53 Perbandingan hasil kompresi terhadap file gambar ACT. .............54 Hasil kompresi terhadap file gambar milik penulis. ......................59
xi
