STUDI PERBANDINGAN KINERJA ALGORITMA KOMPRESI LEMPEL ZIV 77, LEMPEL ZIV 78 DAN LEMPEL ZIV WELCH PADA FILE TEXT SKRIPSI ANDRE PRATAMA

STUDI PERBANDINGAN KINERJA ALGORITMA KOMPRESI LEMPEL ZIV 77, LEMPEL ZIV 78 DAN LEMPEL ZIV WELCH PADA FILE TEXT

SKRIPSI

ANDRE PRATAMA 051401030

PROGRAM STUDI S1 ILMU KOMPUTER DEPARTEMEN ILMU KOMPUTER FAKULTAS MATEMATIKA DAN ILMU PENGETAHUAN ALAM UNIVERSITAS SUMATERA UTARA MEDAN 2009

Andre Pratama : Studi Perbandingan Kinerja Algoritma Kompresi Lempel Ziv 77, Lempel Ziv 78 Dan Lempel Ziv Welch Pada File Text, 2010.


SKRIPSI Diajukan untuk melengkapi tugas dan memenuhi syarat mencapai gelar Sarjana Komputer ANDRE PRATAMA 051401030

PROGRAM STUDI S1 ILMU KOMPUTER DEPARTEMEN ILMU KOMPUTER FAKULTAS MATEMATIKA DAN ILMU PENGETAHUAN ALAM UNIVERSITAS SUMATERA UTARA MEDAN 2009


ii PERSETUJUAN

Judul

Kategori Nama Nomor Induk Mahasiswa Program Studi Departemen Fakultas

: STUDI PERBANDINGAN KINERJA ALGORITMA KOMPRESI LEMPEL ZIV 77, LEMPEL ZIV 78 DAN LEMPEL ZIV WELCH PADA FILE TEXT : SKRIPSI : ANDRE PRATAMA : 051401030 : SARJANA (S1) ILMU KOMPUTER : ILMU KOMPUTER : MATEMATIKA DAN ILMU PENGETAHUAN ALAM (FMIPA) UNIVERSITAS SUMATERA UTARA Diluluskan di Medan, 17 November 2009

Komisi Pembimbing

:

Pembimbing 2

Pembimbing 1

Syahril Efendi, S.Si, MIT NIP. 196711101996021001

Syahriol Sitorus, S.Si, MIT NIP. 197103101997031004

Diketahui/Disetujui oleh Program Studi S1 Ilmu Komputer Ketua,

Prof. Dr. Muhammad Zarlis NIP. 195707011986011003


iii PERNYATAAN


SKRIPSI

Saya mengakui bahwa skripsi ini adalah hasil kerja saya sendiri, kecuali beberapa kutipan dan ringkasan yang masing-masing disebutkan sumbernya.

Medan, 17 November 2009

Andre Pratama 051401030


iv PENGHARGAAN

Alhamdulillah, puji syukur saya sampaikan kehadirat Allah SWT, yang telah memberikan rahmat dan hidayah-Nya serta segala sesuatunya dalam hidup, sehingga saya dapat menyelesaikan penyusunan skripsi ini, sebagai syarat untuk memperoleh gelar Sarjana Komputer, Program Studi S1 Ilmu Komputer Universitas Sumatera Utara. Shalawat beriring salam saya persembahkan kepada Nabi Besar Muhammad SAW. Ucapan terima kasih saya sampaikan kepada bapak Syahriol Sitorus, S.Si, MIT sebagai Dosen Pembimbing I dan Bapak Syahril Efendi, S.Si, MIT sebagai Dosen Pembimbing II yang telah memberikan bimbingan, saran, dan masukan kepada saya untuk menyempurnakan kajian ini. Panduan ringkas, padat dan profesional telah diberikan kepada saya sehingga saya dapat menyelesaikan tugas ini. Selanjutnya kepada Dosen Penguji Bapak Prof. Dr. Muhammad Zarlis dan Ibu Maya Silvi Lydia, B.Sc.,M.Sc atas saran dan kritikan yang sangat berguna bagi saya. Ucapan terima kasih juga ditujukan kepada Ketua dan Sekretaris Program Studi S1 Ilmu Komputer, Bapak Prof. Dr. Muhammad Zarlis dan Bapak Syariol Sitorus, S.Si,MIT, Dekan dan Pembantu Dekan Fakultas Matematika dan Ilmu Pengetahuan Alam Universitas Sumatera Utara, semua dosen serta pegawai di Program Studi S1 Ilmu Komputer FMIPA USU. Skripsi ini terutama saya persembahkan untuk kedua orang tua dan keluarga saya yang telah memberikan dukungan dan motivasi, ayahanda Alfi Syahrir dan ibunda Maryati yang selalu sabar dalam mendidik saya. Untuk kedua adik saya, Friska Lestari dan Velya Ramadhani yang selalu memberikan dorongan kepada saya selama menyelesaikan skripsi ini. Kepada teman-teman terbaik yang selalu memberikan dukungan, Qori Mutia, Jerry Rahmat, Sarmedi Sitohang, Muhammad Andri, Lipantri Mashur Gultom, Hery Wibowo, Silvina Irwanti, Fadlan, Zulkarnain Lubis, dan Muhammad Husli Khairi. Untuk teman-teman sekelas dan satu angkatan yang sedang berjuang tanpa patah semangat dan tiada pupus harapan. Terima kasih pula kepada semua pihak-pihak yang tidak dapat saya sebutkan satu persatu, terima kasih atas ide, saran, dan kerjasama yang baik. Saya menyadari bahwa skripsi ini masih jauh dari kesempurnaan, oleh karena itu saya menerima saran dan kritik yang bersifat membangun demi kesempurnaan skripsi ini. Sehingga dapat bermanfaat bagi kita semuanya.


v

ABSTRAK

Meningkatnya penggunaan komputer dalam kegiatan sehari-hari, secara tidak langsung juga membuat kebutuhan akan penyimpanan data semakin meningkat. Semakin besar data, semakin besar ruang yang dibutuhkan dan semakin lama waktu yang diperlukan untuk mengirimkan data. Untuk mengatasinya, telah dikembangkan berbagai algoritma kompresi yang digunakan untuk memampatkan data. Diantaranya, terdapat 3 algoritma kompresi yang menggunakan metoda dictionary : LZ77, LZ78 dan LZW. Ketiga algoritma dibandingkan untuk mengetahui algoritma mana yang memiliki kinerja tertinggi dalam memampatkan file text. Parameter kinerja diukur dari kompleksitas algoritma, rasio kompresi, dan berapa lama waktu yang diperlukan untuk proses kompresi. File yang diuji meliputi *.txt, *.doc, *.rtf, dan *.html. Setelah dianalisis dan diimplementasikan ke dalam program PHP, diperoleh bahwa algoritma LZ77 memiliki kompleksitas tertinggi. Algoritma LZW unggul dalam rasio kompresi file *.txt. Untuk file *.doc, *.rtf, dan *.html rasio kompresi terbaik diperoleh algoritma LZ77, tetapi algoritma LZ77 memerlukan waktu paling lama untuk hampir semua file uji.


vi

STUDY OF PERFORMANCE COMPARISON LEMPEL ZIV 77, LEMPEL ZIV 78 AND LEMPEL ZIV WELCH COMPRESSION ALGORITHM ON TEXT FILE

ABSTRACT

The increasing use of computers in daily activities, indirectly also makes the need for increased data storage. The bigger the data, the greater the space required and the longer time required to transmit data. To overcome this problem, has been developed a variety of compression algorithm used to compress the data. Among them, there are 3 compression algorithm that uses dictionary method: LZ77, LZ78 and LZW. All three algorithms is compared to determine which algorithm has the highest performance to compress text file. Performance is measured by complexity of the algorithm, compression ratio, and how much time is needed in compression process. Files that are tested include *. txt, *. doc, *. rtf, and *. html. Having analyzed and implemented into a PHP program, LZ77 algorithm has the highest complexity. LZW algorithm has the best compression ratio in *. txt files. For *. doc, *. rtf, and *. html file, the best compression ratio is obtained by LZ77 algorithm, but the LZ77 algorithm takes the longest time for almost all test files.


vii

DAFTAR ISI

Halaman Persetujuan Pernyataan Penghargaan Abstrak Abstract Daftar Isi Daftar Tabel Daftar Gambar Bab 1 Pendahuluan 1.1 Latar Belakang 1.2 Rumusan Masalah 1.3 Batasan Masalah 1.4 Tujuan Penelitian 1.5 Manfaat Penelitian 1.6 Diagram Konsepsi 1.7 Metodologi Penelitian 1.8 Sistematika Penulisan Bab 2 Landasan Teori 2.1 Definisi dan Klasifikasi Algoritma Kompresi Data 2.2 Algoritma Lempel Ziv 77 2.3 Algoritma Lempel Ziv 78 2.4 Algoritma Lempel Ziv Welch 2.5 Kompleksitas Algoritma dan Notasi O-besar (big O) Bab 3 Perancangan Sistem 3.1 Perancangan Fungsi 3.1.1 Perancangan Fungsi Dasar 3.1.1.1 Fungsi Konversi Bilangan Desimal ke Bilangan Biner 3.1.1.2 Fungsi Konversi Bilangan Biner ke Bilangan Desimal 3.1.1.3 Fungsi Pemotongan String 3.1.1.4 Fungsi Zero Left Pad 3.1.1.5 Fungsi Zero Right Pad 3.1.2 Perancangan Fungsi Khusus 3.1.2.1 Fungsi Bit Stream to String 3.1.2.2 Fungsi String to Bit Stream 3.2 Perancangan Algoritma Kompresi 3.2.1 Algoritma LZ77 3.2.1.1 Algoritma LZ77 Encoding 3.2.1.2 Algoritma LZ77 Decoding 3.2.2 Algoritma LZ78 3.2.2.1 Algoritma LZ78 Encoding 3.2.2.2 Algoritma LZ78 Decoding 3.2.3 Algoritma LZW

ii iii iv v vi vii ix xi 1 1 2 2 2 3 3 4 5 6 6 8 11 14 16 24 24 24 25 26 27 27 28 29 29 31 32 32 34 40 44 46 51 55


viii

