Analisa dan Perancangan Aplikasi Kompresi File Dengan Menggunakan Metode Byte Pair Encoding

Analisa dan Perancangan Aplikasi Kompresi File Dengan Menggunakan Metode Byte Pair Encoding Loka Andriyan1 ,Ummul Khair2 ,Abdul Jabbar3 Mahasiswa Jurusan Teknik Informatika Sekolah Tinggi Teknik Harapan Medan 2,3 Dosen Jurusan Teknik Informatika Sekolah Tinggi Teknik Harapan Medan Jl. HM Jhoni No 70 Medan, Indonesia [email protected]

1

ABSTRAK Kompresi sangat diperlukan baik pada pemanfaatan penyimpanan yang efisien maupun pada komunikasi jaringan. Kebutuhan akan kompresi telah melahirkan beberapa metode yang dapat di-implementasikan pada kegiatan komunikasi pada jaringan maupun pada kegiatan penyimpanan. Algoritma byte pair encoding merupakan algoritma kompresi yang memanfaatkan munculnya pasangan byte karakter yang berulang atau frekuen. Pasangan byte karakter yang berulang tersebut di data dan disubstitusikan dengan sebuah byte karakter pengganti yang mana byte karakter pengganti tersebut tidak terdapat pada deret byte karakter dari file. Beberapa file multimedia seperti gambar, video dan suara secara umum memiliki deret byte karakter yang sama dalam jumlah yang besar dan saling berurutan sehingga algoritma byte pair encoding dapat memiliki tingkat kompresi yang cukup baik pada beberapa file tersebut. Pada file biasa seperti dokumen dan file aplikasi, tingkat kompresi sangat bergantung pada jumlah pasangan byte karakter yang terdapat pada isi file tersebut. Tugas akhir ini akan membahas tahapan dan proses yang dibutuhkan dalam penelitian dalam rangka mengembangkan aplikasi kompresi pada file menggunakan algoritma byte pair encoding. Keywords : Kompresi, Byte Pair Encoding, File, Multimedia, Dokumen, Aplikasi, Karakter, Byte. ABSTRACT Compression is indispensable both in the utilization of efficient storage and the communications network. The need for compression has spawned a number of methods that can be implemented in communication activities on the network or on storage activities. Byte pair encoding algorithm is a compression algorithm that utilizes the emergence of a recurring character byte pairs or frekuen. Couple byte characters that are repeated in the data and substituted with an alternate character byte which are not contained in the substitute sequence byte characters from the file. Some multimedia files such as pictures, video and sound in general has the same character byte sequence in large numbers and each pair sequentially so that the algorithm byte encoding can have a pretty good compression rate in multiple files. At regular files such as documents and application files, the compression rate is very dependent on the number of pairs byte characters contained in the file contents. This final project will discuss the stages and processes involved in research in order to develop applications using a file compression algorithm byte pair encoding. Keywords : Compression, Byte Pair Encoding, File, Multimedia, Dokumen, Aplikasi, Karakter, Byte.

1.

PENDAHULUAN Pada zaman sekarang ini komputer telah berkembang mulai dari perangkat pengolah data menjadi perangkat yang serba bisa. Perkembangan ini didukung dengan berkembangnya tekhnologi manufaktur dan tekhnologi komunikasi. Perlahan tapi pasti komputer telah menggantikan metode manual manusia yang membutuhkan biaya, waktu dan ruang yang besar. Pada awal komputer dikembangkan, kapasitas penyimpanan atau memori merupakan komponen yang sangat mahal dan sulit untuk diperoleh. Inovasi – inovasi dalam bidang komputer banyak terhambat dikarenakan alasan kapasitas penyimpanan atau memori yang masih langka dan mahal. Inovasi perangkat lunak dan aplikasi

melahirkan dilema baru, yaitu semakin besarnya ukuran file atau berkas yang dihasilkan. Kompresi data atau data compression merupakan bidang yang berfokus pada membentuk output file dengan ukuran yang kecil dari file yang berukuran besar. Dengan kata lain bidang kompresi data bertujuan untuk mengatasi masalah-masalah yang diakibatkan oleh besarnya ukuran atau kapasitas file. Dalam bidang kompresi data telah banyak muncul metode – metode yang dapat digunakan dalam kompresi data. Salah satu metode kompresi data yang cukup dikenal adalah metode Byte Pair Encoding, dimana metode ini merupakan metode tipe lossless yang artinya file atau berkas yang telah dikompresi dapat direkonstruksi ulang menjadi file sebelum

