1.
PENDAHULUAN
1.1. Latar Belakang Masalah Kompresi data merupakan suatu proses pengubahan ukuran suatu file atau dokumen menjadi lebih kecil secara ukuran. Berkembangnya teknologi hardware dan software yang makin canggih dan kompleks menuntut adanya efisiensi dalam hal penyimpanan data dan memori. Karena itulah, kompresi data merupakan hal yang penting dalam proses transfer dan akselerasi dalam transmisi data serta efisiensi kapasitas penyimpanan data atau dokumen. Berbagai algoritma kompresi data, baik itu data berupa teks, suara atau audio, atau video telah dirintis dan ditemukan. Jenis kompresi terbagi dua, yaitu: kompresi Lossy dan kompresi Lossless. Kompresi Lossy adalah jenis kompresi yang menimbulkan perubahan data setelah terjadi proses kompresi. Kompresi Lossy sesuai dengan file multimedia tipe audio, video (image bergerak), dan digital image. Adapun algoritma yang sesuai dengan jenis kompresi ini adalah metode Bit Rate, Kuantisasi, dan Fourier Transform. Jenis kedua adalah kompresi Lossless dimana tidak terjadi perubahan pada data sesudah terjadi proses kompresi. Contoh algoritma dari kompresi ini adalah Algoritma Huffman yang sangat terkenal, lalu algoritma Dynamic Markov, Run Length Encoding, LZW, Burrows Wheeler Transform, dan algoritma PPM (Prediction by Partial Matching). Proses kompresi dimulai dari inputan berupa context/data yang akan diolah menjadi suatu pemodelan. Dari tahap pemodelan akan didistribusikan suatu probabilitas dari karakter/simbol yang muncul. Simbol/karakter yang muncul akan dikodekan sesuai tipe algoritma yang dipilih, tergantung apakah algoritma tersebut adalah two-pass atau one-pass, lossy atau lossless, symbolwise atau dictionary. Dari kode inilah terbentuk bit bit yang lebih sederhana (proses kompresi) dari simbol atau karakter yang diinput.
15
Pada Tugas Akhir ini, penulis mengimplementasikan kompresi dengan algoritma PPM (Prediction by Partial Matching). Algoritma ini termasuk tipe lossless dan dictionarybased. Algoritma ini diperkenalkan pada tahun 1984 oleh Cleary dan Witten. Algoritma ini cukup handal untuk penanganan kompresi jenis teks dengan implementasinya dalam program kompresi lossless terbaik untuk natural language text. Kompresi adalah gabungan dari teknik pemodelan (pengetahuan manusia) dan pengkodean (komputasi mesin). Algoritma ini men-generate prediksi untuk tiap simbol input berdasarkan konteks sebelumnya. Prediction by Partial Matching (PPM) merupakan teknik kompresi data berdasarkan context modeling dan prediksi. Model PPM memodelkan set simbol sebelumnya dalam stream simbol yang tidak terkompresi untuk memprediksi simbol berikutnya pada stream. Teknik ini telah diimplementasikan pada file format ZIP dan 7z. Algoritma PPM memiliki persamaan dengan algoritma Huffman, yaitu melakukan perhitungan probabilitas untuk tiap karakter. Namun, metode Huffman hanya melakukan perhitungan probabilitas murni atas tiap karakter. Perhitungan probabilitas murni dari tiap karakter tersebut diperbaiki pada metode PPM dengan mengolah kembali probabilitas karakter tersebut dalam bentuk modelling dan encode yang menggunakan metode Arithmetic Coding. Sehingga hasil code yang dihasilkan pada metode PPM hanya satu code output, sedangkan untuk metode Huffman memiliki code output yang berbeda-beda sesuai karakter yang diencode. 1.2. Perumusan Masalah Perumusan masalah yang akan dibahas berdasarkan latar belakang yang telah dijelaskan, antara lain: 1. Bagaimana cara mengimplementasikan algoritma kompresi Prediction by Partial Matching (PPM) pada file tipe teks (dokumen). 2. Bagaimana pengaruh algoritma kompresi Prediction by Partial Matching (PPM) pada hasil kompresi.
16
3. Bagaimana performansi dari penerapan algoritma Prediction by Partial Matching (PPM) ditinjau dari rasio kompresi. Hipotesis awal dari Tugas Akhir ini adalah metode algoritma kompresi Prediction by Partial Matching (PPM) adalah lebih baik dalam kompresi jenis teks dibanding metode lain, seperti Huffman. 1.3. Batasan Masalah Batasan masalah untuk Tugas Akhir ini adalah : 1. Data yang dikompresi adalah jenis file teks, seperti: Canterbury Corpus (.txt, .c, .htm), dan file uji tambahan seperti: .doc, .xls, .pdf, .rtf. 2. Kompresi dilakukan secara offline. 3. Hal yang akan diukur pada kompresi adalah size kompresi (rasio kompresi). 4. Text formatting menggunakan kode ASCII 8 bit (256 simbol). 1.4. Tujuan Tujuan dari dilakukannya penelitian ini adalah : 1. Mengimplementasikan pengembangan dari teknik algoritma Prediction by Partial Matching (PPM) untuk kompresi teks, dengan menggunakan varian PPM tipe D. 2. Menganalisis dan membandingkan mutu/performansi dilihat dari rasio kompresi dari teknik algoritma Prediction by Partial Matching (PPM) dengan metode lain yang terkenal, seperti metode Huffman. 1.5. Metodologi Penyelesaian Masalah a. Studi Literatur Mengumpulkan, mempelajari berbagai bahan literatur terkait dengan kompresi data, macam-macam algoritma kompresi, serta melakukan berbagai pencarian referensi dan sumber-sumber relevan lain sebagai acuan dalam pembuatan Tugas Akhir ini. 17
b. Analisis dan Desain Melakukan analisis serta perancangan desain dan sistem yang terstruktur dalam implementasi Tugas Akhir. c. Implementasi sistem Melakukan proses pembangunan perangkat lunak/Coding sebagai realisasi implementasi algoritma kompresi Prediction by Partial Matching. d. Analisis hasil dan Testing Pada tahap ini dilakukan kegiatan analisis terhadap hasil pengerjaan dan proses penyusunan perangkat lunak. Lalu dilakukan uji terhadap perangkat yang telah dibangun apakah telah berjalan sesuai prosedur dan algoritma. Pengujian juga dilakukan dengan membandingkan ukuran file kompresi dengan file original secara keseluruhan. e. Penyusunan laporan Pada tahap terakhir ini akan dilakukan penyusunan laporan hasil penelitian yang telah dilakukan sejak awal dan rincian langkah-langkah pengerjaan Tugas Akhir. 1.6. Sistematika Penulisan Sistematika Penulisan dalam Tugas Akhir ini adalah sebagai berikut : Bab 1. Pendahuluan Pengenalan dan teori singkat mengenai dunia kompresi. Bab 2. Landasan Teori Pemahaman serta penggalian bahan mengenai kompresi dan algoritma PPM, dan algoritma Huffman. Bab 3. Analisis Kebutuhan Sistem dan Perancangan Sistem Gambaran spesifikasi sistem aplikasi perangkat lunak yang akan dibangun berdasarkan algoritma yang diajukan. Bab 4. Implementasi dan Analisis Hasil Pengujian
18
Proses pembuatan aplikasi perangkat lunak sesuai dua algoritma yang diajukan. Selanjutnya, dilakukan analisis dan perbandingan performansi atas aplikasi perangkat lunak yang dibangun. Bab 5. Kesimpulan dan Saran Tahap akhir sebagai penyajian kesimpulan serta saran dari pengerjaan Tugas Akhir.
19