Algoritma LZW Encoding 3.2.3.2 Algoritma LZW Decoding 3.3 Pengukuran Kecepatan Algoritma 3.4 Pengukuran Rasio Kompresi 3.5 Perancangan Aplikasi 3.5.1 Data Flow Diagram dan Kamus Data 3.5.1.1 Data Flow Diagram Proses Kompresi 3.5.1.2 Data Flow Diagram Proses Dekompresi 3.5.1.3 Kamus Data 3.5.2 Perancangan Interface 3.6 Implementasi Sistem 3.6.1 Halaman Home 3.6.2 Halaman Upload File Kompresi 3.6.3 Halaman Pilih Algoritma Kompresi 3.6.4 Halaman Pengaturan Parameter Kompresi LZ77 3.6 5 Halaman Pengaturan Parameter Kompresi LZ78 3.6.6 Halaman Bandingkan Algoritma 3.6.7 Halaman Upload File Dekompresi 3.6.8 Halaman Pengaturan Parameter Dekompresi Bab 4 Analisa dan Pengujian Sistem 4.1 Analisa Perbandingan Kompleksitas Algoritma 4.1.1 Kompleksitas Proses Kompresi 4.1.2 Kompleksitas Proses Dekompresi 4.2 Pengujian Implementasi Algoritma dan Analisa Hasil 4.2.1 Perangkat Pengujian 4.2.2 File Pengujian 4.2.3 Pengujian Parameter Algoritma 4.2.3.1 Pengujian Parameter Algoritma LZ77 4.2.3.2 Pengujian Parameter Algoritma LZ78 4.2.3.3 Pengujian Parameter Algoritma LZW 4.2.4 Pengujian Algoritma 4.2.4.1 Pengujian File Plain Text ASCII (*.txt) 4.2.4.2 Pengujian File Microsoft Word Document (*.doc) 4.2.4.3 Pengujian File Rich Text Format (*.rtf) 4.2.4.4 Pengujian File hipertext markup language (*.htm/*.html) Bab 5 Kesimpulan dan Saran 5.1 Kesimpulan 5.2 Saran Daftar Pustaka

57 62 66 68 68 68 69 71 73 74 81 81 82 83 83 86 87 89 89 91 91 91 92 93 94 94 97 97 100 101 103 103 105 108 110 114 114 115 116


ix

DAFTAR TABEL

Halaman

Tabel 2.1 Tabel 2.2 Tabel 2.3 Tabel 2.4 Tabel 2.5 Tabel 2.6 Tabel 2.7 Tabel 2.8 Tabel 2.9 Tabel 2.10 Tabel 2.11 Tabel 2.12 Tabel 2.13 Tabel 2.14 Tabel 3.1 Tabel 3.2 Tabel 3.3 Tabel 3.4 Tabel 3.5 Tabel 3.6 Tabel 3.7 Tabel 3.8 Tabel 3.9 Tabel 3.10 Tabel 3.11 Tabel 3.12 Tabel 3.13 Tabel 3.14 Tabel 3.15 Tabel 3.16 Tabel 3.17 Tabel 3.18 Tabel 3.19 Tabel 3.20 Tabel 3.21 Tabel 3.22 Tabel 4.1 Tabel 4.2 Tabel 4.3 Tabel 4.4 Tabel 4.5 Tabel 4.6

Algoritma Dasar LZ77 Encoding Algoritma Dasar LZ77 Decoding Contoh Cara Kerja Algoritma LZ78 Algoritma Dasar LZ78 Encoding Algoritma Dasar LZ78 Decoding Algoritma Dasar LZW Encoding Contoh Cara Kerja Algoritma LZW Algoritma Dasar LZW Decoding Perbandingan Pertumbuhan Kompleksitas (Growth Rates) Algoritma Konversi Suhu Algoritma Bilangan Ganjil atau Genap Algoritma Perulangan Sederhana Algoritma Perulangan Sederhana Perbandingan Pertumbuhan Kompleksitas Algoritma Fungsi Konversi Bilangan Desimal ke Bilangan Biner Algoritma Fungsi Konversi Bilangan Biner ke Bilangan Desimal Algoritma Fungsi Pemotongan String Algoritma Fungsi Zero Left Pad Algoritma Fungsi Zero Right Pad Algoritma Fungsi Bit stream to String Algoritma Fungsi String to Bit Stream Algoritma LZ77 Encoding Algoritma LZ77 Decoding Algoritma Fungsi Dalam Array LZ78 Algoritma Fungsi Cari Array LZ78 Algoritma LZ78 Encoding Algoritma LZ78 Decoding Algoritma Dalam Array LZW Algoritma Cari Array LZW Algoritma LZW Encoding Algoritma LZW Decoding Spesifikasi Proses DFD Kompresi Level 0 Spesifikasi Proses DFD Kompresi Level 1 Spesifikasi Proses DFD Dekompresi Level 0 Spesifikasi Proses DFD Dekompresi Level 0 Kamus Data Perbandingan Kompleksitas Kompresi 1 Perbandingan Kompleksitas Kompresi 2 Perbandingan Kompleksitas Dekompresi 1 Perbandingan Kompleksitas Dekompresi 2 File Uji Plain Text ASCII File Uji Microsoft Word Document

9 11 12 13 13 14 15 16 17 19 20 20 20 22 25 26 27 28 29 30 31 35 41 47 47 48 53 57 58 60 64 69 70 71 72 73 91 92 92 93 95 95


x

Tabel 4.7 Tabel 4.8 Tabel 4.9 Tabel 4.10 Tabel 4.11 Tabel 4.12 Tabel 4.13 Tabel 4.14 Tabel 4.15 Tabel 4.16 Tabel 4.17 Tabel 4.18 Tabel 4.19

File Uji Rich Text Format File Uji Hipertext Markup Language Hasil Pengujian Parameter Algoritma LZ77 Hasil Pengujian Parameter Algoritma LZ78 Hasil Pengujian Parameter Algoritma LZW Rasio Kompresi File *.txt Lama Proses File *.txt Rasio Kompresi File *.doc Lama Proses File *.doc Rasio Kompresi File *.rtf Lama Proses File *.rtf Rasio Kompresi File *.htm/*.html Lama Proses File *.htm/*.html

96 96 98 100 101 103 104 106 107 108 109 111 112


xi

DAFTAR GAMBAR

Halaman

Gambar 1.1 Gambar 2.1 Gambar 2.2 Gambar 2.3 Gambar 2.4 Gambar 3.1 Gambar 3.2 Gambar 3.3 Gambar 3.4 Gambar 3.5 Gambar 3.6 Gambar 3.7 Gambar 3.8 Gambar 3.9 Gambar 3.10 Gambar 3.11 Gambar 3.12 Gambar 3.13 Gambar 3.14 Gambar 3.15 Gambar 3.16 Gambar 3.17 Gambar 3.18 Gambar 3.19 Gambar 3.20 Gambar 3.21 Gambar 3.22 Gambar 3.23 Gambar 3.24 Gambar 3.25 Gambar 3.26 Gambar 3.27 Gambar 3.28 Gambar 3.29 Gambar 3.30 Gambar 3.31 Gambar 3.32 Gambar 3.33 Gambar 3.34 Gambar 3.35 Gambar 3.36 Gambar 3.37

Diagram Konsepsi Contoh Cara Kerja Algoritma LZ77 Bagian 1 Contoh Cara Kerja Algoritma LZ77 Bagian 2 Urutan Spektrum Kompleksitas Waktu Algoritma Grafik Perbandingan Pertumbuhan Kompleksitas Konversi token ke bit stream algoritma LZ77 Konversi bit stream ke token algoritma LZ77 Flowchart Algoritma LZ77 Encoding Proses Pencarian Pola Karakter LZ77 Flowchart Algoritma LZ77 Decoding Proses Decoding Token Algoritma LZ77 Konversi Token Ke Bit Stream Algoritma LZ78 Konversi bit stream ke token algoritma LZ78 Flowchart Algoritma LZ78 Encoding Flowchart Algoritma LZ78 Decoding Konversi Token Ke Bit Stream Algoritma LZW Konversi Bit Stream Ke Token Algoritma LZW Flowchart Algoritma LZW Encoding Flowchart Algoritma LZW Decoding Pengukuran Kecepatan Algoritma Data Flow Diagram Proses Kompresi Level 0 Data Flow Diagram Proses Kompresi Level 1 Data Flow Diagram Proses Dekompresi Level 0 Data Flow Diagram Proses Dekompresi Level 1 Struktur Perancangan Halaman Website Tampilan Rancangan Halaman Home Tampilan Rancangan Halaman Upload File Source Kompresi Tampilan Rancangan Halaman Pilih Algoritma Kompresi Tampilan Rancangan Halaman Pengaturan Parameter Algoritma Tampilan Rancangan Halaman Upload File Dekompresi Tampilan Rancangan Halaman Pengaturan Parameter Dekompresi Tampilan Halaman Home Tampilan Halaman Upload File Kompresi Tampilan Halaman Pilih Algoritma Kompresi Tampilan Halaman Pengaturan Parameter Kompresi LZ77 Tampilan Hasil Kompresi LZ77 Tampilan Halaman Pengaturan Parameter Kompresi LZ78 Tampilan Hasil Kompresi LZ78 Tampilan Halaman Bandingkan Algoritma Tampilan Halaman Upload File Dekompresi Tampilan Pengaturan Parameter Dekompresi Tampilan Hasil Dekompresi

3 10 10 23 23 33 33 34 38 41 43 45 45 46 52 56 56 59 63 67 69 70 71 72 74 75 76 76 78 79 80 82 82 83 84 85 86 87 88 89 89 90


xii

Gambar 4.1 Gambar 4.2 Gambar 4.3 Gambar 4.4 Gambar 4.5 Gambar 4.6 Gambar 4.7 Gambar 4.8 Gambar 4.9 Gambar 4.10 Gambar 4.11 Gambar 4.12 Gambar 4.13 Gambar 4.14 Gambar 4.15 Gambar 4.16 Gambar 4.17

Grafik Rasio Kompresi Parameter Algoritma LZ77 Grafik Rasio Kompresi Parameter Algoritma LZ78 Grafik Lama Proses Kompresi Parameter Algoritma LZ78 Grafik Rasio Kompresi Parameter Algoritma LZW Grafik Lama Proses Kompresi Parameter Algoritma LZW Grafik Rasio Kompresi File *.txt Grafik Lama Proses Kompresi File *.txt Grafik Performa File *.txt Grafik Rasio Kompresi File *.doc Grafik Lama Proses Kompresi File *.doc Grafik Performa File *.doc Grafik Rasio Kompresi File *.rtf Grafik Lama Proses Kompresi File *.rtf Grafik perbandingan Performa File *.rtf Grafik Rasio Kompresi File *.html Grafik Lama Proses Kompresi File *.html Grafik Perbandingan Performa Kompresi File *.html

99 100 101 102 102 104 105 105 106 107 108 109 110 110 111 112 113


BAB 1

PENDAHULUAN

1.1 Latar Belakang

Meningkatnya penggunaan komputer dalam kegiatan sehari-hari, secara tidak langsung juga membuat kebutuhan akan penyimpanan data semakin meningkat. Data tersebut, dapat berupa file text, gambar, suara, dan video. Semakin besar ukuran file, semakin besar pula tempat penyimpanan yang dibutuhkan. Untuk keperluan pengiriman data melalui media transmisi, akan semakin lama juga waktu yang dibutuhkan

untuk

mengirimkan

data

tersebut.

Oleh

karena

itu,

mulailah

dikembangkan algoritma-algoritma kompresi yang bertujuan untuk memampatkan data.

Kompresi data adalah ilmu atau seni merepresentasikan informasi dalam bentuk yang lebih compact. (Ida Mengyi Pu, 2006). Berbagai algoritma telah dikembangkan untuk keperluan kompresi data. Namun, algoritma tersebut sebahagian besar lebih efisien digunakan untuk tipe data tertentu saja. Misalnya untuk kompresi text, terdapat algoritma Huffman, Ziv and Lempel 77 (LZ77), Ziv and Lempel 78 (LZ78), Lempel Ziv Welch (LZW), Dinamic Markov Compression (DMC), Run Length Encoding (RLE) dan lain-lain.

Dalam tugas akhir ini, akan dibandingkan tiga algoritma kompresi : Ziv and Lempel 77 (LZ77), Ziv and Lempel 78 (LZ78), dan Lempel Ziv Welch (LZW), yang semuanya memakai metode kompresi dictionary. Ketiga algoritma ini dipilih karena merupakan algoritma dasar dan algoritma yang populer untuk metode kompresi dictionary. Banyak variasi algoritma lainnya dikembangkan dari algoritma dasar ini. Andre Pratama : Studi Perbandingan Kinerja Algoritma Kompresi Lempel Ziv 77, Lempel Ziv 78 Dan Lempel Ziv Welch Pada File Text, 2010.

2

Algoritma LZW memberikan hasil kompresi yang buruk untuk file multimedia, seperti gambar, suara dan video (Linawati dan Panggabean, H.P., 2004). Karena Algoritma LZ77 dan LZ78 menggunakan konsep yang relatif sama, implementasi akan dilakukan hanya untuk file text.

Dalam menentukan algoritma yang tepat, ada 3 faktor yang akan dipertimbangkan, yaitu: kompleksitas algoritma, waktu yang dibutuhkan untuk melakukan kompresi, dan rasio perbandingan file hasil kompresi.

1.2 Rumusan Masalah

Permasalahan yang akan diteliti dan diuraikan dalam tugas akhir ini adalah: 1.

Bagaimana perbandingan kompleksitas algoritma antara LZ77, LZ78, dan LZW.

2.

Algoritma mana yang lebih efisien, dilihat dari waktu yang diperlukan untuk kompresi dan dekompresi file, serta rasio perbandingan antara file hasil kompresi dengan file sebelum dikompresi.

1.3 Batasan Masalah

Batasan-batasan masalah dalam penelitian ini adalah: 1.

Jenis file yang akan dikompresi adalah file plain text ASCII (.txt), microsoft word document (.doc), rich text format (.rtf) dan hipertext markup language (.html).

2.

Studi perbandingan kinerja yang dilakukan mencakup kompleksitas, waktu yang diperlukan, dan rasio perbandingan kompresi file.

3.

Pengukuran kompleksitas dilakukan dengan perbandingan notasi Big O.

4.

Aplikasi untuk implementasi algoritma dibuat menggunakan bahasa pemograman PHP dan JavaScript.

1.4 Tujuan Penelitian Tujuan dari penelitian ini adalah: 1. Mengetahui algoritma mana yang lebih efektif dalam mengkompresi file text, 2. Mengembangkan aplikasi sebagai bentuk implementasi dari algoritma kompresi LZ77, LZ78, dan LZW. Andre Pratama : Studi Perbandingan Kinerja Algoritma Kompresi Lempel Ziv 77, Lempel Ziv 78 Dan Lempel Ziv Welch Pada File Text, 2010.

3

3. Dengan aplikasi yang dikembangkan, ukuran file text dapat dikompresi menjadi lebih kecil, sehingga mengefisiensikan penggunaan memori penyimpanan. 1.5 Manfaat Penelitian Dengan membandingkan 3 algoritma ini, dapat diambil manfaat algoritma mana yang lebih baik dalam melakukan kompresi file text, dan kelebihan serta kekurangan masing-masing algoritma. Selain itu, dengan membandingkan konsep-konsep dalam ketiga algoritma ini dapat dilihat bagaimana proses perancangan algoritma yang lebih baik, karena ketiga algoritma ini merupakan bentuk perbaikan dari algoritma sebelumnya. 1.6 Diagram Konsepsi Konsep kerja studi perbandingan ketiga algoritma ini adalah sebagai berikut:

Algoritma Kompresi

Algoritma LZ77

Mengukur kompleksitas algoritma LZ77

Algoritma LZ78

Algoritma LZW

Mengukur kompleksitas algoritma LZ78

Mengukur kompleksitas algoritma LZW

Implementasi ke dalam program komputer Kompresi dan dekompresi file text ketiga algoritma

Analisa dan bandingkan hasil kompresi ketiga algoritma Gambar 1.1 Diagram Konsepsi


4

1.7 Metodologi Penelitian

Metodologi penelitian yang akan digunakan adalah: 1. Studi Literatur Dengan melakukan studi literatur, penulis mempelajari teori tentang algoritma kompresi dari berbagai sumber, seperti buku, artikel, jurnal, dan situs-situs internet. Selain itu juga mempelajari beberapa teori lainnya yang dirasakan perlu. 2. Merancang Desain Sistem Desain yang akan dirancang adalah struktur program yang akan digunakan untuk implementasi algoritma kompresi LZ77, LZ78, dan LZW. 3. Implementasi Sistem Sistem

akan

diimplementasikan

dalam

bentuk

aplikasi

berbasis

web

menggunakan bahasa pemograman PHP dan JavaScript. 4. Pengujian dan Analisa Sistem Pengujian ini mencakup apakah implementasi telah sesuai dengan teori, atau apakah program mengalami kesalahan. Perbaikan program akan dilakukan jika ditemukan kesalahan. 5. Dokumentasi Sistem Pembuatan dokumentasi sistem, lengkap dengan analisis yang telah diperoleh.

1.8 Sistematika Penulisan

Sistematika penulisan dari skripsi ini terdiri dari beberapa bagian utama sebagai berikut:

BAB I . PENDAHULUAN Bab ini akan menjelaskan mengenai latar belakang masalah yang dibahas dalam skripsi ini, rumusan masalah, batasan masalah, tujuan penelitian, manfaat penelitian, metode penelitian, dan sistematika penulisan skripsi.


5

BAB II. LANDASAN TEORI Bab ini merupakan tinjauan teoritis yang berkaitan dengan algoritma kompresi, algoritma LZ77, LZ78 dan LZW, serta membahas teori Big O yang akan digunakan untuk membandingkan kompleksitas ketiga algoritma.

BAB III. PERANCANGAN DAN IMPLEMENTASI SISTEM Dalam bab ini akan dibahas tentang perancangan untuk ketiga algoritma, pembuatan psoude code untuk masing-masing algoritma dan menghitung kompleksitasnya. Lalu diimplementasikan dalam bahasa pemograman PHP dan Javascript, beserta fungsifungsi program yang digunakan

BAB IV. ANALISA DAN PENGUJIAN SISTEM Dalam bab ini akan berisi pengujian terhadap program yang sudah diimplementasikan, lalu dilakukan analisa perbandingan kinerja dari ketiga algoritma tersebut.

BAB V. KESIMPULAN DAN SARAN Bab terakhir akan memuat kesimpulan isi dari keseluruhan uraian bab-bab sebelumnya dan saran-saran dari hasil yang diperoleh yang diharapkan dapat bermanfaat dalam pengembangan selanjutnya.


BAB 2

LANDASAN TEORI

Pada bab ini dijelaskan tentang defenisi dan klasifikasi kompresi data, lalu masingmasing teori tentang algoritma Ziv and Lempel 77 (LZ77), Ziv and Lempel 78 (LZ78), dan Lempel Ziv Welch

(LZW). Selanjutnya dibahas teori tentang

pengitungan kompleksitas algoritma menggunakan Big O.

2.1 Definisi dan Klasifikasi Algoritma Kompresi Data

Menurut Ida Mengyi Pu (2006, hal: 1) kompresi data adalah ilmu atau seni merepresentasikan informasi dalam bentuk yang lebih compact. Sedangkan David Salomon (2007, hal: 2) mengatakan bahwa data kompresi adalah proses mengkonversikan sebuah input data stream (stream sumber, atau data mentah asli) menjadi data stream lainnya (bit stream hasil, atau stream yang telah terkompresi) yang berukuran lebih kecil.

Tujuan dari kompresi data adalah untuk merepresentasikan suatu data digital dengan sesedikit mungkin bit, tetapi tetap mempertahankan kebutuhan minimum untuk membentuk kembali data aslinya. Data digital ini dapat berupa text, gambar, suara, dan kombinasi dari ketiganya, seperti video.

Untuk membuat suatu data menjadi lebih kecil ukurannya daripada data asli, diperlukan tahapan-tahapan (algoritma) untuk mengolah data tersebut. Menurut Thomas H. Cormen (2001, hal: 2) algoritma adalah suatu prosedur komputasi yang didefinisikan secara baik, membutuhkan sebuah atau sekumpulan nilai sebagai input, dan menghasilkan sebuah atau sekumpulan nilai sebagai output. Dalam algoritma Andre Pratama : Studi Perbandingan Kinerja Algoritma Kompresi Lempel Ziv 77, Lempel Ziv 78 Dan Lempel Ziv Welch Pada File Text, 2010.

7

kompresi data, tidak ada algoritma yang cocok untuk semua jenis data. Hal ini disebabkan karena data yang akan dimampatkan harus dianalisis terlebih dahulu, dan berharap menemukan pola tertentu yang dapat digunakan untuk memperoleh data dalam ukuran yang lebih kecil. Karena itu, muncul banyak algoritma-algoritma kompresi data.

Secara garis besar, terdapat 2 penggolongan algoritma kompresi data: kompresi lossy, dan kompresi lossless.

a.

Kompresi Lossy Algoritma kompresi dikatakan lossy atau disebut juga irreversible jika tidak dimungkinkan untuk membentuk data asli yang tepat sama dari data yang sudah dikompresi. Ada beberapa detail yang hilang selama proses kompresi. Contoh penggunaan algoritma lossy seperti pada data gambar, suara dan video. Karena cara kerja sistem pengelihatan dan pendengararn manusia yang terbatas, beberapa detail dapat dihilangkan, sehingga didapat data hasil kompresi yang seolah-olah sama dengan data asli.

b.

Kompresi Lossless Algoritma kompresi dikatakan lossless atau disebut juga reversible jika dimungkinkan untuk membentuk data asli yang tepat sama dari data yang sudah dikompresi. Tidak ada informasi yang hilang selama proses kompresi dan dekompresi. Teknik ini digunakan jika data tersebut sangat penting, jadi tidak di mungkinkan untuk menghilangkan beberapa detail.

Untuk kompresi Lossless, berdasarkan cara mereduksi data yang akan dikompresi, terbagi lagi menjadi 2 kelompok besar algoritma:

a.

Algoritma berbasis Entropi Algoritma berbasis Entropi, atau disebut juga berbasis statistik, menggunakan model statistik dan probabilitas untuk memodelkan data, keefisienan kompresi bergantung kepada berapa banyak karakter yang digunakan dan seberapa besar


8

distribusi probabilitas pada data asli. Contoh algoritma yang berbasis entropi adalah: Huffman Coding, Adaptive Huffman, dan Shannon Fano. b.

Algoritma berbasis dictionary Algoritma berbasis dictionary, bekerja dengan cara menyimpan pola masukan sebelumnya, dan menggunakan index dalam mengakses pola tersebut jika terdapat perulangan. Contoh algoritma yang berbasis dictionary adalah: LZ77, LZ78, LZW, DEFLATE, dan LZMA.

Dari beberapa algoritma kompresi berbasis dictionary, LZ77, LZ78, dan LZW adalah yang paling populer. Banyak algoritma lainnya yang merupakan variasi dari tiga algoritma dasar tersebut. Pengembangan algoritma LZ77, LZ78, dan LZW tidak dalam waktu yang sama, algoritma LZ77 dikembangkan pada tahun 1977, LZ78 pada tahun 1978, dan LZW yang merupakan pengembangan dari LZ78, dipublikasikan pada tahun 1984.

Proses kompresi melibatkan 2 buah proses, yaitu proses kompresi (compression) dan dekompresi (decompression). Pada proses kompresi file asli dibaca, lalu dilakukan pengkodean untuk membuat file hasil kompresi. Proses ini disebut juga dengan proses encoding. Untuk memperoleh kembali file asli dari file yang sudah dimampatkan tersebut, proses pengkodean kembali dilakukan. Proses ini disebut juga proses decoding.

2.2 Algoritma Lempel Ziv 77

Algoritma Lempel-Ziv 77 (LZ77), atau dikenal juga dengan LZ1, dipublikasikan dalam sebuah paper oleh Abraham Lempel dan Jacob Ziv pada tahun 1977. Algoritma ini merupakan tipe algoritma lossless. Algoritma LZ77 disebut juga dengan ’sliding windows’, atau jendela berjalan karena proses kerjanya (wikipedia, 2008).

Prinsip dari algoritma ini adalah menggunakan sebahagian input karakter yang telah dikodekan sebelumnya sebagai dictionary (kamus). Bagian input ini seolah-olah diibaratkan dengan sebuah jendela (window) yang dapat digeser dari kiri ke kanan. Jendela ini secara dinamis merupakan dictionary untuk mencari simbol Andre Pratama : Studi Perbandingan Kinerja Algoritma Kompresi Lempel Ziv 77, Lempel Ziv 78 Dan Lempel Ziv Welch Pada File Text, 2010.

9

input dengan pola tertentu. Ketika jendela ini bergerak dari kiri ke kanan, isi dari dictionary dan input karakter yang akan dicari polanya juga akan berubah. Jendela ini dibagi menjadi dua bagian, bagian pertama disebut history buffer (H), atau search buffer, yang berisi sebahagian input karakter yang sudah dikodekan. Jendela kedua adalah lookahead buffer (L), yang berisi sebahagian input karakter yang akan dikodekan. Ukuran dari masing-masing buffer ini telah ditetapkan sebelumnya, dalam implementasinya nanti, history buffer akan memiliki panjang beberapa ribu byte, dan lookahead buffer panjangnya hanya puluhan byte (Salomon, D., 2007 ). Algoritma kompresi LZ77 secara sederhana dapat dilihat pada tabel 2.1, dimana input berupa sebuah string karakter. Output algoritma adalah kumpulan token.

Tabel 2.1 Algoritma Dasar LZ77 Encoding Baris 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29

Pseudo code a ← batasan panjang history_buffer; b ← batasan panjang lookahead_buffer; history_buffer ← ””; lookahead_buffer ← a karakter pertama dari string input; while not EOF do temukan pola karakter terpanjang pada history_buffer yang cocok dengan pola yang terdapat pada lookahead_buffer; l ← jumlah karakter terpanjang yang ditemukan; f ← jarak antara ujung history_buffer dengan karakter yang ditemukan; c ← karakter pertama setelah karakter yang ditemukan; output token (f,l,c); history_buffer ← history buffer + karakter yang sudah dikodekan + c; if ukuran history_buffer > a do hapus beberapa karakter di awal history_buffer supaya tidak melebihi batas a; end if lookahead_buffer←lookahead_buffer + (l+1) karakter berikutnya; if ukuran lookahead_buffer > b do hapus beberapa karakter di awal lookahead_buffer supaya tidak melebihi batas b; end if end while

Sebagai contoh, pada gambar 2.1, H adalah: ”gian_input_yang_dikode kan._Bagian_”, sepanjang 34 byte (1 karakter = 1 byte). Lalu L adalah: ”inputan_ini_merup”, sepanjang 12 byte. Data input karakter pada dan sebelum H Andre Pratama : Studi Perbandingan Kinerja Algoritma Kompresi Lempel Ziv 77, Lempel Ziv 78 Dan Lempel Ziv Welch Pada File Text, 2010.

10

sudah dikodekan sebelumnya, tetapi karakter pada dan sesudah L, adalah yang akan dikodekan. Algoritma LZ77 akan mencari apakah karakter yang terdapat pada jendela L, terdapat juga pada jendela H. Pencarian ini untuk menemukan karakter terpanjang yang cocok dengan karakter yang ada pada jendela L. Kode yang dihasilkan dengan algoritma LZ77 berupa token dengan bentuk (f, l,c). Dimana f adalah jumlah karakter dari ujung jendela H kepada karakter yang ditemukan, dalam contoh ini adalah 29 karakter. Sedangkan l adalah jumlah panjang dari karakter yang ditemukan cocok pada H, dalam contoh ini sepanjang 5 karakter. Dan c adalah karakter pertama setelah karakter yang sudah dikodekan, yaitu ’a’.sehingga token yang dihasilkan adalah (29,5,a). Setelah token (29,5,a), jendela akan bergeser sebanyak 6 karakter, yaitu banyak karakter yang ditemukan + 1, ke kiri. Sehingga tampak seperti gambar 2.2. 29

5

Sebahagian_input_yang_dikodekan._Bagian_inputan_ini_merup

History Buffer

Lookahead Buffer

Gambar 2.1 Contoh Cara Kerja Algoritma LZ77 Bagian 1 8

4

gian_input_yang_dikodekan._Bagian_inputan_ini_merupak

History Buffer

Lookahead Buffer

Gambar 2.2 Contoh Cara Kerja Algoritma LZ77 Bagian 2

Pada tahap ini, dilakukan cara yang sama seperti tahap sebelumnya, algoritma akan mencari apakah karakter yang terdapat pada jendela L, terdapat juga pada jendela H, dan menghasilkan token (8,4,i). Lalu jendela akan bergeser sebanyak 4+1 karakter ke kanan. Langkah ini dilakukan terus menerus sampai akhir dari file. Kumpulan token inilah yang menjadi file terkompresi dari file asli.


11

Dekompresi algoritma LZ77, dilakukan dengan cara membaca semua token hasil kompresi dan mengkodekannya kembali menjadi string asli. Algoritma dasar dekompresi LZ77 dapat dilihat pada tabel 2.2.

Tabel 2.2 Algoritma Dasar LZ77 Decoding Baris 1 2 3 4 5 6 7 8 9 10 11

Pseudo code output ← ””; while not EOF do f ← sub token 1 dari token; l ← sub token 2 dari token; c ← sub token 3 dari token; outlen ← panjang string output; output ← output.ambil sebanyak l karakter dari string output dimulai pada karakter ke (outlen-f).c; end while tampilkan output;

Ukuran dari history buffer dan lookahead buffer merupakan faktor penting dalam kinerja kompresi. Proses pencarian string yang efisien juga mempengaruhi kinerja dari algoritma kompresi LZ77.

2.3 Algoritma Lempel Ziv 78

Algoritma Lempel Ziv 78 (LZ78), dikembangkan 1 tahun setelah LZ77, yaitu pada tahun 1978. Oleh Abraham Lempel dan Jacob Ziv. Karena dipublikasikan oleh pihak yang sama, algoritma ini disebut juga dengan LZ2.

Pada algoritma LZ78, Abraham Lempel dan Jacob Ziv mencoba mengatasi permasalah yang ditemukan pada LZ77, yaitu berkaitan dengan kemampuan dalam menemukan pola karakter. Pada LZ77, algoritma ini tidak dapat menemukan pola karakter, jika karakter tersebut sudah dilewati oleh history buffer. Untuk mengatasinya, algoritma LZ78 dikembangkan dengan cara membuat suatu dictionary yang dapat menyimpan pola secara permanen selama proses pengkodean berlangsung.

Token yang digunakan sebagai index untuk menemukan pola tersebut, berkurang dari 3 menjadi 2 buah. Sebuah token dalam LZ78 berbentuk (f,c). Dimana f


12

adalah pointer yang merujuk pada dictionary dimana pola yang ditemukan, dan c adalah karakter pertama sesudah pola.

Dictionary pada LZ78 dapat dibayangkan sebagai sebuah array. Pada saat proses pengkodean dimulai, array ini kosong. Sewaktu algoritma membaca sebuah karakter input, ia akan mencari dalam array, apakah karakter itu ada pada array atau tidak. Jika tidak ditemukan, karakter itu akan dimasukkan ke dalam array, dan dihasilkan token: (0,c), dimana c adalah karakter yang tidak ditemukan tersebut. Tetapi jika didalam array ditemukan, akan dibuat sebuah string yang bersisi karakter yang ditemukan tadi, disambung dengan karakter berikutnya dari input, dan kembali dicari didalam array, apakah pola ini ada atau tidak. Jika ada, string tadi ditambahkan kembali, sampai tidak ditemukan pola yang sesuai dengan string didalam array. Lalu string ini akan dimasukkan ke dalam array, dan dihasilkan token: (f,c). Dimana f adalah index dari array untuk pola string yang ditemukan, dan c adalah karakter terakhir dari string. Proses ini berlangsung terus menerus sampai akhir file (Pu , Ida M., 2006).

Tabel 2.3 adalah contoh 9 langkah pertama dalam mengkodekan string input : ”ada_beberapa_data_yang_hilang”. Kumpulan token inilah yang menjadi file kompresi pada algoritma LZ78. Salah satu masalah yang ada pada algoritma LZ78, adalah jumlah index, atau besar dari dictionary yang diperlukan. Dictionary ini akan bertambah banyak dengan sangat cepat. Salah satu cara sederhana adalah dengan membuat batas maksimum pada jumlah dictionary. Dan jika batas ini tercapai, algoritma tidak akan memasukkan karakter ke dalam dictionary lagi, tetapi hanya memakai dictionary yang sudah ada.

Tabel 2.3 Contoh Cara Kerja Algoritma LZ78 Index

Isi dictionary

0

null

1

”a”

2

Token

Index Isi dictionary

Token

5

”e”

(0,”e”)

(0,”a”)

6

”be”

(4,”e”)

”d”

(0,”d”)

7

”r”

(0,”r”)

3

”a_”

(1,”_”)

8

”ap”

(1,”p”)

4

”b”

(0,”b”)

9

”a_d”

(3,”d”)


13

Algoritma kompresi LZ78 secara sederhana dapat dilihat pada tabel 2.4, dimana input berupa sebuah string karakter, dan sebuah dictionary dengan index pertama berisi dengan nilai null. Output algoritma adalah kumpulan token.

Tabel 2.4 Algoritma Dasar LZ78 Encoding Baris 1 2 3 4 5 6 7 8 9 10 11

Pseudo code dictionary[0] ← ””; while not EOF do word ← ””; c←baca 1 karakter selanjutnya; while word+c ada dalam dictionary do word←word+c; c ← baca 1 karakter selanjutnya; end while key ← index dictionary untuk word; output (key,c); tambahkan word+c kedalam dictionary pada lokasi yang tersedia; end while

Dekompresi algoritma LZ78, dilakukan dengan cara membaca semua token hasil kompresi dan membuat kembali dictionary yang sama persis seperti proses kompresi. Misalkan (f,c) adalah pasangan token, maka algoritma dekompresi LZ78 dapat dilihat pada tabel 2.5.

Tabel 2.5 Algoritma Dasar LZ78 Decoding Baris 1 2 3 4 5 6 7 8 9 10

Pseudo code dictionary[0] ← ””; baca input dalam bentuk stream token while not EOF stream token do a ← karakter f pada token berikutnya; b ← karakter c pada token berikutnya; word ← isi dictionary pada index ke a; output word.b; tambahkan word.b kedalam dictionary pada lokasi yang tersedia end while

Dibandingkan dengan algoritma LZ77 yang menggunakan 3 karakter untuk 1 token, algoritma LZ78 memakai token yang terdiri dari 2 karakter. Karena keterbatasan sumber daya memori, jumlah dictionary dalam LZ78 akan dibatasi. Sebuah algoritma pencarian untuk array juga merupakan faktor penting dalam kinerja algoritma LZ78.


14

2.4 Algoritma Lempel Ziv Welch

Algoritma Lempel Ziv Welch (LZW), dikembangkan oleh Abraham Lempel, Jacob Ziv, dan Terry Welch. Algoritma ini dipublikasikan pada tahun 1984 oleh Terry Welch. LWZ dirancang sebagai peningkatan dari algoritma LZ78.

Algoritma ini mereduksi jumlah token yang dibutuhkan menjadi 1 simbol saja. Simbol ini merujuk kepada index dalam dictionary. Proses kerjanya mirip dengan algoritma LZ78, tetapi jika pada algoritma LZ78 dictionary dimulai dari keadaan kosong, LZW mengisi dictionary ini dengan seluruh simbol karakter yang akan digunakan. Pada kasus yang umum, 256 index pertama dari dictionary akan diisi dengan karakter ASCII dari 0-255. Karena dictionary telah diisi dengan semua kemungkinan karakter terlebih dahulu, maka karakter input pertama akan selalu dapat ditemukan dalam dictionary. Inilah yang menyebabkan token pada LZW hanya memerlukan 1 simbol saja yang merupakan pointer pada dictionary.

Tabel 2.6 Algoritma Dasar LZW Encoding Baris 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15

Pseudo code word←””; inisialisasi dictionary dengan 256 karakter ASCII; while not EOF do x←baca karakter selanjutnya; if word+x ada dalam dictionary do word←word+x; else output index dictionary untuk word; tambahkan word+x kedalam dictionary pada lokasi yang tersedia; word←x; end if end while output index dictionary untuk word;

Prinsip kerja LZW, dimulai dengan membaca karakter input satu persatu dan diakumulasi pada sebuah string I. Lalu dilakukan pencarian dalam dictionary, apakah terdapat string I. Selama string I ditemukan didalam dictionary, string ini ditambahkan dengan satu karakter berikutnya, lalu dicari lagi dalam dictionary. Pada saat tertentu, menambahkan satu karakter x pada string I akan menyebabkan tidak ditemukan dalam dictionary. String I ditemukan, tetapi string I+x tidak. Dalam tahap Andre Pratama : Studi Perbandingan Kinerja Algoritma Kompresi Lempel Ziv 77, Lempel Ziv 78 Dan Lempel Ziv Welch Pada File Text, 2010.

15

ini, algoritma akan akan menulis index dari string I sebagai output, menambahkan string I+x kedalam dictionary, dan menginisialisasikan string I dengan x, lalu proses dimulai lagi dari awal. Algoritma kompresi LZW secara sederhana dapat dilihat pada tabel 2.6, dimana input berupa sebuah string karakter. Output algoritma adalah kumpulan token.

Sebagai contoh, input adalah string : ”ada_beberapa_data_yang_hilang”. Langkah pertama adalah mengisi dictionary dengan semua kemungkinan karakter, yaitu karakter ASCII dari 0-255, yang berarti index dictionary 0-255 telah berisi. Lalu string I diisi dengan karakter ”a”. Didalam dictionary, karakter ”a” ada pada index ke 97. Lalu string I ditambah dengan karakter selanjutnya ”d”. Frase ”ad” tidak ditemukan, maka akan dihasilkan token 97, dan frase ”ad” ditambahkan pada index ke 256 dalam dictionary. String I sekarang berisi ”d”, karena d ada pada index ke 100, maka string I ditambahkan dengan karakter selanjutnya, menjadi ”da”. Untuk langkah selanjutnya dapat dilihat dari tabel 2.7.

Tabel 2.7 Contoh Cara Kerja Algoritma LZW String I Di dalam dictionary? Entry baru

Output keterangan

a ad d da a a_ _ _b b be e eb b be ber ...

97 100 97 95 98 101 260 ...

ada tidak ada tidak ada tidak ada tidak ada tidak ada tidak ada ada tidak ...

[256] = ad [257] = da [258] = a_ [259] = _b [260] = be [261] = eb [262] = be ...

97 adalah index dari ”a” 100 adalah index dari ”d” 97 adalah index dari ”a” 95 adalah index dari ”_” 98 adalah index dari ”b” 101 adalah index dari ”e”

262 adalah index dari ”be” ...


16

Kumpulan output yang berupa angka-angka inilah sebagai hasil kompresi. Karena menggunakan konsep dictionary yang sama seperti LZ78, pengorganisasian dictionary juga diperlukan, misalnya seperti seberapa besar dictionary yang disediakan, dan apa yang akan dilakukan jika dictionary sudah penuh.

Dekompresi algoritma LZW, dilakukan dengan cara membaca semua token hasil kompresi dan membuat kembali dictionary yang sama persis seperti proses kompresi. Misalkan (x) adalah token hasil proses kompresi, maka algoritma dekompresi LZ78 dapat dilihat pada tabel 2.8.

Tabel 2.8 Algoritma Dasar LZW Decoding Baris 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16

Pseudo code x←baca token x dari file; element←isi dictionary pada index x; output element; word←element; while not EOF do x←baca token x selanjutnya; if tidak ada index ke x pada dictionary then element←word+karakter_pertama_pada_word; else element←isi dictionary pada index x; end if output element; tambahkan word + karakter pertama dari word kedalam dictionary; word←element; end while

Banyak algoritma berbasis dictionary lainnya dikembangkan dari tiga algoritma ini. Misalnya algortima LZMW, LZAP dan LZY adalah variasi dari LZW. Algoritma LZFG yang merupakan gabungan dari LZ77 dan LZ78. Atau algoritma DEFLATE yang merupakan gabungan antara algoritma HUFFMAN dengan LZ77 dan banyak diimplementasikan dalam aplikasi kompresi populer seperti PKZIP dan 7-Zib (Feldspar A, 2009).

2.5 Kompleksitas Algoritma dan Notasi O-besar (big O)

Dalam ilmu komputer, sebuah algoritma tidak hanya dilihat dari apakah algoritma tersebut dapat memecahkan suatu masalah atau tidak, tetapi juga dari seberapa efisien algortima tersebut melakukannya. Keefisienan suatu algoritma biasanya berkaitan erat Andre Pratama : Studi Perbandingan Kinerja Algoritma Kompresi Lempel Ziv 77, Lempel Ziv 78 Dan Lempel Ziv Welch Pada File Text, 2010.

17

dengan waktu dan ruang yang dibutuhkan algoritma tersebut dalam memecahkan masalah. Jika algoritma B dapat memecahkan masalah yang sama dengan waktu yang lebih cepat dibandingkan algoritma B, dapat dikatakan bahwa algoritma B lebih efisien daripada algoritma A.

Efisiensi suatu algortima dapat diukur dengan: 1.

Waktu (time): yakni banyaknya komputasi elementer dalam algoritma.

2.

Ruang (space): adalah banyaknya sel memori yang dibutuhkan oleh algoritma.

Ukuran ini secara berturut-turut disebut sebagai kompleksitas komputasi (computational complexity) dan kompleksitas ruang (space complexity) (Suksmono, 2009). Kedua kompleksitas ini tidak begitu berarti untuk input yang relatif sedikit, namun untuk input yang besar, keduanya dapat digunakan untuk mengetahui algoritma mana yang lebih efisien.

Salah satu hal yang paling penting dalam menghitung kompleksitas komputasi algoritma adalah pertumbuhan dari fungsi kompleksitas. Seperti contoh pada tabel 2.9, jika algoritma A mempunyai kompleksitas: 100n+50, dan algoritma B dengan kompleksitas: n2+10n+4, maka algoritma A dapat disimpulkan lebih efisien dibandingkan dengan algortima B untuk input yang besar dari 100. Hal ini dapat dilihat dimana dengan jumlah input (n) yang semakin membesar, algoritma B akan membutuhkan waktu yang lebih lama.

Tabel 2.9 Perbandingan Pertumbuhan Kompleksitas (Growth Rates) Algoritma A (100n+50) dengan Algoritma B ( n2+10n+4) Algoritma A (100n+50)

Algoritma B (n2+10n+4)

10

1.050

204

50

5.050

3.004

100

10.050

11.004

200

20.050

42.004

500

50.050

255.004

1.000

100.050

1.010.004

n


18

Dengan jumlah input (n) kurang dari 100, algoritma B lebih efisien daripada algoritma B, namun jika jumlah input sudah diatas 100, algoritma B akan membutuhkan waktu yang lebih banyak daripada algoritma A. Pertumbuhan dari kompleksitas dengan meningkatnya besarnya input (n), adalah ukuran yang sesuai untuk membandingkan algoritma. Pertumbuhan fungsi kompleksitas dilambangkan dengan notasi O (dibaca big-O).

Dalam bidang matematika, notasi big O menggambarkan batasan ruang lingkup (limiting behavior) dari suatu fungsi, ketika argumen fungsi tersebut condong ke suatu nilai tertentu atau nilai yang tak berhingga. Notasi big O akan menyederhanakan

suatu

fungsi

agar

dapat

diketahui

tingkat

pertumbuhan

kompleksitasnya (growth rates) (wikipedia, 2009). Walaupun dikembangkan sebagai bagian dari perhitungan di bidang matematika, notasi big O juga dapat digunakan dalam bidang ilmu komputer untuk mengukur kompleksitas suatu algoritma. Definisi big O: misalkan f dan g adalah dua buah fungsi dari bilangan bulat ke bilangan riil. Dapat dikatakan bahwa f(x) adalah O(g(x)) jika ada suatu konstanta C dan k sedemikian hingga |f(x)| ≤ C| g(x)|, saat x > k. (Suksmono, 2009). Saat menganalisa

perumbuhan dari fungsi kompleksitas, f(x) dan g(x) selalu positif. Oleh karena itu, persyaratan big-O diatas dapat disederhanakan menjadi f(x) ≤ C⋅g(x) saat x > k. Untuk menunjukkan bahwa f(x) adalah O(g(x)), hanya perlu ditentukan satu buah pasangan (C, k) (yang tidak pernah unik). Ide dibelakang notasi big-O adalah penentuan batas atas (upper boundary) dari perumbuhan suatu fungsi f(x) untuk x besar. Batas ini diberikan oleh fungsi g(x) yang biasanya jauh lebih sederhana daripada f(x). dengan konstanta C dalam persyaratan f(x) ≤ C⋅g(x) saat x > k. Karena C tidak pernah tumbuh sejalan dengan tumbuhnya x. Kita hanya tertarik pada x besar, sehingga jika f(x) > C⋅g(x) untuk x ≤ k, bukanlah suatu masalah. Contoh Soal : Tunjukkan bahwa f(x) = x2 + 2x + 1 adalah O(x2). Jawab: Untuk x > 1: x2 + 2x + 1 ≤ x2 + 2x2 + x2 ⇒ x2 + 2x + 1 ≤ 4 x2 Andre Pratama : Studi Perbandingan Kinerja Algoritma Kompresi Lempel Ziv 77, Lempel Ziv 78 Dan Lempel Ziv Welch Pada File Text, 2010.

19

O(x2).

Karena itu, untuk C = 4 dan k = 1: f(x) ≤ C x2 ketika x > k. ⇒ f(x) adalah Notasi big O dapat ditulis sebagai pangkat tertinggi (higest order) dari suatu

fungsi polinomial. Ini dikarenakan untuk input (n) yang besar dalam fungsi polinomial, pangkat tertinggi akan sangat mendominasi. Jadi fungsi f(n) = 100n+50, ditulis dengan O(n), dan untuk f(n) = (n2+10n+4) ditulis sebagai O(n2).

Kompleksitas suatu algoritma dihitung untuk setiap langkah atau instruksi yang dikerjakan. Beberapa ketetapan waktu yang diterapkan :

1.

Operasi pengisian nilai (assignment), perbandingan, operasi aritmatika, read and write, membutuhkan waktu O(1).

2.

Pengaksesan elemen array membutuhkan waktu O(1).

3.

Operasi if-then-else waktu yang diambil adalah yaktu yang paling besar diantara 2 kondisi.

4.

Operasi perulangan (for, repeat-until, dan while-do) membutuhkan waktu sebanyak jumlah perulangan dikalikan dengan banyak instruksi dalam perulangan tersebut.

Contoh algoritma konversi suhu: Tabel 2.10 Algoritma Konversi Suhu Baris 1 2 3

Pseudo code a←read(x); fahrenheit←(x*1.8)+32; print fahrenheit;

Waktu eksekusi 1 1+1+1=3 1

Pada contoh algoritma diatas, total waktu eksekusi adalah 1+3+1=4, maka notasi big O adalah O(1).


20

Contoh algoritma membedakan bilangan ganjil atau genap: Tabel 2.11 Algoritma Bilangan Ganjil atau Genap Baris 1 2 3 4 5 6 7 8

Pseudo code a←read(x); b←0; if (a mod 2 = 0) hasil←”bilangan genap”; b=b+a; else hasil←”bilangan genap”; end if

Waktu eksekusi 1 1 1+1=2 1 1+1=2 1

Pada contoh algoritma diatas, total waktu eksekusi adalah 1+1+2+ max(3,1)=1+1+2+3=7, maka notasi big O adalah O(1).

Contoh algoritma perulangan: Tabel 2.12 Algoritma Perulangan Sederhana Baris 1 2 3 4 5 6 7

Pseudo code a←read(x); b←0; i←0; for i=1 to a do b=b+i; i←i+1; end for

Waktu eksekusi 1 1 1 (1+1)*n=2n (1+1)*n=2n (1+1)*n=2n

Pada contoh algoritma diatas, total waktu eksekusi adalah 1+1+1+2n+2n+2n =6n+3, maka notasi big O adalah O(n).

Contoh algoritma perulangan bersarang (nested loop): Tabel 2.13 Algoritma Perulangan Sederhana Baris 1 2 3 4 5 6 7 8 9 12

Pseudo code a←read(x); b←0;c←0;i←0;j←0; for i=1 to a do b←i; for j=1 to b do c←c+j j←j+1; end for i←i+1; end for

Waktu eksekusi 1 1+1+1+1=4 (1+1)*n=2n 1*n=1n (1+1)*n*n=2n2 (1+1)*n*n=2n2 (1+1)*n*n=2n2 (1+1)*n=2n

Pada contoh algoritma diatas, total waktu eksekusi adalah 1+4+2n+1n+2n2 +2n2+2n2 +2n=6n2+5n+5, maka notasi big O adalah O(n2). Andre Pratama : Studi Perbandingan Kinerja Algoritma Kompresi Lempel Ziv 77, Lempel Ziv 78 Dan Lempel Ziv Welch Pada File Text, 2010.

21

Notasi big O yang sering diperoleh dari suatu algoritma adalah: 1.

O(1) - constant time Kompleksitas O(1) teradapat pada algoritma yang menghasilkan nilai selalu tetap tanpa bergantung kepada banyak masukan. Contoh: a. Operasi push dan pop pada suatu stack (yang terdiri dari n elemen). b. Inisialisasi suatu variabel. c. Operasi aritmatika sederhana.

2.

O(2log n) - logarithmic time Algoritma yang berdasarkan pada binary tree biasanya memiliki kompleksitas O(log n). Contoh: a. Algoritma binary search pada list berurutan yang terdiri dari n elemen. b. Operasi insert dan search pada binary tree yang terdiri dari n node.

3.

O(n) - linear time Algoritma dengan kompleksitas O(n) membutuhkan 1 kali proses untuk masingmasing masukan. Contoh: a. Penelusuran suatu list/array yang terdiri dari n elemen. b. Pencarian suatu nilai dalam list/array dengan algoritma linear search. c. Mencari nilai maksimum atau minimum dari suatu list.

4.

O(n 2log n) - linearithmic time Kompleksitas O(n log n) terdapat pada algoritma yang memecahkan masalah menjadi masalah yang lebih kecil, lalu menyelesaikan tiap masalah secara independen. Contoh: a. Algoritma pengurutan list quicksort. b. Algoritma pengurutan list mergesort.


22

5.

O(n2) - quadratic time Umumnya algoritma dengan kompleksitas O(n2) melibatkan proses perulangan bersarang (nested loop). Contoh: a. Beberapa algoritma pengurutan sederhana, seperti selection sort. b. Membandingkan array 2 dimensi dengan ukuran n * n. c. Mencari duplikasi dalam sebuah list yang tidak terurut dengan n elemen (menggunakan 2 loop bersarang).

6.

O(n3) - cubic time Algoritma dengan kompleksitas O(n3), mirip dengan O(n2), namun menggunakan loop bersarang sebanyak 3 kali. Algoritma jenis ini hanya cocok jika n kecil. Jika n besar, waktu yang dibutuhkan akan sangat lama.

7.

O(2n) - exponential time Salah satu algoritma yang mempunyai kompleksitas O(2n) adalah brute force dalam

menebak

suatu

password.

Setiap

penambahan

karakter,

akan

melipatgandakan waktu yang dibutuhkan.

8.

O(n!) - factorial time O(n!) merupakan kompleksitas yang sangat cepat pertumbuhan waktu yang diperlukannya. Algoritma ini memproses tiap masukan dan menghubungkannya dengan n-1 masukan lainnya.

Tabel 2.14 Perbandingan Pertumbuhan Kompleksitas Input (n)

O(1)

O(log n)

O(n)

O(n log n) O(n2)

O(n3)

O(2n)

O(n!)

1

1

1

1

1

1

1

2

1

2

1

1

2

2

4

8

4

2

8

1

3

8

24

64

512

256

40.320

64

1

6

64

384

4096

262.144

1019

1088

512

1

9

512

4.608

262.144

108

10153

101165

1.024

1

10

1.024

10.240

106

109

10307

102638

1.048.576

1

20

106

2*10 7

1012

1018

∞

∞


23

Pada tabel 2.4 terlihat perbandingan tingkat pertumbuhan (growth rates) dari masing-masing notasi big O. Untuk masukan (n) yang semakin membesar, O(n2), O(n3), O(2n) dan O(n!) membutuhkan waktu eksekusi yang sangat lama. Sedangkan O(1), O(log n) dan O(n) peningkatan waktu yang dibutuhkan tidak terlalu cepat untuk n yang besar. Urutan spektrum kompleksitas waktu algoritma dapat dilihat pada gambar 2.3, dan dalam grafik, pertumbuhan kompleksitas dapat dilihat pada gambar 2.4. O(1) < O(log n) < O( n) < O( n log n) < O( n 2 ) < O( n 3 ) < ... < O(2 n ) < O(n!)   

algoritma polinomial

algoritma eksponensial

Gambar 2.3 Urutan Spektrum Kompleksitas Waktu Algoritma

Gambar 2.4 Grafik Perbandingan Pertumbuhan Kompleksitas Sumber : Growth of Functions (2009).

Suatu masalah dikatakan tractable (mudah dari segi komputasi) jika ia dapat diselesaikan dengan algoritma yang memiliki kompleksitas polinomial kasus terburuk (artinya dengan algoritma yang mangkus), karena

algoritma akan menghasilkan

solusi dalam waktu yang lebih pendek. Sebaliknya, sebuah masalah dikatakan intractable (sukar dari segi komputasi) jika tidak ada algoritma yang mangkus untuk menyelesaikannya. Masalah yang sama sekali tidak memiliki algoritma untuk memecahkannya disebut masalah tak-terselesaikan (unsolved problem) (Munir, 2009). Andre Pratama : Studi Perbandingan Kinerja Algoritma Kompresi Lempel Ziv 77, Lempel Ziv 78 Dan Lempel Ziv Welch Pada File Text, 2010.

BAB 3

PERANCANGAN SISTEM

Perancangan sistem terdiri dari 5 bagian, bagian pertama adalah perancangan fungsifungsi yang digunakan pada perancangan algoritma kompresi.

Bagian kedua

merupakan perancangan masing-masing algoritma dalam bentuk pseudo code, lalu menghitung kompleksitasnya. Bagian ketiga berisi tentang perancangan pengukuran kecepatan algoritma, bagian keeampat tentang pengukuran rasio kompresi, dan bagian kelima tentang perancangan aplikasi yang mencakup DFD, kamus data dan interface program yang digunakan sebagai implementasi dari ketiga algoritma.

3.1

Perancangan Fungsi

Fungsi-fungsi yang dirancang digunakan dalam perancangan algoritma nantinya. Setiap algoritma membutuhkan beberapa fungsi yang hampir sama dalam melakukan proses kompresi (encoding) dan dekompresi (decoding), sehingga akan lebih efisien jika fungsi tersebut dipisahkan dari algoritma inti. Perancangan fungsi terdiri dari 2 bagian, yaitu perancangan fungsi dasar dan perancangan fungsi khusus.

3.1.1 Perancangan Fungsi Dasar

Perancangan fungsi dasar adalah perancangan fungsi-fungsi yang banyak digunakan dalam pemograman umum. Untuk bahasa pemograman tingkat tinggi, biasanya fungsi-fungsi ini sudah tersedia, termasuk bahasa pemograman PHP yang akan digunakan untuk implementasi ketiga algoritma. Tetapi untuk mengukur kompleksitas suatu algoritma, dihitung berdasarkan langkah demi langkah instruksi yang digunakan. Dengan merancang kembali fungsi-fungsi tersebut, akan dapat dihitung Andre Pratama : Studi Perbandingan Kinerja Algoritma Kompresi Lempel Ziv 77, Lempel Ziv 78 Dan Lempel Ziv Welch Pada File Text, 2010.

25

kompleksitas dan big O untuk masing-masing fungsi. Namun ada beberapa batasan yang digunakan, dimana ada beberapa fungsi dasar yang tidak dirancang ulang, dan dianggap memiliki kompleksitas 1. Fungsi tersebut adalah: 1.

Fungsi untuk mencari panjang dari suatu string : strlen().

2.

Fungsi untuk mencari banyak elemen dalam suatu array : count().

3.

Fungsi konversi integer ke karakter ASCII : chr().

4.

Fungsi konversi karakter ASCII ke integer : ord().

3.1.1.1 Fungsi Konversi Bilangan Desimal ke Bilangan Biner

Tujuan dari fungsi konversi bilangan desimal ke bilangan biner adalah untuk memperoleh output nilai biner dari input nilai desimal. Misalkan input dalam fungsi ini adalah 14, maka output yang dihasilkan adalah 1110. Tipe data masukan adalah integer, dan tipe data keluaran berupa string. Konversi bilangan desimal ke biner, dirancang dengan algoritma sebagai berikut:

Tabel 3.1 Algoritma Fungsi Konversi Bilangan Desimal ke Bilangan Biner Baris 1 2 3 4 5 6 7 8 9 10 11 12 13 14

Pseudo code string function dectobin (int dec){ int sisa←0; string biner←””; repeat { sisa←dec modulus 2; dec←dec div 2; if (sisa == 0) then biner←"0".biner; else biner←"1".biner; end if } until (dec > 0) return biner; } Total Kompleksitas

Waktu eksekusi 1 1+1 (1+1)*2log n (1+1)*2log n 1*2log n (1+1)*2log n (1+1)*2log n 1*2log n 1 8 * 2log n + 4

Algoritma tersebut mempunyai kompleksitas 8 * 2log n + 4, dengan dalam percabangan if pada baris ke-6 hanya diambil salah satu nilai, sehingga O(2 log n). Namun pada desain ketiga algoritma kompresi nantinya, batasan input dari fungsi konversi bilangan desimal ke bilangan biner ini adalah 214 = 16.384. Oleh karena n maksimum adalah 16.384, worst case fungsi ini menjadi 8 * 2log 16.384 + 4 = 116, dengan O(1). Andre Pratama : Studi Perbandingan Kinerja Algoritma Kompresi Lempel Ziv 77, Lempel Ziv 78 Dan Lempel Ziv Welch Pada File Text, 2010.

26

3.1.1.2 Fungsi Konversi Bilangan Biner ke Bilangan Desimal

Tujuan dari fungsi konversi bilangan biner ke bilangan desimal adalah untuk memperoleh output nilai desimal dari input nilai biner. Misalkan input dalam fungsi ini adalah 11010, maka output yang dihasilkan adalah 26. Tipe data masukan adalah string, dan tipe data keluaran adalah integer. Konversi bilangan desimal ke biner, dirancang dengan algoritma sebagai berikut:

Tabel 3.2 Algoritma Fungsi Konversi Bilangan Biner ke Bilangan Desimal Baris 1 2 3 4 5 6 7 8 9 10 11 12 13

Pseudo code int function bintodec(string bin){ int len_bin←0; arr←array(1,2,4,8,16,32,64,128,256,512,1024, ¬2048,4096,8192,16384); len_bin←strlen(bin); int dec←0; int i←0; string bit←""; for i=len_bin-1 to 0 do bit←bin[i]; dec←dec+(bit*arr[len_bin-i-1]); i--; end for return dec; } Total Kompleksitas

Waktu eksekusi 1 1 15 1+1 1+1+1 (1+1+1)*n 1*n (1+1+1+(3))*n 2*n 1 12*n + 23

Algoritma tersebut mempunyai kompleksitas 12n + 22, dengan O(n). n dalam algoritma ini adalah panjang string biner yang digunakan sebagai input. Pada baris kedua algoritma, dideklarasikan sebuah array arr sebagai penampung nilai 2n. Ini digunakan untuk mengatasi operasi pemangkatan dalam penerapannya nanti, bahasa pemograman PHP membutuhkan fungsi khusus untuk operasi pemangkatan, yang menyebabkan nilai kompleksitas akan sulit dihitung.

Dalam desain ketiga algoritma, konversi dari biner ke desimal maksimal hanya membutuhkan 13 digit, atau nilai maksimum desimalnya 16383. Dengan pembatasan ini, kompleksitas fungsi konversi bilangan biner ke bilangan desimal menjadi konstan, karena perulangan yang terjadi maksimal hanya 13 kali, sehingga dapat ditulis sebagai O(1).


27

3.1.1.3 Fungsi Pemotongan String

Fungsi pemotongan string adalah untuk menggantikan fungsi substr() pada PHP, yang digunakan untuk mengambil sebagian isi string. Fungsi ini membutuhkan 3 parameter, yaitu string input, awal dari pemotongan dan panjang pemotongan. Parameter pertama bertipe string, dan yang lainnya bertipe integer. Output fungsi bertipe string. Fungsi pemotongan string dirancang dengan algoritma sebagai berikut:

Tabel 3.3 Algoritma Fungsi Pemotongan String Baris 1 2 3 4 5 6 7 8 9 10

Pseudo code string function sub_str(string input, int ¬awal, int length){ int akhir←length+awal; string output←””; int i←0; for i=awal to akhir do output←output.input[i]; i++; end for return output; } Total Kompleksitas

Waktu eksekusi 3 1+1 1+1 (1+1)*n (1+1)*n 2*n 1 6*n + 8

Algoritma tersebut mempunyai kompleksitas 6n + 8, sehingga O(n). n adalah panjang pemotongan. Prinsip kerja algoritma tersebut adalah menyambung karakter demi karakter dalam batas yang telah ditentukan. Dalam perancangan algoritma kompresi nantinya, nilai n untuk fungsi ini terbatas pada nilai tertentu, sehingga kompleksitas akan menjadi konstan dengan O(1).

3.1.1.4 Fungsi Zero Left Pad

Fungsi ini digunakan untuk menambahkan beberapa karakter nol pada sisi kiri sebuah string dengan jumlah tertentu. Misalnya ditetapkan panjang string akhir adalah 8 karakter, jika input adalah 1101, output akan menjadi 00001101. Jika input adalah 1010010, output yang dihasilkan adalah 01010010. Fungsi ini membutuhkan 2 buah parameter, yang pertama adalah string input, yang kedua adalah panjang pad yang diinginkan dengan tipe data integer. Output fungsi bertipe string. Fungsi zero left pad dirancang dengan algoritma sebagai berikut:


28

Tabel 3.4 Algoritma Fungsi Zero Left Pad Baris 1 2 3 4 5 6 7 8 9 10

Pseudo code string function zero_lpad( string input, ¬int pad_length){ int in_len←strlen(input); int i←0; for i=in_len to pad_length do input←"0".input; i++; end for return input; } Total Kompleksitas

Waktu eksekusi 2 1+1 1 (1+1)*n (1+1)*n 2*n 1 6*n + 6

Algoritma tersebut mempunyai kompleksitas 6n + 6, dengan O(n). n adalah banyaknya karakter “0” yang akan ditambahkan. Algoritma tersebut menambahkan karakter “0” pada sisi kiri sebanyak panjang pad - panjang string input.

Dalam desain ketiga algoritma kompresi yang dirancang, maksimum panjang pad yang digunakan adalah 14 karakter. Sehingga nilai n maksimum adalah 14, dan kompleksitas fungsi zero left pad akan konstan menjadi 6(14) + 6 = 90 pada worst case dengan O(1).

3.1.1.5 Fungsi Zero Right Pad

Fungsi ini mirip dengan zero left pad. Namun penambahan “0” dilakukan pada sisi kanan. Misalnya ditetapkan panjang string akhir adalah 8 karakter, jika input adalah 1101, output akan menjadi 11010000. Jika input adalah 1010010, output yang dihasilkan adalah

10100100. Fungsi ini membutuhkan 2 buah parameter, yang

pertama adalah string input, yang kedua adalah panjang padding yang diinginkan bertipe integer. Output fungsi bertipe string. Fungsi zero right pad dirancang dengan algoritmaseperti pada tabel 3.5.


29

Tabel 3.5 Algoritma Fungsi Zero Right Pad Baris 1 2 3 4 5 6 7 8 9 10

Pseudo code string function zero_rpad(string input, ¬int pad_length){ int in_len←strlen(input); int i←0; for i= in_len to pad_length do input←input."0"; i++; end for return input; } Total Kompleksitas

Waktu eksekusi 2 1+1 1 (1+1)*n (1+1)*n 2*n 1 6*n + 6

Untuk kompleksitas fungsi sama dengan zero left pad, 6n + 6, dengan O(n). n adalah banyaknya karakter “0” yang akan ditambahkan.

Kedua fungsi ini sengaja dipisahkan untuk efisiensi, karena dalam desain algoritma nantinya fungsi zero left pad akan sering digunakan, sedangkan fungsi zero rightpad hanya beberapa kali digunakan.

3.1.2 Perancangan Fungsi Khusus

Perancangan fungsi khusus adalah perancangan fungsi atau sub program yang digunakan dalam perancangan algoritma LZ77, LZ78 dan LZW. Karena dalam beberapa tahap ketiga algoritma memerlukan fungsi yang sama, maka lebih efisien untuk memisahkannya menjadi sebuah sub program. Berbeda dengan desain fungsi dasar yang bersifat umum, desain fungsi khusus sedikit lebih kompleks dan merupakan bagian dari perancangan algoritma kompresi yang akan dibahas.

3.1.2.1 Fungsi Bit Stream to String Fungsi bit stream to string digunakan oleh ketiga algoritma kompresi untuk mengkonversi bit stream menjadi string yang terdiri dari karakter-karakter ASCII sebelum di tulis kedalam file akhir. Fungsi ini diperlukan pada proses kompresi (encoding). Bit stream yang akan dikompresi berupa sebuah string yang berisi angka biner, seperti “0100101010110”. Bit stream ini adalah output dari proses encoding masing-masing algoritma kompresi. Untuk menyimpan hasil encoding ke dalam Andre Pratama : Studi Perbandingan Kinerja Algoritma Kompresi Lempel Ziv 77, Lempel Ziv 78 Dan Lempel Ziv Welch Pada File Text, 2010.

30

sebuah file, setiap beberapa karakter bit stream perlu dikonversi menjadi karakter ASCII. Karakter ASCII (American Standard Code for Information Interchange) adalah kumpulan kode yang digunakan oleh komputer untuk merepresentasikan sebuah karakter. Dalam fungsi ini digunakan kode ASCII 8 bit, sehingga terdapat 256 karakter yang berbeda. Masing-masing kode membutuhkan 8 bit atau 1 byte untuk 1 karakter ASCII. Fungsi bit stream to string dirancang menjadi 2 langkah. Langkah pertama adalah jika bit stream tidak habis dibagi 8, akan ditambahkan beberapa bit “0” supaya bit stream tersebut habis dibagi 8. Lalu langkah ke 2 adalah untuk memotong bit stream menjadi 8 bit lalu mengkonversinya menjadi karakter ASCII. Kumpulan karakter ASCII ini akan ditampung dalam sebuah string. Fungsi bit stream to string dirancang dengan algoritma sebagai berikut:

Tabel 3.6 Algoritma Fungsi Bit stream to String Baris 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24

Pseudo code string function bit_stream_to_string ¬(string stream) { int bit_sisa←0; int last_byte←0; int len_stream←strlen(stream); if len_stream modulus 8 !=0 do bit_sisa←len_stream modulus 8; last_byte←sub_str(stream,len_stream¬bit_sisa,bit_sisa); stream←sub_str(stream,0,len_stream¬bit_sisa); stream←stream.zero_rpad(last_byte,8); end if

Waktu eksekusi 1

2 1+1=2 1+1=2 1+1=2 1+6(7)+8=51 1+6(n)+8=6n+9 1+1+6(7)+6=50

string string←""; int i←0; len_stream←strlen(stream); for i = 0 to len_stream do string←string.chr(bintodec( ¬sub_str(stream,i,8))); i←i+8; end for

1+1=2 1+1=2 (1+1)*n/8=2n/8 (1+1+12(8)+23+56) ¬*n/8=177n/8 (1+1)*n=2n/8

return string; } Total Kompleksitas

1 6n+181n/8+124

Total kompleksitas fungsi bit stream to string adalah 6n+181n/8+124. Sehingga O(n). n merupakan panjang dari bit stream yang akan dikonversi. Penambahan beberapa bit “0” pada bit stream ini akan dihapus saat proses decompress (decoding). Andre Pratama : Studi Perbandingan Kinerja Algoritma Kompresi Lempel Ziv 77, Lempel Ziv 78 Dan Lempel Ziv Welch Pada File Text, 2010.

31

3.1.2.2 Fungsi String to Bit Stream

Fungsi string to bit stream adalah kebalikan dari fungsi bit stream to string. Fungsi ini mengubah suatu string yang terdiri dari sekumpulan karakter ASCII menjadi bit-bit pembentuknya. Proses ini dilakukan pada saat decompress (decoding).

Karakter-karakter ASCII tersebut adalah file hasil kompresi, atau file yang sudah dimampatkan. Kumpulan karakter itu sendiri adalah representasi dari bit stream. Sehingga untuk memprosesnya kembali menjadi file asli, bit stream inilah yang akan dikodekan oleh masing-masing algoritma kompresi.

Fungsi ini terdiri dari 2 proses. Proses pertama mengkonversi tiap-tiap karakter ASCII menjadi nilai biner yang membentuknya, dimana setiap karakter terdiri dari 8 bit, bit-bit dari semua karakter akan menjadi bit stream awal. Bit stream ini terdiri dari bit stream yang sebenarnya ditambah dengan beberapa bit tambahan. Proses kedua akan menghapus bit-bit tambahan ini.

Tabel 3.7 Algoritma Fungsi String to Bit Stream Baris 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20

Pseudo code string function string_to_bit_stream(string ¬string,int ctoken) { string stream←””; int i←0; int len_string←strlen(string); for i = 0 to len_string do stream←stream.zero_lpad(dectobin( ¬ord(string[i])),8); i++; end for

Waktu eksekusi 2

int len_stream = strlen(stream); int del_zero←0; if len_stream mod ctoken != 0 then del_zero←len_stream mod ctoken; stream←sub_str(stream,0,(len_stream¬del_zero)); end if return stream; } Total Kompleksitas

1+1=2 1 1+1=2 1+1=2 1+(6*n+8)+1= ¬6n+10

1+1=2 1+1=2 (1+1)*n=2n 1+1+54+(8*2log255 ¬+4)+1+1)*n=126n 2*n

1 136n + 23

Input fungsi adalah sebuah string yang akan dikonversi dan panjang token yang digunakan oleh algoritma. Panjang token dengan tipe integer ini digunakan untuk Andre Pratama : Studi Perbandingan Kinerja Algoritma Kompresi Lempel Ziv 77, Lempel Ziv 78 Dan Lempel Ziv Welch Pada File Text, 2010.

32

menghapus bit-bit tambahan pada bit stream awal. Jika bit stream awal menghasilkan nilai sisa saat dibagi dengan panjang token, maka sisa bit inilah yang akan dibuang. Fungsi string to bit stream dirancang dengan algoritma seperti pada tabel 3.7. Total kompleksitas fungsi string to bit stream adalah 136n + 23, sehingga O(n). n adalah panjang string karakter yang akan dikonversi.

3.2

Perancangan Algoritma Kompresi

Perancangan algoritma kompresi akan digunakan untuk mengukur kompleksitas algoritma. Untuk proses

kompresi (encoding), algoritma menerima input berupa

sebuah string karakter yang akan dimampatkan, dan output berupa string karakter yang merupakan representasi dari bit stream yang telah dikodekan. Sedangkan untuk proses dekompres (decoding), input adalah string karakter yang merupakan representasi dari bit stream yang telah dikodekan, dan output berupa string karakter asli.

3.2.1 Algoritma LZ77

Perancangan algoritma LZ77, dirancang agar panjang dari history buffer dan lookahaead buffer mendukung beberapa nilai tertentu. Sehingga nanti dapat dianalisis berapa panjang buffer yang efisien untuk LZ77. Untuk panjang history buffer terdiri dari 511, 1023, 2047, 4095, dan 8191 karakter. Pemilihan panjang ini untuk mengalokasikan berapa banyak digit bit yang diperlukan untuk menyimpan nilai sub token pertama dari output algoritma. Output algoritma LZ77 berupa token dengan bentuk (f, l,c). Dimana f adalah jumlah karakter dari ujung jendela history buffer kepada karakter yang ditemukan. Untuk panjang history buffer 1023, nilai maksimal sub token c adalah 1023. Hal ini terjadi jika pola karakter yang ditemukan berada pada awal history buffer. Bilangan biner dari 1023 adalah 1111111111, yang terdiri dari 9 digit. Dengan 9 digit, sub token pertama dapat bernilai 0-1023. Jika maksimum history buffer adalah 4095, akan membutuhkan 12 digit.

Panjang lookahead buffer terdiri diri 15, 31, 63, 127 dan 255 karakter. Nilai ini digunakan pada sub token kedua dari token output LZ77. Dimana l adalah jumlah Andre Pratama : Studi Perbandingan Kinerja Algoritma Kompresi Lempel Ziv 77, Lempel Ziv 78 Dan Lempel Ziv Welch Pada File Text, 2010.

33

panjang dari karakter dalam lookahead buffer yang ditemukan cocok pada history buffer. l akan bernilai sama dengan panjang history buffer jika pola karakter yang ada pada lookahead buffer terdapat seluruhnya pada history buffer. Untuk sub token ketiga (c) adalah karakter pertama setelah karakter yang sudah dikodekan. Karakter ini akan membutuhkan 8 digit bit. Karena akan dikonversi menjadi nilai ASCII pembentuknya.

Output token:

Bit Stream:

(856,27,c) (507,13,K)

1101011000

11011

01100011 0111111011

01101

01001011

Gambar 3.1 Konversi token ke bit stream algoritma LZ77

Gambar 3.1 memperlihatkan konversi token dari output algoritma LZ77 ke dalam bit stream. Masing-masing token akan dijadikan kedalam bentuk bit. Pada gambar tersebut ukuran panjang history buffer adalah 1023 karakter, sehingga akan membutuhkan 10 bit. Panjang lookahead buffer adalah 31 karakter, dan membutuhkan 5 bit. Sub token terakhir adalah sebuah karakter yang dikonversi menjadi nilai ASCII pembentuknya akan membutuhkan 8 bit. Jadi panjang 1 token yang dihasilkan adalah 10+5+8=23 bit. Semakin panjang ukuran masing-masing buffer, akan semakin panjang pula bit yang dibutuhkan untuk sebuah token.

Bit stream ini selanjutnya akan dikonversi menjadi karakter ASCII. Dan disimpan kedalam sebuah string akhir. Dalam implementasinya nanti, string ini akan ditulis kedalam sebuah file akhir.

Bit stream:

1101011000

11011

01100011 0111111011

01101

01001011

Token: (856,27,c) (507,13,K)

Gambar 3.2 Konversi bit stream ke token algoritma LZ77 Andre Pratama : Studi Perbandingan Kinerja Algoritma Kompresi Lempel Ziv 77, Lempel Ziv 78 Dan Lempel Ziv Welch Pada File Text, 2010.

34

Pada proses decoding, string karakter ASCII hasil proses encoding, akan dikonversi kembali menjadi bit stream lalu akan dibentuk kembali token-token yang sama persis dengan proses encoding, seperti yang diperlihatkan gambar 3.2.

3.2.1.1 Algoritma LZ77 Encoding

Untuk mengukur kompleksitasnya, algoritma kompresi (encoding) LZ77 dirancang dalam bentuk flowchart seperti pada gambar 3.3. Lalu dari flowchart tersebut dikembangkan kedalam bentuk pseudo code seperti tabel 3.8. Start source ← baca string input; bhbuffer ← baca batasan panjang history buffer; blbuffer ← baca batasan panjang lookahead buffer; isi lookahead_buffer sebanyak blbuffer karakter awal dari source

EOF source? Tidak temukan pola karakter terpanjang pada history_buffer yang cocok dengan pola yang terdapat pada lookahead_buffer;

l ← jumlah karakter terpanjang yang ditemukan; f ← jarak antara ujung history_buffer dengan karakter yang ditemukan; c ← karakter pertama setelah karakter yang ditemukan;

output ← output + (l,f,c) ;

Ya

history_buffer ← history buffer + karakter yang sudah dikodekan + c; Sesuaikan panjang history_buffer jika melebihi batas bhbuffer

lookahead_buffer←lookahead_buffer + (l+1) karakter selanjutnya dari source Sesuaikan panjang lookahead_buffer jika melebihi batas lhbuffer

Tampilkan output

Stop

Gambar 3.3 Flowchart Algoritma LZ77 Encoding Andre Pratama : Studi Perbandingan Kinerja Algoritma Kompresi Lempel Ziv 77, Lempel Ziv 78 Dan Lempel Ziv Welch Pada File Text, 2010.

35

Tabel 3.8 Algoritma LZ77 Encoding Baris 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57

Pseudo code string source ← input dari user; int chbuffer ← input dari user; int clbuffer ← input dari user;

Waktu eksekusi 1 1 1

int len_source ← strlen(source); int bhbuffer ← 0; string zhbuffer ← ””;

1+1=2 1+1=2

if chbuffer == 9 then bhbuffer ← 511; zhbuffer ← "000000000"; end if else if chbuffer == 10 then bhbuffer ← 1023; zhbuffer ← "0000000000"; end if else if chbuffer == 11 then bhbuffer ← 2047; zhbuffer ← "00000000000"; end if else if chbuffer == 12 then bhbuffer ← 4095;zhbuffer ← "000000000000"; end if else if chbuffer == 13 then bhbuffer ← 8191; zhbuffer←"0000000000000"; end if

1 1+1=2

int blbuffer ← 0; string zlbuffer ← ””;

1+1=2

if clbuffer == 4 then blbuffer ← 15; zlbuffer end if else if clbuffer == 5 then blbuffer ← 31; zlbuffer end if else if clbuffer == 6 then blbuffer ← 63; zlbuffer end if else if clbuffer == 7 then blbuffer ← 127; zlbuffer end if else if clbuffer == 8 then blbuffer ← 255; zlbuffer end if

1 1+1=2 1 1+1=2 1 1+1=2 1 1+1=2

← "0000";

1 1+1=2

← "00000";

1 1+1=2

← "000000";

1 1+1=2

← "0000000";

1 1+1=2

← "00000000";

1 1+1=2

string slbuffer ← sub_str(source,0, ¬(blbuffer)); int i ← 0; int add ← 0; string shbuffer ← ""; string stream ← ""; int shbuffer_len ← 0; string sub_token1 ← ””; string sub_token2 ← ””; string sub_token3 ← ””;

1+6*A+8=6A+9

while i < len_source do int lblen ← strlen(slbuffer); int hblen ← strlen(shbuffer); int j ← 0; int truelen ← 0; int truepos ← 0;

n (1+1)*n=2n (1+1)*n=2n (1+1+1)*n=3n

while j < hblen do

1 1 1+1=2 1 1 1 1

1*B*n=bn


36

58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108

if slbuffer[0] == shbuffer[j] then { int pos ← j; int l ← j; int k ← 0; while ktruelen then truelen ← k; truepos ← pos; end if l++; if slbuffer[k]!=shbuffer[l] then keluar dari perulangan while k; end if end while j++; end while

1*B*n=bn (1+1+1)*B*n=3bn 1*B*A*n=1ban 2*B*A*n=2ban 1*B*A*n=1ban 1*B*A*n=1ban 1*B*A*n=1ban 2*B*A*n=2ban 1*B*A*n=1ban 1*B*A*n=1ban

1*B*n=1bn

if truelen!=0 then sub_token1 ← zero_lpad(dectobin(strlen ¬(shbuffer)-truepos),chbuffer); sub_token2 ← zero_lpad(dectobin(truelen), ¬clbuffer); sub_token3 ← zero_lpad(dectobin(ord(source ¬[i+truelen])),8); stream ← stream.sub_token1.sub_token2. ¬sub_token3; else sub_token1 ← zhbuffer; sub_token2 ← zlbuffer; sub_token3 ← zero_lpad(dectobin(ord ¬(slbuffer[0])),8); stream ← stream.sub_token1.sub_token2. ¬sub_token3; end if

1*n=1n (85+(8*2logB+4)+ 2)n=(82logB+91)n (55+(8*2logA+4)) n=(82logA+59)n (55+(8*2log255+4 )+2)n=125n (1+1+1+1)n=4n

add ← truelen + 1; shbuffer ← shbuffer.sub_str(source,i,add); shbuffer_len ← strlen(shbuffer); if shbuffer_len>bhbuffer then shbuffer←sub_str(shbuffer,add,shbuffer_len); end if

(1+1)*n=2n (6a+10)n=6An+10n (1+1)*n=2n 1n (6*b+9)n=6Bn+9n

slbuffer ← slbuffer.sub_str(source,i+ blbuffer,add); slbuffer ← sub_str(slbuffer,add, ¬strlen(slbuffer));

(1+1+6*A+8+1)*n= 6An+11n (1+6*A+8+1)*n=6A n+10n

i ← i + add; end while

(1+1)*n=2n

string output=bit_stream_to_string(stream); Total Kompleksitas

(6n+181n/8+124)8

1*n=1n 1*n=1n (55+(8*2log255+4 )+1)*n=124n (1+1+1+1)n=4n


37

Algoritma diatas membutuhkan 3 buah input, yaitu string yang akan dikodekan dengan panjang n karakter (source ), panjang bit yang dibutuhkan untuk menyimpan buffer buffer (chbuffer) , dan panjang bit yang dibutuhkan untuk menyimpan lookahead buffer (clbuffer)).

Proses ini terdapat pada baris 1-3. Input panjang buffer ini berupa banyak bit yang disediakan untuk buffer tersebut, sehingga untuk mengetahui panjang sebenarnya, dari baris 8 sampai 40 akan memeriksa input, dan membuat variabel baru untuk menampung panjang buffer dalam ukuran karakter/byte. Jika input buffer berupa: chbuffer=11 dan clbuffer=5. Maka panjang buffer buffer sebenarnya adalah 2067 untuk buffer buffer, dan 31 untuk lookahead buffer. Untuk panjang buffer buffer ini disimbolkan dengan b, dan untuk lookahead buffer disimbolkan dengan a.

Pada baris ke 42, string lookahead buffer (slbuffer) diisi dengan A buah karakter pertama dari source, jika A=31 maka slbuffer akan berisi 31 karakter pertama dari source. Sedangkan string buffer buffer belum diisi pada saat awal ini. Baris 42-50 adalah pendeklarasian beberapa variabel yang akan digunakan. Selanjutnya dari baris 52 sampai 106 akan dikodekan seluruh input dalam sebuah loop while. Loop terluar ini pada kondisi worst case akan diulang sebanyak n kali (sebanyak karakter yang ada). Namun pada kodisi rata-rata (average case), loop tidak akan sampai n kali, karena akan terdapat kemungkinan counter loop (pada baris 105) akan berisi nilai lebih besar dari 1, yaitu saat ditemukan pola karakter pada history buffer.

Loop kedua yang berada pada baris 57-73 adalah perulangan sebanyak b kali untuk mencari pola karakter pada history buffer. Sehingga kompleksitas yang ada pada loop ini akan bernilai B*n. Perulangan terdalam pada baris 61-71 akan diulang sebanyak karakter yang ada pada lookahead buffer (a), sehingga kompleksitasnya akan bernilai A*B*n. Untuk proses kerjanya diperlihatkan pada gambar 3.4.


38

History buffer (shbuffer)

Lookahead buffer (slbuffer)

cabbabcddccbabcdecbabcaa

abcdee

012345678901234567890123

012345

shbuffer[j]=??

slbuffer[0]=a

If shbuffer[j]==slbuffer[0]

shbuffer:

abcddd

abcdec

abcaa

aa

a

slbuffer:

abcdee

abcdee

abcdee

abcdee

abcdee

len=4 pos=4

len=5 pos=12

len=3 pos=19

len=1 pos=22

len=1 pos=23

truelen=5 truepos=12

Gambar 3.4 Proses Pencarian Pola Karakter LZ77

Pada gambar 3.4 terlihat shbbuffer dan slbuffer sudah berisi dengan karakter tertentu. Untuk mencari pola terpanjang pada shbuffer, dilakukan pengecekan tiap-tiap karakter dari shbuffer, apakah sama dengan karakter pertama slbuffer. Jika tidak, maka lanjutkan ke karakter berikutnya. Pada gambar, karakter pertama slbuffer adalah “a”. Pada karakter ke 5 shbuffer (berada pada index ke 4, karena karakter pertama berada pada index 0) berisi “a”, sehingga kondisi “if” terpenuhi. Lalu proses akan masuk pada perulangan baru untuk memeriksa berapa banyak karakter berurutan yang cocok dengan slbuffer. Variabel len berisi panjang karakter yang cocok, dan variabel pos berisi index dari shbuffer sekarang. Jika slbuffer sudah tidak sesuai lagi dengan shbuffer, proses akan keluar dari perulangan dan kembali memeriksa apakah karakter selanjutnya (karakter sesudah “a” ditemukan) sama dengan slbuffer[0]. Jika ada, proses kembali berulang untuk mengetahui berapa banyak karakter yang cocok dengan slbuffer. Andre Pratama : Studi Perbandingan Kinerja Algoritma Kompresi Lempel Ziv 77, Lempel Ziv 78 Dan Lempel Ziv Welch Pada File Text, 2010.

39

Hasil yang akan digunakan adalah len dengan nilai tertinggi, yang berarti karakter yang paling banyak cocok dengan slbuffer. Dari 5 kali kondisi shbuffer[j]==slbuffer[0] yang terpenuhi, pola terpanjang yang ditemukan adalah 5 karakter pada index ke 12 (len=5, pos=12). Lalu hasil ini akan dipindahkan kedalam variabel truelen dan truepos.

Selanjutnya pada tabel 3.8, langkah pada baris 75-91 adalah pembentukan token. sub_token1, sub_token2, dan sub_token3 adalah variabel yang digunakan untuk menampung masing-masing subtoken. sub_token1 adalah jumlah karakter dari ujung jendela history buffer kepada karakter yang ditemukan. Ini dikalkulasi dengan mengurangkan panjang history buffer dengan truepos (strlen (shbuffer)-truepos)). sub_token2 adalah jumlah panjang dari karakter dalam lookahead buffer yang ditemukan cocok pada history buffer, ini didapat dari nilai truelen pada proses pencarian pola sebelumnya. sub_token3 adalah karakter pertama setelah karakter yang sudah dikodekan. Karakter ini didapat dengan counter saat ini +truelen

(source

[i+truelen])). Seluruh token ini akan dikonversi menjadi bit stream.

Pembentukan token juga dibagi menjadi 2 bagian, yaitu bagian dimana truelen tidak sama dengan 0, yang berarti pola karakter ditemukan, dengan bagian dimana truelen=0, dimana pola karakter tidak ditemukan sama sekali. Ini biasanya terjadi pada awal proses algoritma LZ77, dimana history buffer masih dalam keadaan kosong. Pada keadaan ini, subtoken1 dan subtoken2 bernilai 0, dan hanya subtoken3 yang berisi nilai.

Langkah pada baris 93-106 adalah bagian untuk ” menggerakkan” jendela history buffer dan lookahead buffer. Kedua buffer tersebut akan bergerak sebanyak truelen+1. Lalu dilakukan pomotongan string supaya buffer tersebut tidak melebihi kapasitas yang telah ditetapkan.

Langkah terakhir adalah mengkonversi bit stream menjadi karakter string dengan fungsi bit_stream_to_string.


40

Kompleksitas dari LZ77 encoding : 1.

Baris 1-50 merupakan inisialisasi awal, kompleksitas: 6A+32.

2.

Baris 52-73 awal dari loop dan pencarian pola karakter, kompleksitas: 10BAn +6Bn+8n.

3.

Baris 75-91 adalah bagian pembuatan token, karena terbagi menjadi 2 bagian kodisi, kompleksitas yang dipakai adalah yang paling besar, kompleksitas: 8(2 log B)n+8(2 log A)n+280n.

4.

Baris 93-106 merupakan proses untuk menggerakkan kedua buffer dan menaikkan counter, kompleksitas: 18An+6Bn+47n.

5.

Baris 112 untuk mengkonversi bit stream menjadi string karakter, kompleksitas: (6n+181n/8+124 )*8=229n+992 (dengan asumsi panjang bit stream sama dengan panjang bit source).

Sehingga

total

kompleksitas

algoritma

LZ77

encoding

adalah:

6A+32+10BAn +6Bn +8n+8(2 log B)n+8(2 log A)n+280n+18an+6Bn+47n+229n+992 = 10BAn+12Bn+18An+ 564n+6A+82(2 log B)n+82(2 log A)n+1024 Dengan notasi big O = O(BAn). Dimana B adalah panjang history buffer, A adalah panjang lookahead buffer, dan n panjang string yang akan dikodekan.

3.2.1.2 Algoritma LZ77 Decoding

Untuk proses decoding algoritma LZ77, input terdiri dari string karakter yang akan diproses (source). String ini pada dasarnya merupakan kumpulan dari token hasil proses encoding sebelumnya. Input selanjutnya adalah panjang bit yang dibutuhkan untuk menyimpan history buffer (chbuffer) , dan panjang bit yang dibutuhkan untuk menyimpan lookahead buffer (clbuffer).

Untuk mengukur kompleksitasnya, algoritma decoding LZ77 dirancang dalam bentuk flowchart seperti pada gambar 3.5. Lalu dari flowchart tersebut dikembangkan kedalam bentuk pseudo code seperti tabel 3.9.


41

Start source ← baca string input; bhbuffer ← baca batasan panjang history buffer; blbuffer ← baca batasan panjang lookahead buffer; Konversi source ke bentuk token; output ← “”; x ← baca 1 token berikutnya dari source;

EOF token? Tidak f ← sub token 1 dari token; l ← sub token 2 dari token; c ← sub token 3 dari token;

Ya

outlen ← panjang string output; output ← output + ambil sebanyak l karakter dari string output dimulai pada karakter ke (outlen-f) + c;

Tampilkan output

Stop

Gambar 3.5 Flowchart Algoritma LZ77 Decoding

Tabel 3.9 Algoritma LZ77 Decoding Baris 1 2 3 4 5 6 7 8 9 10 11 12 13

Pseudo code string source ← input dari user; int chbuffer ← input dari user; int clbuffer ← input dari user; int ctoken ← chbuffer+clbuffer+8;

Waktu eksekusi 1 1 1 1+1+1=3

string stream_input ← string_to_bit_stream (source,ctoken); int len ← strlen(stream_input); int i ← 0; string shbuffer ← ""; string fulltoken ← ""; int sub_token1 ← 0; int sub_token2 ← 0;

(136n + 23)*2 1+1=2 1 1 1 1 1


42

14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44

int sub_token3 ← 0; string add ← ""; string output ← ""; int output_len ← 0;

1 1 1 1

while i
n

fulltoken ← sub_str(stream_input,i,ctoken); sub_token1 ← bintodec(sub_str(fulltoken,0, chbuffer)); sub_token2 ← bintodec(sub_str(fulltoken, chbuffer,clbuffer)); sub_token3 ← chr(bintodec(sub_str (fulltoken,chbuffer+clbuffer,8)));

(1+6*(a+b+8)+8)n (1+12*13+23+6*b+ 8)*n=6bn+194n (1+12*8+23+6*a+8 )*n=6an+134n (1+12*8+23+6*8+8 +1)*n=177n

if (sub_token1==0) and (sub_token2==0) then output ← output.sub_token3; else output_len ← strlen(output); add ← sub_str(output,(output_lensub_token1),sub_token2); output ← output.add.sub_token3; end if

(1+1)*n=2n (1+1)*n=2n (1+1)*n=2n (1+6*a+8+1)*n= 6an+10n (1+1+1)*n=3n

i ← i + ctoken; end while

(1+1)*n=2n

if sub_token3 == chr(0) then output ← sub_str(output,0,strlen(output)1); end if Total Kompleksitas

1+1=2 1+6*n*3+8+1+1= 18n+11

Setelah menyimpan input dari user pada 3 baris pertama, pada baris ke 4 dihitung berapa bit panjang yang diperlukan oleh sebuah token. Panjang token diperoleh dari panjang bit yang dibutuhkan oleh history buffer, ditambah dengan panjang bit yang dibutuhkan oleh lookahead buffer dan ditambah 8 (panjang bit 1 karakter ASCII). Fungsi stream_to_bit_stream pada baris ke 5 akan mengkonversi string karakter menjadi bit stream pembentuknya. Baris 9-17 untuk menginisialisasi beberapa variabel yang dibutuhkan dalam proses encoding.

Proses perulangan untuk mengkodekan token kembali menjadi string aslinya dimulai dari baris 19 sampai 39. Langkah pertama adalah mengkonversi kembali bit stream menjadi token. Masing-masing sub token ini disimpan dalam variabel sub_token1, sub_token2 dan sub_token3. Selanjutnya dipersiapkan sebuah variabel output untuk menampung string akhir. Perulangan if digunakan untuk membagi proses ke dalam 2 langkah, yang pertama jika token berbentuk: (0,0,x), cukup tambahkan x Andre Pratama : Studi Perbandingan Kinerja Algoritma Kompresi Lempel Ziv 77, Lempel Ziv 78 Dan Lempel Ziv Welch Pada File Text, 2010.

43

kedalam string output, tetapi jika sub_token1 dan sub_token2 tidak bernilai 0, maka tambahkan karakter baru sebanyak sub_token2 karakter, dimulai dari karakter ke(panjang output - sub_token1) dari output saat ini, lalu ditambah 1 karakter dari sub_token3. Untuk proses lebih jelasnya, diperlihatkan pada gambar 3.6.

History buffer:

cab babcdd ccbab 0123456789012345

token:

...(0,0,e),(2,4,c),(1,2,d)

token

add

output+add

...

...

cab babcdd ccbab

(0,0,e)

e

cab babcdd ccbabe

(15,4,e) b bae

cab babcdd ccbabeb bae

(11,2,d) ccd

cab babcdd ccbabeb baeccd

Gambar 3.6 Proses Decoding Token Algoritma LZ77

Pada gambar 3.6 terlihat output berisi beberapa karakter, lalu token yang akan dikodekan selanjutnya adalah: (0,0,e),(2,4,c),(1,2,d). Dalam tiap pembacaan token, variabel add akan menampung nilai sementara dari token. Pada saat token (0,0,e) diproses, add akan berisi “e”, lalu ditambahkan pada output. Pada token (2,4,e), variabel add akan berisi 4 karakter yang diambil mulai dari karakter ke (17-15=4) dari output saat ini, ditambah “e”. Sehingga add akan berisi “b bae”. Dan pada saat token (11,2,d) diproses , variabel add akan berisi 2 karakter yang diambil mulai dari karakter ke (22-11=11) dari output ditambah “d”. Sehingga add akan berisi “ccd”.

Langkah pada baris 41-44 adalah proses untuk mengatasi masalah pada token terakhir. Hal ini terjadi jika token terakhir berbentuk (x,x,null). Karakter null ini didapat pada saat proses encoding (pembentukan token) sudah mencapai akhir file (EOF), sehingga tidak ada lagi karakter setelah pola karakter yang diproses sebagai pengisi sub_token3 . Pada proses pengkodean token, null ini akan ditambahkan pada string output. Namun jika token terakhir adalah (x,x,not null), tidak ada masalah. Untuk mengatasinya, jika sub_token3 sama dengan null (nilai ASCII dari null adalah 0), hapus 1 karakter terakhir dari string output. Andre Pratama : Studi Perbandingan Kinerja Algoritma Kompresi Lempel Ziv 77, Lempel Ziv 78 Dan Lempel Ziv Welch Pada File Text, 2010.

44

Kompleksitas dari LZ77 decoding : 1.

Baris 1-4 : pembacaan input, kompleksitas: 6.

2.

Baris 6 : proses konversi dari bit stream ke string, kompleksitas: (136n + 23)*2 = 272n+46 (dengan asumsi 1 token = 2 karakter).

3.

Baris 8-17 : inisialisasi variabel awal, kompleksitas: 11.

4.

Baris 19-36 : proses membaca token dan menghasilkan string output, kompleksitas: 12an+6bn+6a+6b+581n.

5.

Baris 41-44 : mengatasi masalah karakter terakhir, kompleksitas: 6n*3+13 = 18n+13 (dengan asumsi satu token akan menghasilkan 3 karakter). Sehingga total kompleksitas algoritma LZ77 decoding adalah: 6+272n+46

+11+12an +6bn+6a+6b+581n +18n+13= 12an+6bn+6a+6b+871n+76 . Dengan notasi big O = O(an+bn). Dimana b adalah panjang bit yang diperlukan oleh history buffer, a adalah panjang bit yang dibutuhkan lookahead buffer, dan n jumlah token yang akan dikodekan.

3.2.2 Algoritma LZ78

Dasar teori untuk algoritma kompresi LZ78 telah dibahas pada bab sebelumnya. Untuk perancangan algoritma, besar dictionary akan dibatasi. Jika pada saat melakukan proses kompresi dictionary sudah penuh, maka proses selanjutnya hanya menggunakan pola yang ada di dalam dictionary tanpa menambahkan index baru ke dalam dictionary.

Besar dictionary tersebut akan dirancang supaya dapat mendukung beberapa nilai tertentu yang dapat dipilih. Besar dictionary yang didukung adalah 2n, dengan n = 8,9,10,11,12 dan 13. Dimana n merupakan banyak bit yang diperlukan untuk menyimpan nilai maksimum dari index dictionary. Jika menggunakan 10 bit, dictionary itu akan mempunyai 1024 (210) buah index. Sehingga besar dictionary yang didukung adalah 256, 512, 1024, 2048, 4096, 8192, atau16384. Index array yang digunakan dimulai dari 0, jadi index maksimum = besar dictionary - 1.

Token dalam algoritma LZ78 terdiri dari 2 bagian, berbentuk (f,c). Dimana f adalah index pada dictionary dimana pola yang ditemukan, dan c adalah karakter Andre Pratama : Studi Perbandingan Kinerja Algoritma Kompresi Lempel Ziv 77, Lempel Ziv 78 Dan Lempel Ziv Welch Pada File Text, 2010.

45

pertama sesudah pola. Token ini nantinya akan dikonversi menjadi bit stream seperti gambar x.x. Banyak bit yang diperlukan untuk f tergantung pada input awal, jika besar dictionary ditentukan 2048, maka akan diperlukan 11 bit untuk f. Sedangkan untuk c akan membutuhkan 8 bit, yaitu nilai ASCII dari karakter tersebut.

Output token:

Bit Stream:

(856,c) (507,K)

1101011000

01100011

0111111011

01001011

Gambar 3.7 Konversi Token Ke Bit Stream Algoritma LZ78

Semakin besar dictionary yang digunakan, akan semakin banyak pula bit yang dibutuhkan untuk membentuk sebuah token. Namun, kemungkinan banyaknya pola yang tersimpan juga akan semakin besar sehingga file akhir menjadi lebih kecil. Dengan menggunakan beberapa nilai dictionary nantinya akan dapat dianalisis kelemahan dan kelebihan menggunakan dictionary yang besar atau kecil.

Bit stream ini lalu akan di konversi menjadi karakter ASCII dengan fungsi bit_stream_to_string(). Dalam implementasinya nanti, kumpulan karakter ASCII tersebut akan disimpan ke dalam sebuah file akhir.

Dalam proses encoding, fungsi stream_to_ bit_string() akan mengubah kembali string karakter ini kedalam bentuk bit stream semula, dan dibentuk token yang sama dengan pada proses encoding. Gambar 3.8 memperlihatkan konversi bit stream ke bentuk token untuk algoritma LZ78.

Bit Stream:

1101011000

01100011

0111111011

01001011

Token: (856,c) (507,,K) Gambar 3.8 Konversi bit stream ke token algoritma LZ78 Andre Pratama : Studi Perbandingan Kinerja Algoritma Kompresi Lempel Ziv 77, Lempel Ziv 78 Dan Lempel Ziv Welch Pada File Text, 2010.

46

3.2.2.1 Algoritma LZ78 Encoding

Perancangan algoritma encoding dari LZ78 dalam bentuk flowchart dapat dilihat pada gambar 3.9 dan flowchart tersebut dikembangkan lagi menjadi pseudo code untuk menghitung kompleksitas dari algoritma LZ78 encoding.

Start source ← baca string input; maxdict ← baca batasan besar dictionary; dictionary[0] ← ””; c ← baca 1 karakter berikutnya dari source;

EOF source? Tidak word ← ””;

word+c ada dalam dictionary?

Ya word ← word+c; c ← baca 1 karakter berikutnya; Tidak

Ya

f ← index elemen dalam dictionary yang berisi word output ← output + (f,c)

Tidak

Jumlah elemen dictionary < maxdict? Ya Tambahkan word+c ke dalam dictionary pada index selanjutnya Tampilkan output Stop

Gambar 3.9 Flowchart Algoritma LZ78 Encoding Andre Pratama : Studi Perbandingan Kinerja Algoritma Kompresi Lempel Ziv 77, Lempel Ziv 78 Dan Lempel Ziv Welch Pada File Text, 2010.

47

Perancangan algoritma LZ78 encoding membutuhkan 2 buah fungsi pencarian array, yaitu fungsi untuk mengetahui apakah suatu nilai telah terdapat dalam array, dan fungsi untuk mencari index pada array yang berisi nilai tertentu. Fungsi tersebut dirancang sebagai berikut:

Tabel 3.10 Algoritma Fungsi Dalam Array LZ78 Baris 1 2 3 4 5 6 7 8 9 10 11 12

Pseudo code boolean function dalam_array(string needle, ¬array arr){ int arr_size ← count(arr); int i; for i ← 0 to arr_size do if (arr[i] == needle) then return true; end if i++; end for return false; } Total Kompleksitas

Waktu eksekusi 1+1=2 1+1=2 1 (1+1)*n=2n 1*n 1 1*n 1 4n+6

Fungsi diatas digunakan untuk memeriksa apakah suatu nilai sudah terdapat dalam array, kompleksitasnya = 4n+6 dengan notasi big O = O(n). Dimana n adalah banyak elemen yang terdapat pada array (besar dari array tersebut).

Tabel 3.11 Algoritma Fungsi Cari Array LZ78 Baris 1 2 3 4 5 6 7 8 9 10 11 12

Pseudo code string function cari_array(string needle, ¬array arr){ int arr_size ← count(arr); int i; for i ← 0 to arr_size do if (arr[i] == needle) then return i; end if i++; end for return false; } Total Kompleksitas

Waktu eksekusi 1+1=2 1+1=2 1 (1+1)*n=2n 1*n 1 1*n 1 4n+6

Fungsi diatas digunakan untuk mencari suatu nilai dalam array.

Jika

ditemukan, hasil dari fungsi adalah index dimana nilai itu ditemukan. Kompleksitas fungsi ini = 4n+6 dengan notasi big O = O(n). Dimana n adalah banyak elemen yang


48

terdapat pada array (besar dari array). Selanjutnya pada tabel 3.12 dirancang algoritma LZ78 encoding dalam bentuk pseudo code dan dihitung kompleksitasnya.

Tabel 3.12 Algoritma LZ78 Encoding Baris 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52

Pseudo code string source ← input dari user; int cmaxdict ← input dari user;

Waktu eksekusi 1 1

int maxdict ← 0; if cmaxdict == 8 then maxdict ← 256; end if if cmaxdict == 9 then maxdict ← 512; end if else if cmaxdict == 10 maxdict ← 1024; end if else if cmaxdict == 11 maxdict ← 2048; end if else if cmaxdict == 12 maxdict ← 4096; end if else if cmaxdict == 13 maxdict ← 8192; end if else if cmaxdict == 14 maxdict ← 16384; end if

1 1 1 1 1 then

1 1

then

1 1

then

1 1

then

1 1

then

1 1

int len ← strlen(source); int i ← 0; int j ← 0; array dict[0] ← ""; int key ← 0; string sub_token1 ← ""; string sub_token2 ← ""; string next_char ← ""; string word ← ""; boolean ada_dlm_arr ← false; string stream ← ""; string output ← "";

1 1+1=2 1 1 1 1 1 1 1 1 1

while (i < len) do word ← ""; next_char ← sub_str(source,i,1); j ← 0; ada_dlm_arr ← dalam_array(word.next_char, dict)

1*n 1*n (1+6*1+8)*n=15n 1*n (4C+7)*n=4Cn+7n

while (ada_dlm_arr) do j++; word ← word.next_char; if (i+j==(len+1)) then key ← cari_array(word,dict); sub_token1 ← zero_lpad(dectobin(key), cmaxdict);

1*n (1+1)*n=2n (1+1)*n=2n (1+1+1)*n=3n (4C+7)=4C+7 6*14+11+8*2logC= 8(2logC)+95


49

53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76

sub_token2 ← "00000000"; stream ← stream.sub_token1.sub_token2; break 2; end if next_char ← sub_str(source,(i+j),1); ada_dlm_arr ← dalam_array(word.next_char, dict) end while

1 (1+1+1)=3 1

key ← cari_array(word,dict); sub_token1 ← zero_lpad(dectobin(key), cmaxdict); sub_token2 ← zero_lpad(dectobin(ord (next_char)),8); stream ← stream.sub_token1.sub_token2;

(4C+7)*n=4Cn+7n (6*14+11+8*2logC )n=8(2logC)n+95n (6*8+12+8*2logC) n=8(2logC)n+60n (1+1+1)*n=3n

if (count(dict)<maxdict) then dict[] ← (word.next_char); end if

(1+1)*n=2n (1+1)*n=2C

(1+6*1+8+1)n=16n (4C+7)*n=4Cn+7n

i ← i+j+1; end while

(1+1+1)*n=3n

output ← bit_stream_to_string(stream);

(6n+181n/8+124)8

Input dari algoritma LZ78 encoding adalah string yang akan dikodekan (disimpan dalam variabel source) dan banyak bit yang dibutuhkan untuk menyimpan index (disimpan dalam variabel cmaxdict). Karena cmaxdict hanya berisi berapa banyak bit yang dibutuhkan, langkah pada baris 4 sampai dengan 25 akan membuat sebuah variabel baru (maxdict ) yang akan menampung maksimum elemen array yang dapat digunakan dalam dictionary.

Langkah pada baris 27 - 37 adalah inisialisasi awal beberapa variabel yang akan digunakan. Dictionary yang digunakan adalah variabel dict, yang dedefinisikan sebagai sebuah array. Index 0 (elemen pertama) dari dict diisi dengan string kosong. Perulangan untuk proses encoding dilakukan pada baris 39 sampai dengan 74. Proses ini dimulai dengan mengisi variabel word dengan string kosong, dan variabel next_char dengan 1 karakter berikutnya dari source. Lalu isi dari variabel word+next_char akan diperiksa apakah sudah ada dalam array dict atau tidak dengan menggunakan fungsi dalam_array. Jika tidak, fungsi cari_array akan mencari index yang berisi nilai dari variabel word pada array dict, yang hasilnya disimpan dalam variabel key. sub_token1 akan dibentuk yang berisi nilai bit dari key, dan sub_token2 yang berisi nilai bit dari karakter ASCII yang berada pada variabel next_char. sub_token1 dan sub_token2 ini akan disambung kedalam bit stream (variabel stream). Andre Pratama : Studi Perbandingan Kinerja Algoritma Kompresi Lempel Ziv 77, Lempel Ziv 78 Dan Lempel Ziv Welch Pada File Text, 2010.

50

Selanjutnya selama jumlah elemen dalam array dict tidak lebih atau sama dengan maxdict, word+next_char akan ditambahkan ke dalam array dict pada index berikutnya yang tersedia. Proses perulangan while pada baris 46 sampai dengan 60 akan dieksekusi jika word+next_char ternyata sudah ada dalam dictionary dict. Variabel word akan terus ditambah dengan isi dari variabel next_char didalam perulangan ini, dan jika word+next_char tidak ada ditemukan dalam dictionary dict, perulangan akan berhenti dan dilanjutkan dengan pembentukan token.

Pemeriksaan kondisi if pada baris 49 digunakan untuk mengatasi masalah jika pada waktu di dalam perulangan while, ditemukan tidak ada lagi karakter yang akan diproses (end of file). Masalah ini diatasi dengan menambahan “00000000” sebagai nilai sub_token2. Penambahan ini akan diatasi nantinya pada waktu proses decoding.

Walaupun ada 2 buah proses perulangan bersarang (nested loop) dengan menggunakan notasi while do, namun proses perulangan ini akan dieksekusi bergantian untuk nilai n yang telah ditetapkan. Sehingga kompleksitas akan dipilih untuk proses loop terluar yang memiliki kompleksitas lebih besar.

Kompleksitas dari LZ78 encoding : 1.

Baris 1-37 : pembacaan input dan inisialisasi awal, kompleksitas: 17.

2.

Baris 39-44 dan 62-74 : proses perulangan untuk mengkodekan string input menjadi bit stream, kompleksitas : 8cn+16(2 log C)n+196n+2C.

3.

Baris 46-49 dan 57-60 : proses perulangan untuk menambahkan variabel word, kompleksitas : 4Cn+31.

4.

Baris 49-56 : proses untuk mengatasi token terakhir, kompleksitas : 4C+82 log C+107.

5.

Baris 76 : untuk mengkonversi bit stream menjadi string karakter, kompleksitas: (6n+181n/8+124 )*8=229n+992 (dengan asumsi panjang bit stream sama dengan panjang bit source).


51

Sehingga total kompleksitas algoritma LZ78 encoding adalah: 17+8Cn +16(2log C)n+196n+2C +4c+82 log C+107+229n+992 = 8Cn+16(2 logC)n+425n+6C +1116. Dimana C adalah besar dictionary yang akan digunakan, dan n adalah panjang string yang akan dikodekan. Dari total kompleksitas tersebut, didapat notasi big O = O(Cn).

3.2.2.2 Algoritma LZ78 Decoding

Untuk proses decoding algoritma LZ78, input terdiri dari string karakter yang akan diproses (source). String ini pada dasarnya merupakan kumpulan token hasil dari proses encoding sebelumnya. Input kedua adalah banyak bit yang dibutuhkan untuk menyimpan index dictionary (disimpan dalam variabel cmaxdict).

Untuk mengukur kompleksitasnya, algoritma decoding LZ78 dirancang dalam bentuk flowchart seperti pada gambar 3.10. Lalu dari flowchart tersebut dikembangkan kedalam bentuk pseudo code seperti tabel 3.13.


52

Start

source ← baca string input; maxdict ← baca batasan besar dictionary;

Konversi source ke bentuk token; dictionary[0] ← ””; Baca 1 token berikutnya dari source

EOF token? Tidak f ← subtoken 1 dari token; c ← subtoken 2 dari token; word ← cari isi dictionary pada index ke-f output ← output + word + c

Tidak

Ya

Jumlah elemen dictionary < maxdict? Ya Tambahkan (word+c) ke dalam dictionary pada index selanjutnya Tampilkan output

Stop

Gambar 3.10 Flowchart Algoritma LZ78 Decoding


53

Tabel 3.13 Algoritma LZ78 Decoding Baris 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55

Pseudo code string source ← input dari user; int cmaxdict ← input dari user; int ctoken ← cmaxdict + 8;

Waktu eksekusi 1 1 1+1=2

string stream_input ← string_to_bit_stream (source,ctoken);

(136n + 23)*2


1 1 1 1 1 then

1 1

then

1 1

then

1 1

then

1 1

then

1 1

int len ← strlen(source); int i ← 0; array dict[0] ← ""; string sub_token1 ← ""; string sub_token2 ← ""; string fulltoken ← ""; string add ← ""; string output ← "";

1+1=2 1 1 1 1 1 1 1

while (i < len) do fulltoken ← sub_str(stream_input,i,ctoken); sub_token1 ← bintodec(sub_str(fulltoken,0, cmaxdict)); sub_token2 ← chr(bintodec(sub_str( fulltoken,cmaxdict,8)));

1*n (1+6*(c+8)+8)n (1+12*c+23+6*c+8 )*n=18cn+38n (1+12*8+23+6*8+8 +1)*n=177n

add ← dict[sub_token1].sub_token2; output ← output.add;

(1+1)*n=2n (1+1)*n=2n

if (count(dict)<maxdict) then dict[] ← add; end if

(1+1)*n=2n 1*C=1C

i ← i + ctoken; end while

(1+1)*n=2n


54

56 57 58 59 60

if sub_token2 == chr(0) then output ← sub_str(output,0,strlen(output)1); end if Total Kompleksitas

1+1=2 1+6*n+8+1+1=6n +11

Baris 1 dan 2 merupakan proses pembacaan input string yang akan dikodekan (disimpan dalam variabel source) dan batasan besar dictionary dalam bentuk banyak bit yang disediakan untuk menyimpan nilai index elemen dictionary (disimpan dalam variabel cmaxdict). Variabel cmaxdict ini akan diproses lebih lanjut pada baris 8-29 untuk mengetahui berapa besar batasan dictionary yang sebenarnya. Hasil

pemeriksaan

ini

disimpan

dalam

variabel

maxdict.

Fungsi

string_to_bit_stream(), pada baris ke 5 digunakan untuk mengkonversi string input source menjadi bentuk bit stream. Baris 31-38 digunakan untuk inisialisasi beberapa variabel yang akan digunakan selanjutnya.

Proses pengkodean kembali token kedalam bentuk string asli dimulai dari baris 40-55. Variabel sub_token1 dan sub_token2 digunakan untuk menampung masing-masing subtoken. Selanjutnya, dengan variabel sub_token1 yang berisi index dalam dictionary, akan diambil elemen dengan index tersebut, dan disambung dengan karakter dalam sub_token2, hasilnya disimpan dalam variabel add. Pemeriksaan dengan logika “if” pada baris 50 akan memeriksa apakah dictionary sudah penuh atau belum. Jika belum, tambahkan nilai dalam variabel add ke dalam dictionary. Proses ini akan terus berulang sampai tidak ada lagi token yang akan diproses.

Proses pada baris 57-60 digunakan untuk mengatasi masalah pada token terakhir. Ini terjadi jika saat proses encoding, sub_token2 pada token terakhir berisi “00000000”. Pada waktu proses decoding, nilai ini akan dikonversi menjadi karakter ASCII “null” (nilai ASCII null = 0 ) dan akan ditambahkankan pada string output, sehingga output akan bertambah 1 karakter. Untuk menghapus karakter tambahan ini, nilai sub_token2 terakhir akan diperiksa, dan jika sama dengan “null” (dengan fungsi chr(0)), 1 karakter terakhir akan dihapus.


55

Kompleksitas dari LZ78 decoding : 1.

Baris 1-3 dan 8-38 : pembacaan input dan inisialisasi awal, kompleksitas: 16.

2.

Baris 6 : proses konversi dari bit stream ke string, kompleksitas: (136n + 23)*2 = 272n+46 (dengan asumsi 1 token = 16 bit = 2 karakter).

3.

Baris 40-55: proses perulangan untuk mengkodekan bit stream menjadi token dan memproses token menjadi output berupa string akhir, kompleksitas : 24cn+221n +1C.

4.

Baris 57-60 : mengatasi masalah karakter terakhir, kompleksitas: 6n*3+13 = 18n +13(dengan asumsi satu token akan menghasilkan 3 karakter).

Sehingga

total

kompleksitas

algoritma

LZ78

decoding

adalah:

16+272n+46+24cn+221n+1C+18n+13 = 24cn+511n+1C+75. Dimana c adalah panjang bit yang diperlukan untuk menyimpan index dictionary, n adalah banyak token yang dikodekan dan C adalah jumlah batasan maximum elemen dalam dictionary . Dari kompleksitas total tersebut, didapat notasi big O = O(cn).

3.2.3 Algoritma LZW

Dasar teori untuk algoritma kompresi LZW juga telah dibahas pada bab sebelumnya. Seperti algoritma LZ78, dalam perancangan algoritma LZW, besar dictionary akan dibatasi. Jika pada saat melakukan proses kompresi dictionary sudah penuh, maka proses selanjutnya hanya menggunakan pola yang ada di dalam dictionary tanpa menambahkan index baru ke dalam dictionary.

Besar dictionary tersebut akan dirancang supaya dapat mendukung beberapa nilai tertentu yang dapat dipilih. Besar dictionary yang didukung adalah 2n, dengan n = 8,9,10,11,12 dan 13. Dimana n merupakan banyak bit yang diperlukan untuk menyimpan nilai maksimum dari index dictionary. Jika menggunakan 10 bit, dictionary itu akan mempunyai 1024 (210) buah index. Sehingga besar dictionary yang didukung adalah 256, 512, 1024, 2048, 4096, 8192, atau16384. Index array yang digunakan dimulai dari 0, jadi index maksimum = besar dictionary - 1.


56

Token dalam algoritma LZW hanya terdiri dari 1 bagian, berbentuk (f). Dimana f adalah index pada dictionary dimana pola yang ditemukan. Dibandingkan dengan algoritma LZ77, Algoritma LZW mengeliminasi perlunya sub token ke 2 dengan cara menyimpan semua karakter yang akan digunakan (dalam hal ini adalah 256 buah karakter ASCII) kedalam dictionary.

Token yang dihasilkan nantinya akan dikonversi menjadi bit stream seperti gambar 3.11. Banyak bit yang diperlukan untuk f tergantung pada input awal, jika besar dictionary ditentukan 2048, maka akan diperlukan 11 bit untuk f.

Output token:

Bit Stream:

(856) (507) (1007)

1101011000

0111111011

1111101111

Gambar 3.11 Konversi Token Ke Bit Stream Algoritma LZW

Bit stream ini lalu akan di konversi menjadi karakter ASCII dengan fungsi bit_stream_to_string(). Dalam implementasinya nanti, kumpulan karakter ASCII tersebut akan disimpan ke dalam sebuah file akhir.

Dalam proses encoding, fungsi stream_to_ bit_string() akan mengubah kembali string karakter ini kedalam bentuk bit stream semula, dan dibentuk token yang sama dengan pada proses encoding. Gambar x.x memperlihatkan konversi bit stream ke bentuk token untuk algoritma LZW.

Bit Stream:

1101011000

0111111011

1111101111

Token: (856) (507) (1007)

Gambar 3.12 Konversi Bit Stream Ke Token Algoritma LZW Andre Pratama : Studi Perbandingan Kinerja Algoritma Kompresi Lempel Ziv 77, Lempel Ziv 78 Dan Lempel Ziv Welch Pada File Text, 2010.

57

3.2.3.1 Algoritma LZW Encoding

Algoritma LZW membutuhkan 2 buah fungsi pencarian array, sehingga akan lebih mudah jika fungsi ini dipisahkan dari algoritma utama. Fungsi pertama untuk mengetahui apakah suatu nilai telah terdapat dalam array, dan fungsi kedua untuk mencari index pada array yang berisi nilai tertentu. Fungsi ini mirip dengan fungsi dalam_array() dan fungsi cari_array() pada perancangan algoritma LZ77, namun karena LZW menggunakan 256 elemen pertama dictionary untuk menyimpan semua karakter ASCII, fungsi tersebut dapat dirancang lebih efisien dengan menambah beberapa langkah tambahan.

Tabel 3.14 Algoritma Dalam Array LZW Baris 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16

Pseudo code boolean function dalam_array_lzw(string needle, array arr){ if (strlen(needle)==1)then return true; else int arr_size ← count(arr); int i; for i ← 256 to arr_size do if (arr[i] == needle) then return true; end if i++; end for end if return false; } Total Kompleksitas

Waktu eksekusi 1+1=2 1+1=2 1 1+1=2 1 2(n-256) 1(n-256) 1 1(n-256)

1 4(n-256)+6

Fungsi diatas digunakan untuk memeriksa apakah suatu nilai sudah terdapat dalam array, kompleksitasnya = 4(n-256)+6 = 4n - 1018 dengan notasi big O = O(n). Dimana n adalah banyak elemen yang terdapat pada array (besar dari array tersebut). Langkah pada baris ke-3 fungsi ini akan memeriksa apakah string yang dicari (variabel needle) hanya terdiri dari satu karakter atau tidak. Jika terdiri dari 1 karakter, maka karakter tersebut pasti sudah terdapat dalam dictionary. Hal ini dapat dipastikan, karena pada algoritma LZW, 256 karakter pertama ASCII sudah dimasukkan ke dalam dictionary sebelum proses pengkodean dimulai. Dengan demikian, fungsi ini lebih efisien dibandingkan mencari setiap input langsung pada dictionary.


58

Tabel 3.15 Algoritma Cari Array LZW Baris 1 2 3 4 5 6 7 8 9 10 11 12

Pseudo code boolean function cari_array_lzw(string needle, array arr){ if (strlen(needle)==1)then return ord(needle); else int arr_size ← count(arr); int i; for i ← 256 to arr_size do if (arr[i] == needle) then return i; end if i++; end for end if return false;

Waktu eksekusi 1+1=2

Total Kompleksitas

4(n-256)+6

1+1=2 1+1=2 1+1=2 1 2(n-256) 1(n-256) 1 1(n-256)

1

Fungsi diatas digunakan untuk mencari suatu nilai dalam array.

Jika

ditemukan, hasil dari fungsi adalah index dimana nilai itu ditemukan. Kompleksitas fungsi ini = 4(n-256)+6 = 4n - 1018 dengan notasi big O = O(n). Dimana n adalah banyak elemen yang terdapat pada array (besar dari array). Sama seperti langkah tambahan dalam fungsi dalam_array_lwz(), pada baris ke-3 fungsi ini akan diperiksa apakah string yang dicari (variabel needle) hanya terdiri dari satu karakter atau tidak. Jika terdiri dari 1 karakter, maka kembalian fungsi adalah bilangan desimal dari karakter ASCII tersebut (dengan menggunakan fungsi ord()). Hal ini dimungkinkan karena dalam inisialisasi dictionary, index 0-255 berisi karakter ASCII yang tersusun secara berurutan, sehingga index untuk karakter x sama dengan bilangan desimal ASCII dari karakter x. Dengan demikian, tidak diperlukan proses looping untuk memeriksa setiap elemen.

Untuk mengukur kompleksitasnya, algoritma LZW encoding dirancang dalam bentuk flowchart seperti pada gambar 3.13. Lalu dari flowchart tersebut dikembangkan kedalam bentuk pseudo code seperti tabel 3.16.


59

Start source ← baca string input; maxdict ← baca batasan besar dictionary; Inisialisasi 256 elemen pertama dictionary dengan 256 karakter ASCII word ← ””; c ← baca 1 karakter berikutnya dari source; EOF source? Tidak

word ← word+c;

Ya

word+c ada dalam dictionary?

Tidak f ← index elemen dalam dictionary yang berisi word output ← output + (f)

Ya

word ← c

Tidak

Jumlah elemen dictionary < maxdict? Ya Tambahkan word+c ke dalam dictionary pada index selanjutnya Tampilkan output Stop

Gambar 3.13 Flowchart Algoritma LZW Encoding Andre Pratama : Studi Perbandingan Kinerja Algoritma Kompresi Lempel Ziv 77, Lempel Ziv 78 Dan Lempel Ziv Welch Pada File Text, 2010.

60

Tabel 3.16 Algoritma LZW Encoding Baris 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57

Pseudo code string source ← input dari user; int cmaxdict ← input dari user;

Waktu eksekusi 1 1


1 1 1 1 1 then

1 1

then

1 1

then

1 1

then

1 1

then

1 1

int len ← strlen(source); int i ← 0; dict ← array of string; int key ← 0; string token ← ""; string next_char ← ""; string word ← ""; boolean ada_dlm_arr ← false; string stream ← ""; string output ← "";

1+1=2 1 1 1 1 1 1 1 1 1

for i ← 0 to 255 do dict[i] ← chr(i); i++; end for

(1+1)*256=512 (1+1)*256=512 (1+1)*256=512

while (i < len) do next_char ← sub_str(source,i,1); ada_dlm_arr ← dalam_array_lzw( (word.next_char),dict)

1*n (1+6*1+8)*n=15n (1+4D-1018)*n

if (ada_dlm_arr) then word ← word.next_char; else key ← cari_array_lzw(word,dict); token ← zero_lpad(dectobin(key), cmaxdict); stream ← stream.token; word ← next_char; if (count(dict)<maxdict) do

1*n (1+1)*n=2n (1+4D-1018)*n (6*14+11+8*2logD )n=8(2logD)n+95n (1+1)*n=2n 1*n (1+1)*n=2n


61

58 59 60 61 62 63 64 65 66 67 68 69 70 71

dict[] ← word.next_char; end if

(1+1)*D=2D

end if i++; end while

(1+1)*n=2n

if (i==len) then key ← cari_array_lzw(word,dict); token ← zero_lpad(dectobin(key),cmaxdict); stream ← stream.token; end if

1+4D-1018 8(2logD)+95 1+1=2

output ← bit_stream_to_string(stream);

(6n+181n/8+124)8

Proses pembacaan input dan inisialisasi awal dilakukan pada baris 1-36. Pada baris 5-25 adalah pembuatan variabel maxdict yang berisi nilai maksimum banyaknya elemen dalam dictionary. Hal ini diperlukan karena input dari user (variabel cmaxdict) hanya berisi banyak bit yang disediakan untuk menampung index dictionary.

Inisialisasi array dict dengan 256 karakter ASCII dilakukan pada baris 3841, dan proses perulangan untuk pengkodean input (variabel source) dimulai dari baris 43-63. Pada perulangan ini, terdapat 2 kondisi, yaitu jika variabel word+next_chat ada dalam array, proses akan langsung lanjut kepada perulangan berikutnya, tanpa menghasilkan token. Jika word+next_chat tidak ditemukan dalam dictionary, token baru akan dibuat. Proses ini akan menghasilkan bit stream yang merupakan kumpulan dari token. Bit stream ini akan dikonversi menjadi bentuk string karakter ASCII dengan fungsi bit_stream_to_string().

Langkah pada baris 65 diperlukan untuk membentuk token terakhir, karena pada waktu string source sudah end of file, variabel word masih berisi karakter yang belum diproses. Karena itu isi variabel word ini akan diproses untuk membentuk token terakhir.

Kompleksitas dari LZW encoding : 1.

Baris 1-36 : pembacaan input dan inisialisasi awal, kompleksitas: 16.

2.

Baris 38-41 : inisialisasi array dict dengan 256 karakter ASCII, kompleksitas: 1536.


62

3.

Baris 43-63: proses perulangan untuk mengkodekan string input menjadi bit stream, kompleksitas : 8Dn+8(2 logD)n+2D-1915n.

4.

Baris 65-69 : proses untuk token terakhir, kompleksitas : 4D+8(2logD)-920

5.

Baris 76 : untuk mengkonversi bit stream menjadi string karakter, kompleksitas: (6n+181n/8+124 )*8=229n+992 (dengan asumsi panjang bit stream sama dengan panjang bit source).

Sehingga total kompleksitas algoritma LZW encoding adalah: 16+1536+8Dn 2

+8( logD)n+2D-1915n+4D+8(2 logD)-920+229n+992 = 8Dn+6D +16(2logD)n-1686n +1624. Dimana D adalah besar dictionary yang akan digunakan, dan n adalah panjang string yang akan dikodekan. Dari total kompleksitas yang didapat, maka notasi big O = O(Dn).

3.2.3.2 Algoritma LZW Decoding

Untuk proses decoding algoritma LZW, input adalah string karakter yang akan diproses (source). String ini pada dasarnya merupakan kumpulan token hasil dari proses encoding sebelumnya. Input kedua adalah banyak bit yang dibutuhkan untuk menyimpan index dictionary (disimpan dalam variabel cmaxdict).

Untuk mengukur kompleksitasnya, algoritma LZW decoding dirancang dalam bentuk flowchart seperti pada gambar 3.14. Lalu dari flowchart tersebut dikembangkan kedalam bentuk pseudo code seperti tabel 3.17.


63

Start source ← baca string input; maxdict ← baca batasan besar dictionary; Inisialisasi 256 elemen pertama dictionary dengan 256 karakter ASCII Konversi source ke bentuk token; x ← baca token pertama; word ← elemen pada index x dalam dictionary; element ← word; output ← word; x ← baca 1 token berikutnya dari source; EOF token? Tidak

Tidak element ← word + karakter pertama dari word;

index x ada dalam dictionary ?

Ya

element ← elemen pada index x dalam dictionary;

Jumlah elemen dictionary < maxdict?

Tidak

Ya

Ya Tambahkan word + karakter pertama dari element ke dalam dictionary

output ← output + element word ← element ; Tampilkan output

Stop

Gambar 3.14 Flowchart Algoritma LZW Decoding


64

Tabel 3.17 Algoritma LZW Decoding Baris 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57

Pseudo code string source ← input dari user; int cmaxdict ← input dari user; int ctoken ← cmaxdict;

Waktu eksekusi 1 1 1

string stream_input ← string_to_bit_stream (source,ctoken);

(136n + 23)*2


1 1 1 1 1 then

1 1

then

1 1

then

1 1

then

1 1

then

1 1

int len ← strlen(source); int i ← 0; dict ← array of string; int key ← 0; string word ← ""; string output ← ""; string element ← "";

1+1=2 1 1 1 1 1 1

for i ← 0 to 255 do dict[i] ← chr(i); i++; end for

(1+1)*256=512 (1+1)*256=512 (1+1)*256=512

key ← bintodec(sub_str(stream_input,0, ctoken)); word ← dict[key]; output ← word; i ← ctoken;

1+12*d+23+6*d+8 =18d+32 1 1 1

while (i < len) do key ← bintodec(sub_str(stream_input,i, ctoken)); cdict ← count(dict);

1*n (1+12*d+23+6*d+8 )*n=18dn+32n 1*n

if (key>=cdict) then element ← word.sub_str(word,0,1); else

1*n (2+6*1+8)*n=16n


65

58 59 60 61 62 63 64 65 66 67 68

element ← dict[key]; end if

1*n

if (cdict < maxdict) then dict[] ← word.sub_str(element,0,1); end if

1*n (2+6*1+8)*D=16D

output ← output.element; word ← element; i ← i + ctoken; end while

(1+1)*n=2n 1*n (1+1)*n=2n

Proses pada baris 1-2 adalah pembacaan input, berupa string karakter yang akan dikodekan (disimpan dalam variabel source), dan banyak bit yang disediakan untuk menyimpan index dictionary (disimpan dalam variabel cmaxdict). Banyak bit ini harus sama dengan banyak bit yang dipakai sewaktu proses encoding. Untuk mengetahui banyak elemen yang dapat digunakan, variabel cmaxdict ini akan diperiksa, dan hasilnya disimpan dalam variabel maxdict (proses pada baris 8-29).

Pada baris ke 5, fungsi string_to_bit_stream(), digunakan untuk mengubah string karakter input menjadi bit stream. Setelah proses inisialisasi variabel pada baris 31-37, pada baris 39 adalah inisialisasi 256 elemen pertama dictionary (variabel dict) yang berupa array dengan 256 karakter ASCII. Proses pengkodean dimulai dari baris 44-67.

Langkah pertama adalah mengambil token pertama dari bit stream. karena token dalam algoritma LZW hanya berupa key yang berupa index dictionary, token ini disimpan dalam variabel key. Variabel word selanjutnya diisi dengan nilai dari dictionary pada index key. Variabel output digunakan untuk menampung string hasil pengkodean.

Untuk pembacaan token selanjutnya, akan diproses dalam perulangan while dari baris 50 sampai 67. Pada proses decoding algoritma LZW, ada kemungkinan token yang dibaca sekarang, merujuk kepada index yang belum ada dalam dictionary saat ini. Hal ini diperiksa dalam kondisi if pada baris 56. Logika ini untuk menggantikan proses pencarian elemen array dalam mengatahui apakah index key sudah ada dalam dictionary atau belum. Karena pada setiap proses perulangan while, akan dimasukkan 1 elemen ke dalam dictionary, maka jika variabel key lebih besar Andre Pratama : Studi Perbandingan Kinerja Algoritma Kompresi Lempel Ziv 77, Lempel Ziv 78 Dan Lempel Ziv Welch Pada File Text, 2010.

66

daripada jumlah elemen dalam dictionary saat ini berarti index tersebut belum ada dalam dictionary. Jika hal ini terjadi, isi dari index tersebut dapat ditebak bahwa isinya adalah variabel word + karakter pertama dari variabel word. Cara ini dimungkinkan karena pada proses encoding, dalam pembuatan token baru, dilakukan dengan cara menyambung 1 karakter dari proses sebelumnya.

Proses pada baris 61 adalah untuk membatasi penambahan dictionary hanya dalam rentang variabel maxdict. Seluruh hasil decoding disimpan dalam variabel output. Variabel ini dalam implementasinya akan ditulis kedalam sebuah file sebagai hasil proses encoding.

Kompleksitas dari LZWdecoding : 1.

Baris 1-3 dan 8-37 : pembacaan input dan inisialisasi awal, kompleksitas: 14.

2.

Baris 5 : proses konversi dari bit stream ke string, kompleksitas: (136n + 23)*2 = 272n+46 (dengan asumsi 1 token = 16 bit = 2 karakter).

3.

Baris 39-42 : inisialisasi array dict dengan 256 karakter ASCII, kompleksitas: 1536.

4.

Baris 44-48 : proses untuk token pertama, kompleksitas: 18d+35.

5.

Baris 50-68: proses perulangan untuk mengkodekan bit stream menjadi token dan memproses token menjadi output berupa string akhir, kompleksitas : 18dn+58n+16D.

Sehingga

total

kompleksitas

algoritma

LZ78

decoding

adalah:

14+272n+46+1536 +18d+35+18dn+58n+16D = 18dn+330n+16D+18d+1631. Dimana d adalah panjang bit yang diperlukan untuk menyimpan index dictionary, n adalah banyak token yang dikodekan dan D adalah jumlah batasan maximum elemen dalam dictionary . Dari kompleksitas total tersebut, didapat notasi big O = O(dn).

3.3

Pengukuran Kecepatan Algoritma

Masing-masing algoritma memerlukan waktu dalam melakukan proses encoding dan decoding. Algoritma yang efisien adalah yang membutuhkan waktu paling singkat dalam memproses file yang sama. Untuk mengukur kecepatan proses Andre Pratama : Studi Perbandingan Kinerja Algoritma Kompresi Lempel Ziv 77, Lempel Ziv 78 Dan Lempel Ziv Welch Pada File Text, 2010.

67

ini, dilakukan dengan cara mengurangi waktu saat akhir proses dengan awal proses. Seperti yang dapat dilihat pada gambar 3.15.

Deklarasi Fungsi Baca Input Baca File a←waktu saat ini Proses encoding/decoding b←waktu saat ini Buat File Hasil

Buat Statistik Proses

Lama proses = b-a

Gambar 3.15 Pengukuran Kecepatan Algoritma

Deklarasi fungsi merupakan tahap pemuatan fungsi-fungsi ke dalam memori, sehingga dapat diakses oleh algoritma nantinya. Proses baca input menangani pengiriman variabel dari browser ke web server, dan mencegah apabila terjadi input yang tidak valid. Selanjutnya file sumber dibaca dan dimuat ke dalam memori. Pembuatan variabel a untuk menyimpan waktu dilakukan setelah ketiga proses ini, karena setelah inilah proses pengkodean sebenarnya dimulai. Juga karena ketiga proses sebelumnya relatif sama untuk ketiga algoritma.

Setelah setelah proses pengkodean selesai, akan dibuat lagi variabel b yang menampung waktu saat proses selesai. Untuk menghitung kecepatan proses dilakukan dengan cara mengurangi waktu saat akhir proses (b) dengan waktu saat awal proses (a). Proses selanjutnya yaitu membuat file hasil, dan mengirim statistik mengenai proses kembali ke web browser.


68

3.4

Pengukuran Rasio Kompresi

Pengukuran rasio kompresi dimaksudkan untuk melihat seberapa besar pengurangan yang terjadi pada file hasil proses kompresi bila dibandingkan dengan file aslinya. Rasio kompresi dicari dengan rumus :

Semakin besar rasio kompresi, berarti semakin banyak pengurangan ukuran pada file hasil kompresi dibandingkan file aslinya. Rasio kompresi 60 %, berarti telah terjadi pengurangan sebanyak 60% dari ukuran file asli. Rasio kompresi dapat bernilai negatif, yang berarti ukuran file hasil kompresi lebih besar dari file asli.

3.5

Perancangan Aplikasi

Perancangan aplikasi meliputi perancangan data flow diagram (DFD) yang digunakan untuk menggambarkan alur proses kerja dan aliran data antar proses, perancangan kamus data, serta perancangan interface yang digunakan untuk sarana interaksi antara aplikasi dengan pengguna aplikasi.

3.5.1 Data Flow Diagram dan Kamus Data

DFD adalah suatu model logika data atau proses yang dibuat untuk menggambarkan darimana asal data dan kemana tujuan data yang keluar dari sistem, dimana data disimpan, proses apa yang menghasilkan data tersebut dan interaksi antaradata yang tesimpan dan proses yang dikenakan pada data tersebut. DFD menunjukan hubungan antar data pada sistem dan proses pada sistem.

Data flow diagram yang dirancang terdiri dari 2 bagian aplikasi, yaitu untuk proses kompresi, dan proses dekompresi. Karena kedua bagian ini terpisah dan dapat digunakan hanya salah satu saja ketika menggunakan aplikasi.


69

3.5.1.1 Data Flow Diagram Proses Kompresi

Untuk data flow diagram proses kompresi level 0 dapat dilihat pada gambar 3.16 berikut : Jenis_algo, Parameter_algo, File_asli

User

P.0 Aplikasi Kompresi File

File_terkompresi, Statistik_proses

Gambar 3.16 Data Flow Diagram Proses Kompresi Level 0

Data Flow Diagram Proses Kompresi Level 0 di atas menggambarkan sistem kompresi secara garis besar yang memperlihatkan masukan, proses, dan keluaran dari sistem yang akan dirancang. Proses yang terjadi pada DFD di atas dapat dijelaskan dengan menggunakan spesifikasi proses pada tabel 3.18 berikut :

Tabel 3.18 Spesifikasi Proses DFD Kompresi Level 0 No / Nama Proses

Input

Keterangan Proses

Output

P.0 / Aplikasi

Jenis_algo,

Pada proses ini, file asli

File_terkompresi,

Kompresi File

Parameter_algo, diproses menjadi file File_asli

Statistik_proses

terkompresi berdasarkan parameter dan jenis algoritma yang ditentukan oleh user

Dari DFD diatas, Proses 0 dapat dijabarkan menjadi proses 4 yang lebih kecil. Proses tersebut dapat dilihat pada gambar 3.17. Berikut ini adalah uraian proses yang terjadi pada program.


70

P.1 File_asli

Pembacaan File Asli Bit_stream_asli

P.2

Jenis_algo, Parameter_algo

Pengecekan Jenis dan Parameter Algoritma Jenis_algo, Parameter_algo

P.3

User Statistik_proses

Proses Kompresi

File_terkompresi

P.4 Pembuatan File Hasil Kompresi

Bit_stream_terkompresi

Gambar 3.17 Data Flow Diagram Proses Kompresi Level 1 Dari DFD Level 1 Proses P.0 terdapat 4 proses utama. Proses tersebut dapat diuraikan pada tabel 3.19 spesifikasi proses berikut ini : Tabel 3.19 Spesifikasi Proses DFD Kompresi Level 1 No / Nama Proses

Input

Keterangan Proses

Output

Proses P.1/ Pembacaan File Input

File_asli

File asli dari user diupload ke server,

Bit_stream_input

lalu dibaca dan disimpan ke dalam sebuah variabel sebagai bit stream.

Proses P.2/ Jenis_algo, Pengecekan Jenis Parameter_algo dan Parameter Algoritma Proses P.3/ Proses Jenis_algo,

Pemeriksaan apakah parameter dari

Jenis_algo,

user sesuai dengan jenis algoritma

Parameter_algo

File input yang telah berupa bit

Bit_stream_

Kompresi

Parameter_algo,

stream dikompresi dengan algoritma

terkompresi,

Bit_stream_asli

dan parameter yang ditentukan user.

Statistik_proses

yang digunakan.

Selama proses berlangsung, dicatat juga statistik mengenai proses. Proses P.4 /

Bit_stream_

Bit stream terkompresi hasil proses

Pembuatan File

terkompresi

kompresi dimasukkan ke dalam file

Hasil Kompresi

File_terkompresi

akhir dengan beberapa tambahan header menjadi file terkompresi


71

3.5.1.2 Data Flow Diagram Proses Dekompresi

Untuk data flow diagram proses dekompresi level 0 dapat dilihat pada gambar 3.18 berikut : File_terkompresi

P.0 Aplikasi Dekompresi File

User

File_asli, Statistik_proses

Gambar 3.18 Data Flow Diagram Proses Dekompresi Level 0

Proses yang terjadi pada diagram di atas dapat dijelaskan dengan menggunakan spesifikasi proses pada tabel 3.20 berikut :

Tabel 3.20 Spesifikasi Proses DFD Dekompresi Level 0 No / Nama Proses

Input

Keterangan Proses

Aplikasi Dekompresi File

File_terkompresi Pada proses ini, file terkompresi akan diproses

Output File_asli, Statistik_proses

untuk menghasilkan file asli (file sebelum dikompresi)

Dari DFD diatas, Proses 0 dapat dijabarkan menjadi 3 proses yang lebih kecil.. Proses tersebut dapat dilihat pada gambar 3.19, DFD Level 1 dari Proses P.0. Berikut ini adalah uraian proses yang terjadi pada program.


72

P.1 File_terkompresi

Bit_stream_terkompresi, Jenis_algo, Parameter_algo

Pembacaan File Terkompresi P.2 Statistik_proses

User

Proses Dekompresi

File_asli

P.3 Pembuatan File Hasil Dekompresi

Bit_stream_asli

Gambar 3.19 Data Flow Diagram Proses Dekompresi Level 1

Dari DFD level 1 proses dekompresi P.0 terdapat 3 proses utama. Proses tersebut dapat diuraikan pada tabel spesifikasi proses berikut ini :

Tabel 3.21 Spesifikasi Proses DFD Dekompresi Level 0 No / Nama Proses

Input

Keterangan Proses

Output

Proses P.1/ Pembacaan File Terkompresi

File_terkompresi

File terkompresi akan dikirim

Bit_stream_

(upload) ke server, diperiksa

terkompresi,

apakah file tersebut adalah hasil

Jenis_algo,

kompresi, lalu file dibaca dan dari

Parameter_algo

header file dapat diketahui jenis algoritma dan parameternya. Proses P.2/ Proses Bit_stream_

File terkompresi yang telah berupa

Bit_stream_asli,

Dekompresi

terkompresi,

bit stream dikodekan kembali untuk Statistik_proses

Jenis_algo,

mendapatkan bit stream file asli.

Parameter_algo

Selama proses berlangsung, dicatat juga statistik mengenai proses.

Proses P.4 /

Bit_stream_asli

Bit stream hasil proses dekompresi

Pembuatan File

dimasukkan ke dalam file akhir.

Hasil Dekompresi

File akhir ini harus sama dengan

File_asli

file asli (file sebelum dikompresi) Andre Pratama : Studi Perbandingan Kinerja Algoritma Kompresi Lempel Ziv 77, Lempel Ziv 78 Dan Lempel Ziv Welch Pada File Text, 2010.

73

3.5.1.3 Kamus Data

Tabel 3.22 mendaftarkan rincian data dan berkas yang digunakan pada data flow diagram (DFD) yang telah dipaparkan sebelumnya.

Tabel 3.22 Kamus Data Nama Jenis_algo

Tipe Data String

Deskripsi Jenis algoritma yang digunakan, hanya terdiri dari LZ77, LZ78 dan LZW.

Parameter_algo

Array of

Parameter yang digunakan dalam algoritma.

Integer

Untuk LZ77, terdapat 2 buah parameter, yaitu history buffer dan lookahead buffer, sedangkan untuk LZ78 dan LZW hanya terdapat 1 parameter, berupa besar dictionary.

File_asli

File

File asli yang akan dikompresi atau file hasil proses dekompresi.

File_terkompresi

File

File hasil proses kompresi.

Statistik_proses

Array of

Merupakan kumpulan dari string yang terdiri

String

dari: nama file, ukuran file, lama proses, total jumlah token, total elemen dictionary, ukuran token, rasio kompresi, output token, dan output dictionary.

Bit_stream_asli

String

Hasil dari pembacaan file asli atau pembacaan file hasil proses dekompresi, seluruh isi file dijadikan sebuah string panjang.

Bit_stream_terkompresi String

Hasil dari proses kompresi, berupa sebuah string panjang.


74

3.5.2 Perancangan Interface

Aplikasi akan dirancang dalam bentuk website yang berjalan pada sebuah web server. Interface disediakan untuk memudahkan pengguna dalam memberikan input berupa beberapa parameter yang diperlukan, serta menampilkan hasilnya.

Teori

Home

Referensi

Upload File Kompresi

Upload File Dekompresi

Pilih Algoritma Kompresi

Pengaturan Parameter Dekompresi

Help

Pengaturan Parameter Algoritma LZ77 Pengaturan Parameter Algoritma LZ78 Pengaturan Parameter Algoritma LZW Bandingkan Semua Algoritma

Gambar 3.20 Struktur Perancangan Halaman Website

Aplikasi ini terdiri dari 12 halaman web. Namun karena beberapa halaman mempunyai interface yang hampir sama, tidak semua halaman akan ditampilkan dalam perancangan interface ini.

1. Halaman Home

Halaman home adalah halaman utama dari aplikasi. Terdiri dari 3 bagian: header, content, dan footer. Header terdapat pada bagian atas halaman. Pada bagian kanan header terdapat menu navigasi berupa link untuk ke halaman lain dan ke halaman home sendiri. Content adalah bagian tengah dari halaman. Bagian ini adalah tempat dimana isi dari web. Pada halaman home, bagian content berisi 2 buah tombol untuk menentukan proses yang akan dilakukan. Tombol “COMPRESS” merupakan Andre Pratama : Studi Perbandingan Kinerja Algoritma Kompresi Lempel Ziv 77, Lempel Ziv 78 Dan Lempel Ziv Welch Pada File Text, 2010.

75

link ke halaman proses kompresi, sedangkan tombol “DECOMPRESS” adalah link ke halaman proses dekompresi. Footer terdapat pada bagian paling bawah dari halaman ini. Karena header dan footer selalu sama dan berada pada setiap halaman, dalam perancangan halaman selanjutnya, header dan footer tidak ditampilkan.

HOME

COMPRESSSION ALGORITHM LZ77 LZ78 LZW

TEORI REFERENSI HELP

Pilih proses yang akan dilakukan : COMPRESS

DECOMPRESS

Gambar 3.21 Tampilan Rancangan Halaman Home

2. Halaman Upload File Kompresi

Halaman ini tampil ketika tombol “COMPRESS” dari halaman home di pilih. Halaman upload file kompresi merupakan langkah pertama dalam proses kompresi file. Ketika tombol “Browse” di klik, akan muncul jendela explorer untuk mencari file yang akan dimampatkan. Setelah memilih file, tombol “UPLOAD FILE” adalah untuk mengirim file ke web server (upload) serta halaman berganti menuju langkah selanjutnya.


76

Langkah 1 : Pilih File

Pilih file yang akan diproses : Browse

UPLOAD FILE

Gambar 3.22 Tampilan Rancangan Halaman Upload File Source Kompresi

3. Halaman Pilih Algoritma Kompresi

Halaman ini adalah lanjutan dari halaman upload file kompresi. Setelah file yang akan dikompresi dipilih, selanjutnya pada halaman ini pengguna dapat memilih algoritma yang akan digunakan. Nama pada tombol sesuai dengan nama algoritma. Tombol “Bandingkan Algoritma” adalah link kepada halaman untuk membandingkan ketiga algoritma secara langsung.

Step 2 : Choose Algorithm

Pilih Algoritma Kompresi : LZ77 Algorithm LZ78 Algorithm LZW Algorithm Bandingkan Algoritma

Gambar 3.23 Tampilan Rancangan Halaman Pilih Algoritma Kompresi


77

4. Halaman Pengaturan Parameter Algoritma

Halaman pengaturan parameter algoritma seperti pada gambar 3.24, merupakan halaman utama untuk mengatur parameter input yang dibutuhkan oleh algoritma, pada algoritma LZ78 digunakan untuk mengatur seberapa besar history buffer dan lookahead buffer. Untuk algoritma LZ78 dan LZW, parameter input yang diperlukan adalah besar dari dictionary. Pada bagian “FILE ASLI”, ditampilkan informasi dari file yang akan dimampatkan. Sebagai contoh untuk algoritma LZ77, pada bagian “PENGATURAN LZ77” merupakan tempat pengaturan parameter. Selain pengaturan buffer, terdapat 2 buah check box, yang pertama adalah untuk mengatur apakah menggunakan fungsi-fungsi umum yang disediakan PHP atau tidak, dan yang kedua untuk menampilkan token hasil proses kompresi. Tombol “Pengaturan Awal” berfungsi untuk mengembalikan setingan ke awal (default settings).

Tombol “MULAI PROSES” digunakan untuk memulai proses kompresi. File hasil dari proses serta statistik mengenai file hasil terdapat pada bagian “HASIL PROSES KOMPRESI”. Bagian “TOKEN” merupakan bagian untuk menampilkan token hasil dari proses kompresi.

Untuk halaman Pengaturan Parameter Algoritma LZ78 dan halaman Pengaturan Parameter Algoritma LZW menggunakan tampilan interface yang hampir sama, perbedaan hanya pada bagian pengaturan parameter.


78

Langkah 3 : Pengaturan Parameter Algoritma FILE ASLI Nama File

: ____________

Jenis File

: ____________

Ukuran File

: ____________

PENGATURAN LZ77 Ukuran History Buffer

: ____________

Ukuran Lookahead Buffer : ____________

Gunakan Fungsi PHP Pengaturan Awal

Tampilkan Token

MULAI PROSES

HASIL PROSES KOMPRESI Nama File

: ____________

Ukuran File

: ____________

Lama Proses

: ____________

Total Jumlah Token

: ____________

Ukuran Token

: ____________

Rasio Kompresi

TOKEN

Gambar 3.24 Tampilan Rancangan Halaman Pengaturan Parameter Algoritma


79

5. Halaman Upload File Dekompresi

Halaman ini tampil ketika tombol “DECOMPRESS” dari halaman home di pilih. Halaman upload file dekompresi merupakan langkah pertama dalam proses dekompresi file. Ketika tombol “Browse” di klik, akan muncul jendela explorer untuk mencari file yang akan dimampatkan. Setelah memilih file, tombol “UPLOAD FILE” adalah untuk mengirim file ke web server (upload) serta halaman berganti menuju langkah selanjutnya. File yang dapat digunakan untuk proses ini hanya file yang sudah dimampatkan sebelumnya (file hasil kompresi).

Langkah 1 : Pilih File

Pilih file yang akan diproses : Browse

UPLOAD FILE

Gambar 3.25 Tampilan Rancangan Halaman Upload File Dekompresi

4. Halaman Pengaturan Parameter Dekompresi

Halaman pengaturan parameter dekompresi seperti yang terlihat pada gambar 3.25, adalah halaman lanjutan dari halaman upload file dekompresi. Pada halaman ini terdapat beberapa pengaturan yang lebih sederhana dibandingkan halaman pengaturan parameter kompresi, karena ukuran dari buffer atau dictionary terdapat dalam header file yang dimampatkan pada waktu proses kompresi. Tambahan check box “Tampilkan Dictionary” hanya terdapat jika algoritma yang digunakan adalah LZ78 dan LZW. Pilihan ini untuk menampilkan isi dictionary yang digunakan pada saat proses dekompresi.

Tombol “MULAI PROSES” digunakan untuk memulai proses dekompresi. File hasil dan statistik mengenai proses dekompresi terdapat pada bagian “HASIL Andre Pratama : Studi Perbandingan Kinerja Algoritma Kompresi Lempel Ziv 77, Lempel Ziv 78 Dan Lempel Ziv Welch Pada File Text, 2010.

80

PROSES DEKOMPRESI”. Bagian “TOKEN” dan “DICTIONARY” akan menampilkan token dan dictionary dari proses dekompresi. Bagian ini hanya tampil jika check box yang sesuai dipilih sebelum proses dekompresi dilakukan.

Langkah2 : Pengaturan Parameter Dekompresi FILE KOMPRESI Nama File

: ____________

Jenis Algoritma

: ____________

Ukuran File

: ____________

PARAMETER DEKOMPRESI Gunakan Fungsi PHP Tampilkan Token Tampilkan Dictionary

Pengaturan Awal

MULAI PROSES HASIL PROSES DEKOMPRESI Nama File

: ____________

Ukuran File

: ____________

Lama Proses

: ____________

Total Jumlah Token

: ____________

Ukuran Token @

: ____________

Rasio Kompresi

TOKEN

DICTIONARY

Gambar 3.26 Tampilan Rancangan Halaman Pengaturan Parameter Dekompresi Andre Pratama : Studi Perbandingan Kinerja Algoritma Kompresi Lempel Ziv 77, Lempel Ziv 78 Dan Lempel Ziv Welch Pada File Text, 2010.

81

3.6

Implementasi Sistem

Dari hasil perancangan sistem yang dilakukan, maka proses selanjutnya adalah tahap implementasi ke dalam bentuk program komputer. Pada tahap ini bahasa pemrograman yang digunakan adalah PHP. Input yang dibutuhkan oleh aplikasi ini mencakup berbagai jenis file, dan outputnya juga merupakan file yang berbentuk *.lz7 untuk file dengan algoritma kompresi LZ77, *.lz8 untuk file dengan algoritma kompresi LZ78, dan *.lzw untuk file dengan algoritma kompresi LZW.

Karena aplikasi dirancang dengan menggunakan bahasa pemograman PHP, sistem ini berbentuk sebuah website yang berjalan pada web server. Web server tersebut harus memiliki kemampuan dalam membaca kode PHP. Sedangkan pada sisi client, dapat diakses menggunakan web browser yang mendukung Javascript.

3.6.1 Halaman Home

Halaman home merupakan halaman pertama yang akan tampil ketika aplikasi diakses. Halaman ini berisi link untuk tahap proses kompresi dan dekompresi. Link ini dapat diakses melalui 2 buah tombol yang terdapat pada tengah halaman. Menu navigasi yang terdapat pada bagian kanan atas hanya bersifat tambahan sebagai pelengkap aplikasi, terdiri dari link ke halaman home, link ke halaman yang berisi teori tentang algoritma LZ77, LZ78 dan LZW, link ke halaman yang berisi referensi yang digunakan, dan link ke halaman help yang berisi petunjuk penggunaan aplikasi ini.


82

Gambar 3.27 Tampilan Halaman Home

3.6.2 Halaman Upload File Kompresi

Halaman ini tampil ketika tombol COMPRESS dari halaman home diklik. Halaman upload file kompresi digunakan untuk upload (mengirim ke server) file asli atau file sumber yang akan dikompresi. Ini merupakan langkah pertama dari 3 langkah dalam proses kompresi file pada aplikasi ini.

Gambar 3.28 Tampilan Halaman Upload File Kompresi


83

3.6.3 Halaman Pilih Algoritma Kompresi

Langkah kedua setelah upload file kompresi adalah menentukan algoritma apa yang akan digunakan. Terdapat 4 pilihan tombol pada halaman ini. Ketiga tombol pertama adalah menggunakan algoritma LZ77, LZ78 atau LZW untuk kompresi file. Tombol ‘Bandingkan Algoritma’, adalah link ke halaman untuk membandingkan ketiga algoritma secara langsung untuk menguji algoritma mana yang lebih efisien untuk mengompresi file yang sama.

Gambar 3.29 Tampilan Halaman Pilih Algoritma Kompresi 3.6.4 Halaman Pengaturan Parameter Kompresi LZ77

Jika pada halaman pilih algoritma kompresi, algoritma yang dipilih adalah LZ77, maka halaman selanjutnya adalah halaman pengaturan parameter LZ77. Halaman ini merupakan halaman untuk mengatur besar history buffer, lookahead buffer dan menampilkan hasil dari proses kompresi.


84

Pada bagian atas halaman, terdapat beberapa informasi mengenai file asli, meliputi: nama file, jenis file, dan ukuran file. Pada bagian tengah, ukuran masingmasing buffer dapat diatur dengan menggerakkan slider. Tombol check box ‘Gunakan Fungsi PHP’ jika dipilih, akan menngganti fungsi-fungsi dasar yang dirancang pada bab 3 dengan fungsi-fungsi yang disediakan PHP, sehingga akan mempercepat proses kompresi karena fungsi tersebut lebih efisien. Tombol check box ‘Tampilkan Token’ jika dipilih, pada akhir proses kompresi, akan ditampilkan token yang digunakan secara internal oleh algoritma, sehingga dapat dilihat proses pengkodean algoritma. Tombol ‘Pengaturan Awal’ digunakan untuk mengembalikan pengaturan buffer dan check box ke kondisi awal. Setelah pengaturan selesai, tombol ‘MULAI PROSES’ digunakan untuk memulai proses kompresi. Hasil proses akan tampil pada bagian bawah halaman, seperti pada gambar 3.30.

Gambar 3.30 Tampilan Halaman Pengaturan Parameter Kompresi LZ77


85

Gambar 3.31 Tampilan Hasil Kompresi LZ77 Setelah proses kompresi selesai, akan ditampilkan statistik dari file, yaitu: 1.

Nama File Nama File kompresi sama dengan nama file asli, tetapi dengan akhiran .lz7. Nama file ini sekaligus sebagai link untuk mendownload file kompresi.

2.

Ukuran File Ukuran file menampilkan ukuran file kompresi dalam satuan kilo byte.

3.

Lama Proses Lama proses kompresi ditampilkan dalam satuan detik

4.

Total Jumlah Token Total jumlah token menampilkan berapa banyak token yang terdapat pada file kompresi, seluruh token akan diperlihatkan pada bagian ‘TOKEN’ jika check box ‘Tampilkan Token’ dipilih.

5.

Ukuran Token Ukuran token berasal dari besar history buffer+besar lookahead buffer+ukuran 1 karakter (8 bit). Dengan mengalikan ukuran token dengan total token, hasilnya akan sama dengan ukuran file kompresi, ditambah beberapa bit header.

6.

Rasio Kompresi Rasio kompresi diperlihatkan dalam kotak. Angka 62.48% menyatakan terdapat 62.48 % pengurangan yang terjadi pada file hasil kompresi bila dibandingkan


86

dengan file aslinya. Kotak warna hijau merepresentasikan perbandingan besar file kompresi dengan file asli (keseluruhan kotak). 3.6.5 Halaman Pengaturan Parameter Kompresi LZ78

Gambar 3.32 Tampilan Halaman Pengaturan Parameter Kompresi LZ78

Halaman ini digunakan untuk mengatur parameter yang dibutuhkan untuk proses kompresi menggunakan algoritma LZ78. Tampilan halaman mirip dengan halaman pengaturan LZ77 sebelumnya, tetapi parameter yang dapat dirubah adalah besar dari dictionary yang akan digunakan. Selain itu ada tambahan check box ‘Tampilkan Dictionary’ yang jika dipilih, pada hasil kompresi akan ditampilkan isi dari dictionary yang dibuat selama proses kompresi. Setelah pengaturan selesai, tombol ‘MULAI PROSES’ digunakan untuk memulai proses kompresi. Hasil proses akan tampil pada bagian bawah halaman, seperti pada gambar 3.33.


87

Gambar 3.33 Tampilan Hasil Kompresi LZ78

Pada statistik hasil proses kompresi, informasi yang ditampilkan sama dengan pada algoritma LZ77 sebelumnya. tetapi untuk algoritma LZ78 dan LZW terdapat tambahan informasi mengenai seberapa banyak elemen dalam dictionary. Informasi ini ditampilkan pada

bagian ‘Ukuran Dictionary’. Untuk halaman

pengaturan parameter kompresi LZW, tampilan interfacenya sama dengan halaman pengaturan parameter LZ78 ini.

3.6.6 Halaman Bandingkan Algoritma

Halaman bandingkan algoritma akan tampil jika pada halaman pilih algoritma kompresi,

link untuk bandingkan algoritma dipilih. Halaman ini dapat

dilihat pada gambar 3.34. Pada halaman bandingkan algoritma, dapat dibandingkan hasil statistik ketiga algoritma untuk kompresi file asli yang sama, sehingga dapat diketahui untuk file tersebut, algoritma apa yang lebih efisien. Namun pilihan untuk menampilkan token dan dictionary tidak terdapat pada halaman ini.


88

Gambar 3.34 Tampilan Halaman Bandingkan Algoritma


89

3.6.7 Halaman Upload File Dekompresi

Halaman ini tampil ketika tombol DECOMPRESS dari halaman home diklik. Halaman upload file dekompresi digunakan untuk upload (mengirim ke server) file hasil proses kompresi, menjadi file aslinya kembali. Ini merupakan langkah pertama dari 2 langkah dalam proses kompresi file pada aplikasi ini. File yang dapat dijadikan sebagai input adalah file dengan extension .lz7, .lz8, dan .lzw.

Gambar 3.35 Tampilan Halaman Upload File Dekompresi

3.6.8 Halaman Pengaturan Parameter Dekompresi

Gambar 3.36 Tampilan Pengaturan Parameter Dekompresi


90

Tahap selanjutnya dari proses dekompresi adalah pengaturan parameter dekompresi. Namun pengaturan yang dapat diubah hanyalah untuk menggunakan fungsi PHP, menampilan token, dan menampilkan dictionary (hanya pada algoritma LZ78 dan LZW). Jenis algoritma dan ukuran buffer telah tersimpan dalam header dari masing-masing file terkompresi, sehingga pengaturan untuk buffer atau dictionary tidak diperlukan lagi.

Setelah pengaturan selesai, tombol ‘MULAI PROSES’ digunakan untuk memulai proses dekompresi. Hasil proses akan tampil pada bagian bawah halaman, seperti pada gambar 3.37.

Gambar 3.37 Tampilan Hasil Dekompresi

Informasi mengenai statistik proses, sama dengan informasi yang ditampilkan pada saat proses kompresi. Nama file hasil dekompresi juga berfungsi sebagai link untuk mengambil kembali (download) file hasil dekompresi.


BAB 4

ANALISA DAN PENGUJIAN SISTEM

4.1

Analisa Perbandingan Kompleksitas Algoritma

Total kompleksitas dari ketiga algoritma telah diperoleh dari perancangan pada

bab

3.

Selanjutnya,

kompleksitas

masing-masing

algoritma

tersebut

dibandingkan, yang mencakup perbandingan kompleksitas proses kompresi dan proses dekompresi.

4.1.1 Kompleksitas Proses Kompresi

Pada Tabel 4.1 dapat dilihat perbandingan kompleksitas proses kompresi dari algoritma Lempel Ziv 77 (LZ77), Lempel Ziv 78 (LZ78) dan Lempel Ziv Welch (LZW).

Tabel 4.1 Perbandingan Kompleksitas Kompresi 1 Algoritma

Kompleksitas

Big O

Lempel Ziv 77

10BAn+12Bn+18An+ 564n+6A+82(2 log

O (BAn)

B)n+82(2 log A)n+1024 Lempel Ziv 78

8Cn+6C +16(2 logC)n+425n+1116

O(Cn)

Lempel Ziv Welch

8Dn+6D +16(2 logD)n-1686n +1624

O(Dn)

Dengan keterangan variabel sebagai berikut: A: panjang lookahead buffer. B: panjang history buffer. Andre Pratama : Studi Perbandingan Kinerja Algoritma Kompresi Lempel Ziv 77, Lempel Ziv 78 Dan Lempel Ziv Welch Pada File Text, 2010.

92

C: besar dictionary yang akan digunakan. D: besar dictionary yang akan digunakan. n: panjang string yang akan dikodekan.

Setiap variabel (selain n) dalam implementasinya terbatas kepada nilai-nilai tertentu. Besar history buffer dapat berkisar dari 2kB, 4kB, sampai 16kB, dan besar dictionary biasanya 4kB (wikipedia,2009). Sehingga jika setiap variabel disubsitusi dengan nilai yang diasumsikan, dapat dibandingkan kompleksitasnya secara langsung, seperti yang terlihat pada Tabel 4.2.

Tabel 4.2 Perbandingan Kompleksitas Kompresi 2 Algoritma

Big O

Asumsi Variabel

Big O

Lempel Ziv 77

O (BAn)

A=32, B=2048

O(65536n)

Lempel Ziv 78

O(Cn)

C=4096

O(4096n)

Lempel Ziv Welch

O(Dn)

D=4096

O(4096n)

Seperti yang terlihat pada Tabel 4.2, kompleksitas tertinggi untuk proses kompresi adalah algoritma LZ77, selanjutnya besar kompleksitas sama untuk LZ78 dan LZW. Namun kompleksitas atau notasi big O, tidak menunjukkan kecepatan algoritma secara langsung, karena perberbedaan metoda yang digunakan ketiga algoritma, yakni pengaksesan array (pada LZ78 dan LZW) dan pencarian string karakter (LZ77).

4.1.2 Kompleksitas Proses Dekompresi

Pada Tabel 4.3 dapat dilihat perbandingan kompleksitas proses dekompresi dari algoritma Lempel Ziv 77 (LZ77), Lempel Ziv 78 (LZ78) dan Lempel Ziv Welch (LZW). Tabel 4.3 Perbandingan Kompleksitas Dekompresi 1 Algoritma

Kompleksitas

Big O

Lempel Ziv 77

12an+6bn+6a+6b+871n+76

O(an+bn)

Lempel Ziv 78

24cn+511n+1C+75

O(cn)


93

Lempel Ziv Welch

18dn+330n+16D+18d+1631

O(dn)

Dengan keterangan variabel sebagai berikut: a: panjang bit yang dibutuhkan oleh lookahead buffer. b: panjang bit yang diperlukan oleh history buffer. c: panjang bit yang diperlukan untuk menyimpan index dictionary. d: panjang bit yang diperlukan untuk menyimpan index dictionary. n: jumlah token yang akan dikodekan.

Sama seperti proses kompresi, untuk dekompresi dengan mengasumsikan variabel dengan nilai-nilai yang dijadikan referensi, maka dapat dibandingkan kompleksitasnya secara langsung, seperti yang terlihat pada Tabel 4.4

Tabel 4.4 Perbandingan Kompleksitas Dekompresi 2 Algoritma

Big O

Asumsi Variabel

Big O

Lempel Ziv 77

O(an+bn)

a=5, b= 11

O(16n)

Lempel Ziv 78

O(cn)

c=12

O(12n)

Lempel Ziv Welch

O(dn)

d=12

O(12n)

Kompleksitas tertinggi untuk proses dekompresi adalah algoritma LZ77, selanjutnya besar kompleksitas sama untuk LZ78 dan LZW. Dari hasil yang didapat, ketiga algoritma memiliki nilai kompleksitas yang lebih kecil pada proses dekompresi dibandingkan proses kompresi, algoritma seperti ini disebut juga algoritma asimeterik, karena waktu yang diperlukan untuk proses dekompresi lebih cepat daripada proses kompresi.

4.2

Pengujian Implementasi Algoritma dan Analisa Hasil

Setelah ketiga algoritma diimplementasikan dalam bentuk aplikasi dengan bahasa pemograman PHP, selanjutnya dilakukan pengujian, apakah aplikasi yang dirancang dapat melakukan proses pemampatan dan pemekaran file untuk algoritma LZ77, LZ78 dan LZW, lalu bagaimana perbandingan waktu dan rasio kompresi untuk setiap algoritma. Andre Pratama : Studi Perbandingan Kinerja Algoritma Kompresi Lempel Ziv 77, Lempel Ziv 78 Dan Lempel Ziv Welch Pada File Text, 2010.

94

4.2.1 Perangkat Pengujian

Pengujian algoritma dilakukan menggunakan komputer dengan spesifikasi sebagai berikut: •

Tipe

•

Prosesor : Intel core 2 duo T5550 (1,83 GHz)

•

Memori

•

Kartu Grafis

: Notebook Acer Aspire 4920

: 2x1024MB DDR2 : Mobile Intel Graphics Media

Accelerator X3100 •

Sistem Operasi

: Microsoft Windows 7

Karena berbasis web, untuk menjalankan aplikasi digunakan web server dan web browser dengan spesifikasi sebagai berikut: •

Web Server

: Apache 2.2.11, dengan modul PHP

Web Browser

: Mozilla Firefox 3.5

5.2.8 •

4.2.2 File Pengujian

File yang akan diuji meliputi file canterbury corpus dan beberapa file lain. canterbury corpus adalah kumpulan file yang biasa digunakan untuk menguji algoritma kompresi jenis lossless. File ini dibuat pada tahun 1997 di University of Canterbury, New Zealand. File corpus tersebut dapat di download pada alamat : http://corpus.canterbury.ac.nz/descriptions/.

Karena canterbury corpus berisi file dengan berbagai jenis extension, maka yang diuji hanyalah file dengan file dengan jenis file plain text ASCII (.txt), microsoft word document (.doc), rich text format (.rtf) dan hipertext markup language (.html). untuk file lainnya, berasal dari beberapa artikel dan novel berbahasa inggris dan indonesia yang mewakili karakteristik file yang biasa digunakan. File yang akan diuji dikelompokkan berdasarkan jenisnya : Andre Pratama : Studi Perbandingan Kinerja Algoritma Kompresi Lempel Ziv 77, Lempel Ziv 78 Dan Lempel Ziv Welch Pada File Text, 2010.

95


96

1.

File plain text ASCII (*.txt).

Tabel 4.5 File Uji Plain Text ASCII No

Nama File

Ukuran File

Keterangan

1

alice29.txt

148 KB (152.089 byte)

Bagian dari canterbury corpus, text berbahasa inggris: Alice's Adventures In Wonderland.

2

asyoulik.txt

122 KB (125.179 byte)

Bagian dari canterbury corpus, text berbahasa inggris: As You Like It, oleh Shakespeare.

3

lcet10.txt

416 KB (426.754 byte)

Bagian dari canterbury corpus, text berbahasa inggris: Workshop On Electronic Texts.

4

plrabn12.txt

470 KB (481.861 byte)

Bagian dari canterbury corpus, puisi berbahasa inggris: Paradise Lost oleh John Milton.

5

myskripsi.txt

121 KB (123.934 byte)

Skripsi ini, dari bab1 - bab4, hanya berupa text (tanpa gambar).

2.

File microsoft word document (*.doc).

Tabel 4.6 File Uji Microsoft Word Document No Nama File

Ukuran File

Keterangan

1

397 KB (407.040 byte)

Novel berbahasa inggris:

- 96 halaman

Sherlock Holmes : A Study In

study.doc

Scarlet, oleh Sir Arthur Conan Doyle. 2

cover.doc

85,5 KB (87.552 byte) -

Halaman cover skripsi

1 halaman 3

artikel.doc

241 KB (246.784 byte)

Artikel berbahasa Indonesia


97

- 24 halaman 4

skripsi.doc

730 KB (747.520 byte)

Skripsi ini, dari bab1 - bab4,

- 83 halaman

hanya berupa text (tanpa gambar).

5

3.

plestin.doc

464 KB (475.136 byte)

Text berbahasa inggris,

- 123 halaman

Palestine, oleh Harun Yahya.

File rich text format (*.rtf).

Tabel 4.7 File Uji Rich Text Format No Nama File

Ukuran File

Keterangan

1

239 KB (244.942 byte)

Skripsi ini, hanya bab 1.

bab_1.rtf

- 5 halaman 2

creation.rtf

492 KB (503.884 byte)

Text berbahasa Inggris,

- 106 halaman

Creation of Universe, oleh Harun Yahya.

3

keruntuhan.rtf

563 KB (576.557 byte)

Text berbahasa Indonesia,

- 132 halaman

Keruntuhan Teori Evolusi, oleh Harun Yahya.

4

adventures.rtf

1,21 MB (1.272.665

Text berbahasa Inggris, The

byte) - 163 halaman

Adventures of Sherlock Holmes oleh Sir Arthur Conan Doyle.

4.

File hipertext markup language (*.htm/*.html).

Tabel 4.8 File Uji Hipertext Markup Language No Nama File

Ukuran File

Keterangan

1

146 KB (149.656 byte)

Halaman awal dari

amazon.htm

http://www.amazon.com 2

google.htm

16,0 KB (16.469 byte)

Halaman awal dari http://www.google.com

3

msn.com.html

63,1 KB (64.684 byte)

Halaman awal dari


98

http://www.msn.com 4

usu.html

15,6 KB (16.000 byte)

Halaman awal dari http://www.usu.ac.id

5

yahoo!.html

151 KB (154.742 byte)

Halaman awal dari http://www.yahoo.com

4.2.3 Pengujian Parameter Algoritma

Pada aplikasi yang dirancang, setiap algoritma memiliki parameter yang dapat disesuiakan. Untuk algoritma LZ77, parameter tersebut adalah ukuran dari history buffer dan lookahead buffer, untuk algoritma LZ78 dan LZW adalah ukuran dari dictionary. Pengaturan parameter ini akan berpengaruh terhadap kinerja algoritma. Dalam pengujian algoritma terhadap file uji yang telah ditentukan, hanya 1 parameter yang akan digunakan untuk masing-masing pengujian.

Untuk mencari parameter yang optimal, dilambil sampel pengujian file alice29.txt (148 KB) yang merupakan bagian dari canterbury corpus dan merepresentasikan file teks yang umum digunakan. Masing-masing algoritma akan diuji dengan parameter yang berbeda-beda terhadap file alice29.txt.

Untuk mengetahui parameter yang efisien, dihitung performa dari masingmasing parameter, performa didapat dengan rumus: rasio kompresi/(lama proses kompresi+lama proses dekompresi).

4.2.3.1 Pengujian Parameter Algoritma LZ77

Parameter untuk algoritma LZ77 berupa history buffer dan lookahead buffer. Dalam aplikasi ini, ukuran history buffer dapat diatur dengan nilai 512, 1024, 2048, 4096 dan 8192 byte. Sedangkan untuk ukuran lookahead buffer dapat diatur dengan nilai 16, 32, 64, 128 dan 256 byte. Sehingga terdapat 25 kombinasi buffer yang dapat dipakai. Untuk mengetahui kombinasi buffer yang terbaik dilakukan pengujian, dengan hasil pengujian seperti yang terlihat dalam Tabel 4.9.


99

Tabel 4.9 Hasil Pengujian Parameter Algoritma LZ77 Ukuran Buffer1 History Lookahead

Lama proses2

Ukuran File Kompresi1

Kompresi

Performa

Dekompresi

Rasio Kompresi3

512

16

105509

30,27

4,87

30,63

0,872

512 512 512 512 1024 1024 1024 1024 1024 2048 2048 2048 2048 2048 4096 4096 4096 4096 4096 8192 8192 8192 8192 8192

32 64 128 256 16 32 64 128 256 16 32 64 128 256 16 32 64 128 256 16 32 64 128 256

109980 114921 119914 124910 97523 101248 105580 109976 114375 90840 93982 97817 101726 105638 85396 87995 91423 94932 98444 80839 82980 86080 89260 92444

30,17 31,71 33,34 34,49 48,58 48,06 48,60 49,73 52,36 81,24 80,22 81,16 82,22 83,18 140,50 138,56 137,95 139,03 141,19 245,26 243,77 242,04 241,45 242,61

4,95 4,97 4,77 4,93 4,36 4,52 4,26 4,71 4,85 4,02 3,89 4,24 4,34 4,44 3,50 3,79 3,89 4,01 3,80 3,51 3,58 3,68 3,43 3,84

27,69 24,44 21,16 17,87 35,88 33,43 30,58 27,69 24,80 40,27 38,21 35,68 33,11 30,54 43,85 42,14 39,89 37,58 35,27 46,85 45,44 43,40 41,31 39,22

0,788 0,666 0,555 0,453 0,678 0,636 0,578 0,509 0,433 0,472 0,454 0,418 0,383 0,349 0,305 0,296 0,281 0,263 0,243 0,188 0,184 0,177 0,169 0,159

Keterangan: 1

Ukuran buffer dan ukuran file kompresi dalam satuan byte.

2

Lama proses dalam satuan detik.

3

Rasio kompresi dalam satuan %.

Dalam bentuk grafik, rasio kompresi untuk masing-masing kombinasi buffer dapat dilihat pada gambar berikut:


100

Gambar 4.1 Grafik Rasio Kompresi Parameter Algoritma LZ77

Dari grafik diatas, terlihat bahwa rasio kompresi semakin meningkat seiring bertambahnya ukuran history buffer. Semakin besar ukuran history buffer, semakin besar pula kemungkinan ditemukan pola yang cocok dari lookahead buffer. Namun pertambahan lookahead buffer berpengaruh negatif terhadap rasio kompresi. Setiap penambahan lookahead buffer, rasio kompresi turun dari sebelumnya, yang berarti pada file pengujian, pola karakter yang ditemukan sebagian besar tidak lebih dari 16 karakter. Dari hasil pengujian yang dilakukan, performa maksimum untuk algoritma LZ77 didapat pada konfigurasi history buffer 512 byte, dan lookahead buffer 16 byte. Walaupun rasio kompresi yang dihasilkan bukanlah yang terbaik. Andre Pratama : Studi Perbandingan Kinerja Algoritma Kompresi Lempel Ziv 77, Lempel Ziv 78 Dan Lempel Ziv Welch Pada File Text, 2010.

101

4.2.3.2 Pengujian Parameter Algoritma LZ78

Parameter untuk algoritma LZ78 berupa besar dictionary yang disediakan untuk menyimpan pola karakter. Dalam aplikasi ini, ukuran dictionary diatur dengan nilai 256, 512, 1024, 2048, 4096, 8192 dan 16384 byte. Untuk mengetahui performa yang terbaik dilakukan pengujian, dengan hasil pengujian seperti yang terlihat dalam Tabel 4.10. Tabel 4.10 Hasil Pengujian Parameter Algoritma LZ78 Ukuran Dictionary1


Lama proses2 Kompresi

Dekompresi

Rasio Kompresi3

Performa

256

111873

12,87

4,44

26,44

1.53

512 1024 2048 4096 8192 16384

104613 98535 93425 88574 84826 82628

17,10 25,58 40,25 69,17 117,86 188,08

4,45 4,13 3,81 3,33 3,44 3,36

31,22 35,21 38,57 41,76 44,23 45,67

1.45 1.19 0.88 0.58 0.36 0.24

Keterangan: 1

Ukuran dictionary dalam satuan byte.

2


3


Dalam bentuk grafik, rasio kompresi untuk masing-masing dictionary dapat dilihat pada Gambar 4.2 dan perbandingan lama proses kompresi pada Gambar 4.3 berikut ini:

Gambar 4.2 Grafik Rasio Kompresi Parameter Algoritma LZ78


102

Gambar 4.3 Grafik Lama Proses Kompresi Parameter Algoritma LZ78 Dari hasil pengujian pada Tabel 4.10 yang diperlihatkan pada grafik dalam Gambar 4.2, rasio kompresi bertambah baik seiring pertambahan ukuran dictionary. Namun seperti yang diperlihatkan pada grafik dalam Gambar 4.3, pertambahan dictionary juga mengakibatkan bertambahnya waktu yang diperlukan untuk proses kompresi. Sedangkan untuk proses dekompresi, waktu yang diperlukan relatif tidak terpengaruh oleh pertambahan ukuran dictionary. Dengan membandingkan rasio kompresi dan lama waktu yang diperlukan, performa tertinggi didapat pada ukuran dictionary 256.

4.2.3.3 Pengujian Parameter Algoritma LZW

Parameter untuk algoritma LZW sama seperti algoritma LZ78 berupa besar dictionary yang disediakan untuk menyimpan pola karakter. Yaitu: 256, 512, 1024, 2048, 4096, 8192 dan 16384 byte. Untuk mengetahui performa yang terbaik dilakukan pengujian, dengan hasil pengujian seperti yang terlihat dalam Tabel 4.11. Tabel 4.11 Hasil Pengujian Parameter Algoritma LZW Ukuran Dictionary1


Lama proses2 Kompresi

Dekompresi

Rasio Kompresi3

Performa

256

152098

7.04

5.46

-0.01

0.00

512 1024 2048 4096 8192 16384

104730 88109 77797 72327 68453 65937

14.66 26.92 49.04 87.32 165.75 259.56

3.98 2.97 2.82 2.38 2.63 2.38

31.14 42.07 48.85 52.44 54.99 56.65

1.67 1.41 0.94 0.58 0.33 0.22


103

Keterangan: 1

Ukuran dictionary dalam satuan byte.

2


3


Dalam bentuk grafik, rasio kompresi untuk masing-masing dictionary dapat dilihat pada Gambar 4.4 dan perbandingan lama proses kompresi pada Gambar 4.5 berikut ini:

Gambar 4.4 Grafik Rasio Kompresi Parameter Algoritma LZW

Gambar 4.5 Grafik Lama Proses Kompresi Parameter Algoritma LZW

Sama seperti hasil pengujian untuk algoritma LZ78, rasio kompresi bertambah baik seiring pertambahan ukuran dictionary. Namun pertambahan Andre Pratama : Studi Perbandingan Kinerja Algoritma Kompresi Lempel Ziv 77, Lempel Ziv 78 Dan Lempel Ziv Welch Pada File Text, 2010.

104

dictionary juga mengakibatkan bertambahnya waktu yang diperlukan untuk proses kompresi. Sedangkan untuk proses dekompresi, waktu yang diperlukan lebih sedikit jika rasio kompresi semakin tinggi. Dengan ukuran dictionary 256, rasio kompresi menjadi negatif, ini dikarenakan cara kerja algoritma LZW, dimana untuk 256 elemen pertama dalam dictionary akan diisi hanya dengan karakter ASCII, sehingga pola karakter tidak dapat disimpan. Dengan membandingkan rasio kompresi dan lama waktu yang diperlukan, performa tertinggi didapat pada ukuran dictionary 512. 4.2.4 Pengujian Algoritma Setelah dilakukan pengujian untuk mencari performa maksimum masingmasing algoritma, selanjutnya dilakukan pengujian ketiga algoritma terhadap file uji yang telah ditentukan. Ukuran buffer atau dictionary yang digunakan adalah sebagai berikut: •

Algoritma LZ7, history buffer: 1024 byte, lookahead buffer: 16 byte.

•

Algoritma LZ78, dictionary: 1024 byte.

•

Algoritma LZW, dictionary : 1024 byte. Ukuran buffer atau dictionary yang digunakan merupakan parameter dengan

performa terbaik ke-2 dari pengujian sebelumnya, hal ini didasarkan karena perbedaan tipis antara hasil dengan performa pertama dan kedua. Namun rasio kompresi yang didapatkan lebih baik. Juga untuk mengakomodir keragaman file uji yang digunakan. 4.2.3.1 Pengujian File Plain Text ASCII (*.txt) Hasil rasio kompresi untuk pengujian file *.txt, diperlihatkan pada Tabel 4.12 dan Gambar 4.6: Tabel 4.12 Rasio Kompresi File *.txt Nama File

Ukuran File Asli1

Hasil

alice29.txt

152.089

97.523

35.88

98535

35.21

88109

42.07

asyoulik.txt

125.179

83.187

33.55

85311

31.85

78886

36.98

lcet10.txt

426.754

27.4180

35.75

315588

26.05

281549

34.03

plrabn12.txt

481.861

332.642

30.97

326237

32.3

285301

40.79

63.761

48.55

86918

29.87

74414

39.96

myskripsi.txt 123.934

LZ77 1

LZ78 2

Rasio

1

Hasil

LZW 2

Rasio

1

Hasil

Rasio2


105

Keterangan: 1

Ukuran file dalam satuan byte.

2


Gambar 4.6 Grafik Rasio Kompresi File *.txt Dari Gambar 4.6, terlihat bahwa algoritma LZW memberikan hasil terbaik untuk 3 file uji, sedangkan algoritma LZ77 unggul pada 2 buah file. Secara rata-rata, algoritma LZ78 memberikan rasio kompresi paling kecil dibandingkan LZ77 dan LZW. 4 file pertama berisi text berbahasa inggris, terlihat algoritma LZW memberikan hasil yang baik. Untuk file terakhir yang berbahasa Indonesia, algoritma LZ77 memberikan rasio kompresi terbaik. Hasil pengujian untuk lama proses kompresi file *.txt, diperlihatkan pada Tabel 4.13 dan Gambar 4.7 berikut: Tabel 4.13 Lama Proses File *.txt Nama File

Ukuran File Asli1

LZ77

LZ78

2

3

D

K

LZW

2

D

K

3

2

K

D3

alice29.txt

152.089

50.17

4.75

30.18

4.21

27.28

2.98

asyoulik.txt

125.179

42.27

3.86

21.78

3.35

23.39

2.90

lcet10.txt

426.754

139.68

12.86

77.77

13.37

79.45

9.44

plrabn12.txt

481.861

168.27

15.23

78.01

14.19

86.62

10.64

32.22

3.03

22.12

3.97

21.07

2.49

myskripsi.txt 123.934

Keterangan: 1


2

Lama Proses Kompresi, dalam satuan detik.

3

Lama Proses Dekompresi, dalam satuan detik.


106

Gambar 4.7 Grafik Lama Proses Kompresi File *.txt

Untuk lama proses kompresi, algoritma LZ77 memerlukan waktu paling lama untuk semua file uji, algoritma LZ78 dan LZW membutuhkan waktu yang relatif sama untuk semua file. Untuk proses dekompresi, algoritma LZW membutuhkan waktu paling sedikit. Grafik performa untuk file *.txt diperlihatkan dalam grafik berikut:

Gambar 4.8 Grafik Performa File *.txt

Dari grafik pada Gambar 4.8 terlihat bahwa untuk semua file uji *.txt, algoritma LZW memiliki performa tertinggi dibandingkan dengan algoritma LZ77 dan LZ78.

4.2.3.2 Pengujian File Microsoft Word Document (*.doc)

Hasil rasio kompresi untuk pengujian file *.doc, diperlihatkan pada Tabel 4.14 dan Gambar 4.9 berikut: Andre Pratama : Studi Perbandingan Kinerja Algoritma Kompresi Lempel Ziv 77, Lempel Ziv 78 Dan Lempel Ziv Welch Pada File Text, 2010.

107

Tabel 4.14 Rasio Kompresi File *.doc Nama File

Ukuran File Asli1

LZ77 1

Hasil

LZ78 2

Rasio

1

LZW 2

1

Hasil

Rasio

Hasil

Rasio2

study.doc

407.040

239335

41.2

315754

22.43

304652

25.15

cover.doc

87.552

98139

-12.09

92608

-5.77

88181

-0.72

artikel.doc

246.784

181862

26.31

279718

-13.35

219908

10.89

skripsi.doc

747.520

409672

45.2

726330

2.83

637712

14.69

plestin.doc

475.136

288774

39.22

390985

17.71

424507

10.66

Keterangan: 1


2


Gambar 4.9 Grafik Rasio Kompresi File *.doc

Dalam proses uji kompresi file *.doc, pada hampir semua pengujian, algoritma LZ77 memberikan rasio kompresi terbaik, algoritma LZ78 dan LZW cenderung lemah untuk file *.doc. Hal ini dikarenakan file *.doc memiliki haeder sebelum bagian text dari dokumen, sehingga bagian header inilah yang banyak disimpan sebagai pola karakter. Untuk algoritma LZ77, history buffer selalu bergerak sehingga pola karakter selalu dapat update. Untuk file cover.doc, semua algoritma memperoleh rasio negatif, yang berarti ukuran file hasil lebih besar daripada file aslinya. Pada cover.doc, hanya terdapat sedikit text, sehingga lebih banyak header/footer untuk file *.doc. Hasil lama proses kompresi untuk pengujian file *.doc, diperlihatkan pada Tabel 4.15 dan Gambar 4.10 berikut:


108

Tabel 4.15 Lama Proses File *.doc Nama File

Ukuran File Asli1

LZ77 2

LZ78 3

2

LZW 3

2

K

D

K

D

K

D3

study.doc

407.040

134.81

10.94

83.68

13.22

86.27

11.04

cover.doc

87.552

53.39

4.33

22.25

4.00

18.11

3.22

artikel.doc

246.784

110.38

7.47

49.41

11.30

47.50

7.81

skripsi.doc

747.520

216.48

17.09

143.01

29.73

143.89

22.64

plestin.doc

475.136

157.33

12.92

118.49

16.36

107.32

15.21

Keterangan: 1


2


3


Gambar 4.10 Grafik Lama Proses Kompresi File *.doc

Hampir sama dengan pengujian file *.txt, untuk file *.doc, algoritma LZ77 memerlukan waktu paling lama untuk proses kompresi, sedangkan untuk algoritma LZ78 dan LZW, waktu yang dibutuhkan relatif sama untuk semua file uji. Performa algoritma untuk file *.doc diperlihatkan dalam Gambar 4.11 berikut ini:


109

Gambar 4.11 Grafik Performa File *.doc

Dari grafik terlihat bahwa algoritma LZ77 memiliki performa tertinggi pada semua file, kecuali file cover.doc. Sedangkan performa untuk algoritma LZ78 menjadi negatif pada 2 file uji, dikarenakan ukuran file akhir yang lebih besar dari pada file asli.

4.2.3.3 Pengujian File Rich Text Format (*.rtf)

Hasil rasio kompresi untuk pengujian file *.rtf, diperlihatkan pada Tabel 4.16 dan Gambar 4.12 berikut:

Tabel 4.16 Rasio Kompresi File *.rtf Nama File

Ukuran File Asli1

LZ77 1

LZ78 2

1

Hasil

Rasio

Hasil

LZW 2

Rasio

1

Hasil

Rasio2

bab_1.rtf

244.942

60292

75.39

192280

21.5

210709

13.98

creation.rtf

503.884

245638

51.25

389585

22.68

371577

26.26

keruntuhan.rtf

576.557

271975

52.83

470012

18.48

500470

13.2

adventures.rtf

1.272.665 548845

56.87

1094357

14.01

961874

24.42

Keterangan: 1


2



110

Gambar 4.12 Grafik Rasio Kompresi File *.rtf

Algoritma LZ77 memberikan rasio kompresi terbaik untuk semua file *.rtf yang diujikan. Algoritma LZ78 dan LZW menghasilkan rasio kompresi yang tidak terlalu memuaskan untuk file *.rtf. Hasil lama proses kompresi untuk pengujian file *.rtf, diperlihatkan pada Tabel 4.17 dan Gambar 4.13 berikut:

Tabel 4.17 Lama Proses File *.rtf Nama File

Ukuran File Asli1

LZ77

LZ78

2

D

K

3

LZW

2

D

K

3

2

K

D3

bab_1.rtf

244.942

56.70

2.57

82.46

7.92

82.97

7.39

creation.rtf

503.884

203.54

9.75

152.21

14.69

180.26

12.90

keruntuhan.rtf

576.557

229.76

11.05

179.90

17.80

202.67

17.36

adventures.rtf

1.272.665

475.91

22.58

354.81

44.78

456.43

33.99

Keterangan: 1


2


3



111

Gambar 4.13 Grafik Lama Proses Kompresi File *.rtf

Algoritma LZ77 pada hampir semua file uji, membutuhkan waktu paling lama untuk proses kompresi file *.rtf. waktu paling cepat diperoleh algoritma LZ78. Untuk perbandingan performa kompresi file *.rtf, diperlihatkan pada Gambar 4.14 berikut:

Gambar 4.14 Grafik perbandingan Performa File *.rtf

Untuk file *.rtf, performa terbaik diperoleh algoritma LZ77, walaupun algoritma ini membutuhkan waktu yang lebih lama daripada algoritma LZ77 dan LZ78, namun memberikan rasio kompresi yang tinggi.

4.2.3.4 Pengujian File hipertext markup language (*.htm/*.html)

Hasil rasio kompresi untuk pengujian file *.html, diperlihatkan pada Tabel 4.18 dan Gambar 4.15 berikut:


112

Tabel 4.18 Rasio Kompresi File *.htm/*.html Nama File

Hasil

Rasio

Hasil

Rasio

Hasil

amazon.htm

Ukuran File Asli1 149.656

LZ77

52873

64.67

134102

10.39

125315

16.26

google.htm

16.469

9391

42.98

11770

28.53

11910

27.68

msn.com.html

64.684

33028

48.94

52537

18.78

47886

25.97

usu.html

16.000

7306

54.34

9740

39.13

9843

38.48

yahoo!.html

154.742

65734

57.52

125075

19.17

124820

19.34

1

LZ78 2

1

LZW 2

1

Rasio2

Keterangan: 1


2


Gambar 4.15 Grafik Rasio Kompresi File *.html

Dari hasil pengujian file *.html, algoritma LZ77 memberikan rasio kompresi terbaik, jika dibandingkan algoritma LZ78 dan LZW. Rasio kompresi untuk algoritma LZ78 dan LZW relatif sama untuk semua file uji. Hasil lama proses untuk pengujian file *.rtf, diperlihatkan pada Tabel 4.19 dan Gambar 4.16


113

Tabel 4.19 Lama Proses File *.htm/*.html Nama File

Ukuran File Asli1

LZ77

LZ78

2

D

K

3

LZW

2

D

K

3

2

K

D3

amazon.htm

149.656

44.82

2.20

44.37

5.56

56.36

4.47

google.htm

16.469

6.96

0.38

4.95

0.46

6.18

0.44

msn.com.html

64.684

27.26

1.36

19.06

2.16

24.12

1.72

usu.html

16.000

5.56

0.30

4.68

0.41

5.36

0.33

yahoo!.html

154.742

56.47

2.66

47.29

5.16

58.49

4.41

Keterangan: 1


2


3


Gambar 4.16 Grafik Lama Proses Kompresi File *.html

Kecepatan kompresi terbaik untuk file *.html diperoleh oleh algoritma LZ78, yang membutuhkan waktu kompresi lebih sedikit dibandingkan algoritma LZ77 dan LZW. Algoritma LZW membutuhkan waktu paling lama pada hampir semua file uji. Hasil perbandingan performa algoritma untuk file *.html diperlihatkan dalam grafik pada Gambar 4.17 berikut:


114

Gambar 4.17 Grafik Perbandingan Performa Kompresi File *.html

Dari grafik diatas, terlihat bahwa algoritma LZ77 memiliki performa terbaik pada semua file uji *.html. Performa algorita LZW menjadi yang terburuk pada 3 file uji.


BAB 5

KESIMPULAN DAN SARAN

5.1 Kesimpulan

Setelah melakukan studi literatur, perancangan, implementasi, analisis dan pengujian aplikasi untuk membandingkan kinerja algoritma kompresi LZ77, LZ78 dan LZW, maka dapat disimpulkan:

1.

Kompleksitas algoritma secara berturut-turut dari yang paling tinggi ke terendah adalah Algoritma LZ77, Algoritma LZ78, dan Algoritma LZW.

2.

Untuk ketiga algoritma, waktu yang diperlukan untuk proses kompresi lebih lama bila dibandingkan dengan waktu untuk proses dekompresi. Dengan kata lain, proses dekompresi lebih cepat dibandingkan dengan proses kompresi.

3.

Penambahan besar dictionary (atau buffer) pada setiap algoritma, memberikan peningkatan hasil pada rasio kompresi, namun membutuhkan waktu proses yang semakin lama.

4.

Pada pengujian file *.txt, *.doc, dan *.rtf rata-rata algoritma LZ77 membutuhkan waktu paling lama dalam proses kompresi. Untuk file *.html, waktu proses kompresi terlama diperoleh algoritma LZW.

5.

Pada pengujian file *.txt, rasio kompresi terbaik diperoleh algoritma LZW, sedangkan untuk file *.doc, *.rtf, dan *.html, rasio terbaik diperoleh algoritma LZ77.

6.

Dengan membandingkan rasio kompresi dan lama proses, performa terbaik untuk file *.txt, diperoleh algoritma LZW, sedangkan untuk file *.doc, *.rtf, dan *.html, performa terbaik diperoleh algoritma LZ77.


116

5.2 Saran

Beberapa saran untuk pengembangan dan perbaikan diantaranya:

1.

Membandingkan algoritma LZ77, LZ78, dan LZW dengan algoritma kompresi lainnya, seperti Huffman, DMC, Arithmatic Coding, dll.

2.

Mengembangkan algoritma LZ78 dan LZW agar dictionary dapat terus diperbaharui untuk pola karakter yang jarang digunakan pada saat dictionary telah penuh, sehingga perbandingan dengan algoritma LZ77 lebih seimbang.


117

DAFTAR PUSTAKA

Achou, M., et al. Olson, P. (ed.). 2007. PHP Manual. PHP Documentation Group. Chandra, A. J. 2006. Analisa perbandingan kinerja algoritma kompresi huffman, LZW (Lempe-Ziv-Welch) dan DMC (Dynamic Markov Compresions). Universitas Kristen Petra. Skripsi tidak diterbitkan. Cormen T. H., et al. 2001. Introduction to Algorithms, Second Edition. New York: The MIT Press. Feldspar A. 25 Mei 2009. An Explanation of the Deflate Algorithm. http://zlib.net/ feldspar .html Growth of Functions. 29 Mei 2009. http://www.cs.odu.edu/~Etoida/nerzic/content /function/growth.html. Linawati dan Panggabean, H.P. 2004. Perbandingan Kinerja Algoritma Kompresi Huffman, LZW, dan DMC pada Berbagai Tipe File. Integral Vol. 9 No. 1: hal. 7-16.Maret 2004 Munir, R. 22 Agustus 2009. Kompleksitas Algoritma. www.informatika.org/~rinaldi/ matdis/2005-2006/Kompleksitas Algoritma.ppt. Pu, Ida Mengyi. 2006. Fundamental Data Compression. London: ButterworthHeinemann. Salomon, D. 2007. Data Compression The Complete Reference. 4th Edition. London: Springer-Verlag. Salomon, D. 2008. A Concise Introduction to Data Compression. London: SpringerVerlag. Suksmono, A. B. 22 Agustus 2009. 2. Algoritma, Kompleksitas dan Teori Bilangan. radar.ee.itb.ac.id/~suksmono/Lectures/el2009/ppt/2. Algoritma, Kompleksitas dan Teori Bilangan.pdf. Wikipedia. 02 April Big_O_notation.

2009.

Big

O

notation.

http://en.wikipedia.org/wiki/

Wikipedia. 31 Januari 2009. LZ77 and LZ78. http://en.wikipedia.org/wiki/LZ77_ and_LZ78.


STUDI PERBANDINGAN KINERJA ALGORITMA KOMPRESI LEMPEL ZIV 77, LEMPEL ZIV 78 DAN LEMPEL ZIV WELCH PADA FILE TEXT SKRIPSI ANDRE PRATAMA

Recommend Documents