dikompresi. Byte Pair Encoding merupakan metode kompresi sederhana yang mana sederetan data yang memiliki karakter atau symbol yang sama diwakili oleh sebuah karakter yang tidak terdapat pada data tersebut. Mekanisme proses kompresi dan dekompresi file menggunakan metode Byte Pair Encoding dan tingkat rasio hasil kompresi dari metode tersebut serta file text yang telah dikompresi dapat direkonstruksi kembali dengan baik. Berdasarkan uraian diatas penulis bermaksud untuk mengangkat tema kompresi pada file sebagai tugas akhir (skripsi) dengan judul “Analisa dan Perancangan Aplikasi Kompresi File Dengan Menggunakan Metode Byte Pair Encoding”. Seperti yang telah penulis uraiakan diatas penulis memilih metode ini karena selain metode ini menggunakan algoritma yang lebih sederhana juga metode ini memiliki output atau nilai keluaran yang tergolong baik. 1.1. TUJUAN PENELITIAN mengetahui mekanisme proses enkripsi dan dekripsi file teks menggunakan metode Byte Pair Encoding. Meneliti dan menguji apakah metode Byte Pair Encoding memiliki tingkat kompresi yang baik. Serta merancang aplikasi perangkat lunak komputer yang dapat digunakan dalam kompresi data menggunakan metode Byte Pair Encoding. 1.2. MANFAAT PENELITIAN Memahami bagaimana cara kerja dan penerapan metode Byte Pair Encoding dalam proses kompresi dan dekompresi data. Memperoleh hasil validasi seberapa baik kompresi data menggunakan Byte Pair Encoding. Menghasilkan aplikasi yang dapat melakukan kompresi data menggunakan metode Byte Pair Encoding. 2. TINJAUAN PUSTAKA Data disimpan di komputer pada memori utama untuk diproses. Sebuah karakter data disimpan dalam memori utama menempati posisi 1 byte. Pada saat ini komputer merepresentasikan 1 byte terdiri dari 8 bit, yang mana tiap karakter direprensentasikan kedalam 8 bit pada memori utama [1]. Sebelum munculnya komputer dengan kemampuan 8 bit, komputer generasi pertama menggunakan lebar byte sebanyak 4 bit, yang kemudian di-ikuti dengan komputer generasi kedua yang menggunakan lebar byte sebanyak 6 bit, barulah pada komputer generasi ketiga menggunakan lebar bit sebanyak 8 bit. Pada komputer generasi pertama yang menggunakan lebar byte sebanyak 4 bit, sistem pengkodean yang digunakan adalah BCD (Binary Coded Decimal). Pada komputer generasi kedua

