Context model automata CMA pada prediction by partial match PPM untuk kompresi teks

Abstract

Context model automata (CMA) adalah salah satu teknik pemodelan berbasis context untuk kompresi data yang menggunakan finite state automata (FSA) (Franti dan Hatakka, 1998). CMA dapat memodelkan context sampai panjang context minimum (order-1) yang terdapat dalam setiap state pada automata. CMA juga bisa digunakan sebagai alat bantu dalam menganalisis perilaku dari model-model context dan mendesain model context yang baru. Oleh karena itu CMA dapat mensimulasikan metode- metode pemodelan context yang lain. Seperti pemodelan berbasis context lainnya CMA hanya ditujukan untuk memodelkan data saja. Oleh karena itu, CMA harus diintegrasikan dengan beberapa komponen lain agar dapat membentuk suatu teknik pemampatan yang utuh. Prediction By Partial Match (PPM) merupakan salah satu metode yang menggunakan context dalam proses penghitungan distribusi peluang karakter-karakter yang akan dikodekan. Ide dasar dari PPM adalah melakukan prediksi karakter apa yang akan mengikuti rangkaian karakter yang telah muncul dalam model (context). Dari sinilah peluang setiap karakter yang mungkin mengikuti context tersebut didapatkan. Dalam penggunaan context yang akan memprediksi sebuah karakter yang akan dihitung peluangnya PPM memakai panjang context yang berbeda-beda. Jika suatu panjang context tidak dapat memprediksi sebuah karakter, maka PPM akan beralih pada panjang context lain yang lebih pendek (satu karakter). Proses perpindahan dari satu context ke context yang lain ini dilakukan oleh metode escape. Dalam proses pergantian penggunaan context untuk memprediksi peluang ini harus dapat dipastikan agar tidak ada satu karakter yang diprediksi oleh dua context yang berbeda agar peluang setiap karakter dapat dihitung lebih akurat. Permasalahan ini ditangani oleh sebuah metode yang disebut exclusion. Prediction By Partial Match (PPM) merupakan sebuah model peluang yang terbaik. PPM dapat memodelkan sebuah file sehingga dihasilkan file terkompresi dengan bit rate 2.2 per karakter. Tetapi disamping keunggulannya ini PPM cukup sulit dipelajari perilakunya. Oleh karena itu digunakan konsep CMA untuk mensimulasikan proses-proses yang terjadi pada PPM. Penelitian ini bertujuan untuk mempelajari algoritma CMA yang diterapkan pada konsep PPM, merancang dan menganalisis algoritma, serta membuktikan bahwa segala proses yang ada pada CMA setelah diterapkan pada PPM tidak melanggar segala ketentuan/syarat yang ada pada CMA. Dalam penelitian ditemukan bahwa perilaku dari PPM adalah selalu melakukan pembuatan context, perkembangan context sangat cepat, dan pengkodean suatu karakter selalu dimulai dari context dengan panjang maksimum. Sementara kelebihannya adalah dapat mengadaptasi sumber data dengan cepat, mempunyai initial automata (automata awal) yang baik, dan dapat menghitung peluang lebih akurat. Selain itu, penerapan konsep CMA pada PPM tidak melanggar segala ketentuan/syarat yang ada pada CMA. Oleh karena itu, CMA dapat digunakan untuk mensimulasikan PPM. Sedangkan kompleksitas algoritma PPM sendiri adalah O(n)