yang menggunakan lebar byte sebanyak 6 bit menggunakan SBCDIC. Pada sistem pengkodean data yang menggunakan 8 bit, terdapat dua sistem pengkodean yang telah digunakan secara luas hampir di seluruh dunia, yaitu sistem pengkodean data EBCDIC ( Extended Binary Coded Decimal Interchange Code ) dan ASCII ( American Standard Code for Information Interchange ). Kompresi data merupakan wujud dari pengembangan dari representasi yang padat dan efektif dari sajian informasi [2]. Kebanyakan representasi dari informasi yang disajikan mengandung banyaknya bagian – bagian yang berulang atau redundan. Redundansi dapat didefinisikan sebagai bagian dari pesan yang dapat di hilangkan tanpa berkurangnya esensi dari informasi tersebut. Tujuan utama dari kompresi data adalah untuk menghemat ruang penyimpanan dan bandwitdth jaringan yang digunakan untuk transmisi data tersebut [3]. Salah satu aspek dari kompresi data adalah penghilangan redudansi. Pengenalan dari redudansi yang ada melibatkan tahap – tahap yang disebut sebagai modeling. Setelah proses penghilangan redudansi, informasi akan ditransformasi menjadi kode – kode berdasarkan aturan – aturan yang digunakan. Berdasarkan uraian tersebut, maka proses kompresi data terbagi menjadi dua tahap, yaitu modeling dan coding. Model adalah kumpulan dari data dan aturan – aturan yang digunakan untuk memproses symbol sebagai output dan menentukan kode sebagai output [4]. Sebuah program menggunakan model yang diberikan untuk mendefinisikan kemungkinan atau probabilitas untuk setiap symbol dan coder untuk menghasilkan kode yang sesuai berdasarkan probabilitas tersebut. Algoritma Byte Pair Encoding merupakan sebuah algoritma kompresi teks sederhana yang didasarkan oleh substitusi pola [5]. Operasi dasar dari kompresi adalah substitusi sebuah karakter yang mana tidak muncul pada pesan untuk sepasang atau dua karakter yang berpasangan yang sering muncul pada pesan. Operasi akan dilakukan berulang – ulang sampai semua karakter telah digunakan atau tidak ada lagi pasangan karakter yang muncul. 3. METODE PENELITIAN Teks hasil kompresi terdiri dari dua bagian, yaitu table substitusi dan pesan yang telah disubstitusi. Proses dekompresi membutuhkan waktu yang sangat sedikit dan proses yang cepat, lebih lanjut dekompresi dapat dilakukan secara parsial mengingat kompresi hanya bergantung pada proses substitusi. Kelebihan ini menjadi keuntungan tersendiri dibandingkan dengan metode yang menggunakan kamus lainnya. Berikut beberapa criteria dari algoritma byte pair encoding.

a. b. c. d.

Merupakan tipe metode multipass. Hanya mampu mengeliminasi beberapa tipe redudansi. Menggunakan offline dictionary. Merupakan tipe kompresi yang dipengaruhi oleh kosa kata.

Proses kompresi pada algoritma byte pair encoding dapat dijabarkan sebagai berikut. a. Temukan pasangan karakter yang paling sering muncul pada pesan. b. Substitusi pasangan karakter tersebut dengan karakter lain yang tidak muncul pada pesan. c. Daftarkan kode substitusi pada table kamus. d. Ulangi proses a sampai tidak ditemukan lagi pasangan karakter pada pesan.

Aktor yang berinteraksi dengan sistem ini adalah user yang terdiri atas satu jenis yaitu: pengguna. Perancangan use case diagram dari sistem yang dikembangkan dapat dilihat pada gambar 3.4 berikut. System

Input Pesan «uses»

Kompresi

«extends»

Pengguna

Tabel Lookup «uses» Dekompresi

Gambar 1. Use Case Diagram

Pada langkah – langkah proses kompresi diatas, hasil kompresi terdiri dari dua bagian, yaitu table substitusi dan pesan hasil kompresi. Proses dekompresi pada algoritma byte pair encoding dapat dijabarkan sebagai berikut. a.

Baca table substitusi mulai dari indeks terakhir.

b.

Substitusi balik karakter yang terdapat pada pesan berdasarkan data substitusi yang dibaca dari table substitusi.

c.

Baca table substitusi pada indeks berikutnya secara descending. Ulangi proses (b) sampai semua karakter telah disubstitusi balik berdasarkan table substitusi.

d.

Use Case Diagram Perancangan Use Case Diagram dilakukan untuk mengetahui aktivitas pengguna terhadap sistem informasi yang dikembangkan. Untuk mengetahui aktor dan use case yang akan digunakan, maka dilakukan identifikasi aktor dan identifikasi use case. Setelah mendapatkan aktor dan use case, maka use case diagram dapat digambarkan.

Flowchart. Flowchart adalah penggambaran secara grafik dari langkah-langkah dan urut-urutan prosedur dari suatu program.Flowchart menolong analis dan programmer untuk memecahkan masalah kedalam segmen-segmen yang lebih kecil dan menolong dalam menganalisis alternatif-alternatif lain dalam pengoperasian. Berikut perancangan Flowchart (diagram alur) dalam aplikasi Kompresi ini. 1. Flowcart Kompresi.

Gambar 2. Flowcart Kompresi Diagram flowchart kompresi seperti yang terlihat pada gambar 2 diawali dengan menerima input teks dari pengguna. Kemudian karakter – karakter dibaca satu per satu dan dimasukkan ke dalam penampung. Proses dilanjutkan dengan mendata karakter yang tidak terdapat pada teks yang disiapkan sebagai karakter substitusi atau pengganti. Proses kompresi dilanjutkan dengan melakukan proses substitusi atau penggantian antara pasangan karakter yang sering muncul pada teks dengan karakter pengganti yang telah disiapkan. Hasil teks yang telah mengalami substitusi kemudian akan menjadi output dari proses kompresi. 2.

Flowcart Dekompresi.

Rancangan Antarmuka Antar muka kompresi digunakan untuk melakukan proses kompresi pada file yang di-input oleh pengguna. Rancangan antar muka kompresi dapat dilihat pada gambar 4 berikut ini.

Gambar 4. Rancangan Antarmuka Kompresi Antar muka dekompresi digunakan untuk melakukan proses dekompresi pada file yang diinput oleh pengguna. Rancangan antar muka kompresi dapat dilihat pada gambar 5 berikut ini.

Gambar 5. Rancangan Antarmuka Dekompresi 4. HASIL DAN PEMBAHASAN Pada tahap ini akan dibahas mengenai implementasi aplikasi setiap fungsi, dan pembahasan ini berdasarkan implementasi aplikasi kompresi yang dikembangkan.

Gambar 3. Flowcart Dekompresi Diagram flowchart dekompresi seperti yang terlihat pada gambar 3 diawali dengan menerima input teks yang telah dikompresi sebelumnya. Kemudian karakter – karakter dibaca satu per satu dan dimasukkan ke dalam penampung. Proses dilanjutkan dengan melakukan substitusi balik terhadap pasangan karakter yang dikompresi. Hasil teks yang telah mengalami substitusi balik kemudian akan menjadi output dari proses dekompresi. Gambar 6. Implementasi Halaman Kompresi

Form ini digunakan untuk melakukan kompresi terhadap file yang dipilih. Pengguna pertama sekali membuka file yang akan di-kompresi dengan menggunakan tombol open. Proses komprsi kemudian dimulai dengan menggunakan tombol start. Hasil kompresi kemudian dapat disimpan kembali dalam format file menggunakan tombol simpan.

Gambar 9 Form Dekompresi Proses dekripsi kemudian dimulai dengan menggunakan tombol start. Hasil dekripsi kemudian dapat disimpan kembali dalam format file menggunakan tombol simpan. Gambar 7 Hasil Kompresi Pada gambar 7 dapat dilihat berkas hasil dari proses kompresi. Kompresi yang dilakukan oleh aplikasi yang dikembangkan akan disimpan pada berkas dengan ekstensi .bp sehingga dapat membedakan antara berkas hasil kompresi dengan berkas – berkas yang lainnya. Tabel substitusi yang berisikan informasi proses substitusi kemudian disimpan juga dengan ekstensi _key yang mana isi dari tabel substitusi dapat dilihat pada gambar 8 berikut.

Gambar 10 Hasil Dekompresi

Pengujian Aplikasi Pengujian dilakukan untuk memperoleh validasi terhadap fungsionalitas yang dimiliki oleh aplikasi yang dikembangkan. Pengujian pada penelitian ini dilakukan dengan menggunakan input teks yang akan dikompresi dan kemudian dikompresi kembali. Input teks yang digunakan pada pengujian ini adalah input ”uji.txt” yang mana memiliki teks yang dapat dilihat pada gambar 11 berikut :

Gambar 8 Tabel Lookup Kompresi Form dekompresi digunakan untuk melakukan dekompresi terhadap file yang dipilih. Pengguna pertama sekali membuka file yang akan didekompresi dengan menggunakan tombol open.

Gambar 11 Input Pengujian Pengujian yang dilakukan pada penelitian ini dimulai dengan proses kompresi, kemudian dilanjutkan dengan melihat perbedaan ukuran

berkas sebelum kompresi dan setelah kompresi, pengujian terus dilanjutkan dengan proses dekompresi yang akan memeriksa apakah berkas atau teks dapat dikembalikan ke kondisi saat sebelum dikompresi. Pengujian kompresi pada pengujian ini yang dapat dilihat pada gambar 12 berikut.

Berdasarkan perbandingan kompresi seperti yang dapat dilihat pada gambar 4.9 dan 4.10 dapat dilihat bahwa rasio kompresi dari aplikasi kompresi yang diperoleh adalah sebesar 66.38 %. Pengujian blackbox dilanjutkan dengan melakukan dekompresi kembali ke berkas teks asal yang dapat dilihat pada gambar 15 berikut.

Gambar 15 Pengujian Dekompresi Gambar 12 Pengujian Kompresi Hasil pengujian kompresi seperti yang terlihat pada gambar 12 dapat dilihat teks hasil kompresi telah disubstitusikan dengan karakter lain sehingga memiliki ukuran yang lebih kecil. Berkas hasil kompresi dapat dilihat pada gambar 13 berikut.

Pengujian dekompresi seperti yang terlihat pada gambar 15 dapat dilihat proses dekompresi balik terhadap berkas teks yang dikompresi sebelumnya dapat dikembalikan menjadi berkas teks semula dengan sempurna. Pengujian yang telah dilakukan mulai dari proses kompresi, perbandingan rasio kompresi dan proses dekompresi menunjukkan bahwa aplikasi yang dikembangkan memiliki fungsi yang sesuai dan dapat beroperasi sesuai dengan yang diharapkan. Dari hasil yang diperoleh, dapat dilihat bahwa program aplikasi kompresi menggunakan algoritma byte pair encoding yang dibangun dapat memberikan hasil yang cukup baik, dimana file yang di-kompresi dapat di-dekompresi kembali dengan sempurna.

Gambar 13 Berkas Hasil Kompresi Berkas hasil kompresi seperti yang terlihat pada gambar 13 dapat dilihat berkas hasil kompresi memiliki ukuran yang lebih kecil yaitu 135 byte dibandingkan dengan berkas teks semula yaitu 407 byte seperti yang terlihat pada gambar 14 berikut.

5. PENUTUP Kesimpulan Berdasarkan hasil analisa, perancangan dan implementasi aplikasi kompresi yang dikembangkan, maka penulis dapat menyimpulkan : 1.

2. Gambar 14 Berkas Sebelum Kompresi

Telah dibangun aplikasi kompresi untuk meng-kompresi file menggunakan algoritma byte pair encoding. Pada proses pengujian yang dilakukan terhadap sistem, langkah awal dimulai dari memilih file yang akan dikompresi, selanjutnya sistem akan melakukan kompresi pada file yang dipilih. Algoritma byte pair encoding sangat baik diterapkan pada proses kompresi baik pada data pesan maupun data file secara umum

atau data binari, namun terdapat beberapa kelemahan pada algoritma byte pair encoding dimana jika isi file atau pesan memiliki persentase perulangan byte yang sedikit maka performa kompresi akan menurun drastis. Saran Aplikasi Kompresi yang telah penulis rancang ini masih jauh dari sempurna, hal ini dikarenakan keterbatasan waktu dan pengetahuan penulis dalam pengembangannya. Adapun saran yang diberikan setelah melakukan pembahasan ini adalah : 1.

2.

1.

Masih perlu adanya pengembangan dan penyempurnaan dari segigraphic user interfacesehingga tampilan program tampak lebih menarik. Mengenai saran yang digunakan khususnya komputer, perlu diadakan spesifikasi komputer yang sesuai dengan penulis ajukan. Performa komputer yang buruk dapat mempengaruhi waktu yang dibutuhkan dalam proses kompresi dan dekompresi. DAFTAR PUSTAKA

[1].

Hartono, J. (2011). Pengenalan Komputer. Yogyakarta: Penerbit Andi.

[2].

Sayood, K. (2011). Data Compression. Lincoln: University of Nebraska.

[3].

Graefe, G., & Shapiro, L. D. (2010). Data Compression and Database Performance. Kansas City: ACM/IEEE-CS Symp.

[4].

Nelson, M., & Gailly, J.-l. (2009). The Data Compression Book. Bahrain: University Of Bahrain.

[5].

Shibata, Y., & Kida, T. (2009). Byte Pair Encoding : a text compression scheme that accelerates pattern matching. Fukuoka: Kyushu University.