ABSTRACT
Efficient use of bandwidth and memory into the main focus that must be considered in the process of data exchange. More and more data is stored, the greater the size of the data. One alternative that can be implemented is to reduce the size of the (compressed) data. In addition to the process of data transmission, compression is also useful in the data storage medium in the secondary. Compression aims to reduce the amount of data used to represent the contents of a text file, image, audio, and video without reducing the quality of the original data. Compression is done by reducing the number of bits needed to store or transmit the digital media. For data compression, one algorithm has a good performance is the type of the Huffman algorithm. In this study, the Static Huffman algorithm which is one technique that is lossless data compression. Static Huffman algorithm uses frequency/probability of occurrences of a symbol in a string as input and produce output in the form of a prefix code that encodes a string using the little bits of all possible binary prefix code that may be. Static Huffman algorithm implementation is aimed to compress the data so that the compressed data size is smaller than the size of the original data. So that the compressed data can be retrieved, then the decompression process. This application was made and in the making based on Android using Eclipse and the methodology GRAPPLE (Guidlines for Rappid Application Engineering). GRAPPLE is a process modeling in software development which emphasizes the actions carried out in a number of stages , each stage will result in products that work with object-oriented form. With applications of data compression with Huffman Static method in Android based mobile devices, the data size becomes smaller so that it can speed up the process of delivery and storage. Compression using Huffman code would be optimal if the range of the character of the information is not too much despite the high frequency of occurrence and the size of the compression results obtained that the compression of each file depending on the characteristics of the file to be compressed. Keywords: compression, decompression, Static Huffman algorithm, lossless, Android.
v
ABSTRAK
Efisiensi penggunaan bandwidth dan memory menjadi satu fokus utama yang harus diperhatikan dalam proses pertukaran data. Semakin banyak data yang tersimpan maka semakin besar pula ukuran dari data tersebut. Salah satu alternatif yang dapat di implementasikan adalah memperkecil ukuran (kompresi) data tersebut. Selain pada proses pengiriman data, kompresi juga bermanfaat pada penyimpanan data di dalam media sekunder. Kompresi bertujuan untuk mengurangi jumlah data yang digunakan untuk mewakili isi file teks, gambar, audio, dan video tanpa mengurangi kualitas data aslinya. Kompresi dilakukan dengan mengurangi jumlah bit yang diperlukan untuk menyimpan atau mengirimkan media digital tersebut. Untuk kompresi data, salah satu algoritma yang memiliki performa yang baik adalah jenis algoritma Huffman. Pada penelitian ini digunakan algoritma Huffman Statik yang merupakan salah satu teknik kompresi data yang bersifat lossless. Algoritma Huffman Statik menggunakan frekuensi/probabilitas kemunculan dari simbol pada sebuah string sebagai input dan menghasilkan output berupa prefix code yang mengkodekan string menggunakan bit paling sedikit dari seluruh kemungkinan binary prefix code yang mungkin. Implementasi algoritma Huffman Statik ini bertujuan untuk mengkompresi data sehingga ukuran data hasil kompresi lebih kecil dibandingkan dengan ukuran data asli. Agar data yang terkompres dapat dilihat kembali, maka dilakukan proses dekompresi. Aplikasi ini dibuat berbasis Android dan dalam pembuatannya menggunakan Eclipse dan metodologi GRAPPLE (Guidlines for Rappid APPLication Engineering). GRAPPLE merupakan sebuah pemodelan proses dalam pengembangan software yang menekankan pada aksi-aksi yang dilakukan pada sejumlah tahapan, setiap tahap akan menghasilkan produk kerja dengan bentuk yang berorientasi objek. Dengan dibuatnya aplikasi kompresi data dengan metode Huffman Statik pada perangkat mobile berbasis android, ukuran data menjadi lebih kecil sehingga dapat mempercepat dalam proses pengiriman maupun penyimpanan. Kompresi dengan menggunakan kode Huffman akan lebih optimal jika ragam karakter dari informasi tersebut tidak terlalu banyak walaupun frekuensi kemunculannya tinggi dan ukuran hasil kompresi diperoleh bahwa pemampatan setiap file tergantung dari karakteristik file yang akan dimampatkan. Kata kunci : kompresi, dekompresi, algoritma Huffman Statik, lossless, Android.
v
DAFTAR ISI HALAMAN JUDUL ................................................................................................. HALAMAN PENGESAHAN PEMBIMBING ........................................................ HALAMAN PENGESAHAN PENGUJI .................................................................. SURAT PERNYATAAN KARYA ASLI SKRIPSI ................................................. ABSTRAK ................................................................................................................ KATA PENGANTAR ............................................................................................... DAFTAR ISI ............................................................................................................. DAFTAR GAMBAR ................................................................................................. DAFTAR TABEL ..................................................................................................... DAFTAR MODUL PROGRAM ...............................................................................
i ii iii iv v vi viii xi xii xiii
BAB I PENDAHULUAN ........................................................................................ 1.1 Latar Belakang Masalah .............................................................................. 1.2 Perumusan Masalah ..................................................................................... 1.3 Batasan Masalah .......................................................................................... 1.4 Tujuan Penelitian ......................................................................................... 1.5 Manfaat Penelitian ....................................................................................... 1.6 Metode Pengembangan ............................................................................... 1.7 Sistematika Penulisan ..................................................................................
1 1 2 2 3 3 3 4
BAB II LANDASAN TEORI .................................................................................. 2.1 Aplikasi Mobile ........................................................................................... 2.2 Data ............................................................................................................. 2.3 Pengertian File Teks .................................................................................... 2.4 Satuan Dalam Sistem Komputer ................................................................. 2.5 ASCII (American Standard Code for Information Interchange) ................ 2.6 Pohon (Tree) ................................................................................................ 2.6.1 Pohon Biner (Binary Tree)........................................................................ 2.7 Kompresi Data ............................................................................................. 2.7.1 Manfaat Kompresi ...................................................................................... 2.7.2 Teknik Kompresi Data Menurut Jenis Data yang akan dikompresi ............ 2.7.3 Empat Pendekatan yang digunakan pada Kompresi Suatu Data ................. 2.7.4 Metode Kompresi Berdasarkan Tipe Peta Kode ......................................... 2.7.5 Metode Kompresi Berdasarkan Teknik Pengkodean .................................. 2.7.6 Klasifikasi dari Beberapa Teknik Kompresi Data ....................................... 2.7.6.1 Lossless Compression.................................................................................. 2.7.6.2 Lossy Compression ...................................................................................... 2.7.6.3 Teori Informasi dan Entropi........................................................................ 2.7.7 Dekompresi ................................................................................................. 2.7.8 Pengujian Hasil Kompresi............................................................................ 2.7.9 Perbedaan antara Compression Rate dan Compression Ratio..................... 2.7.10 Arithmatic Encoding.................................................................................... 2.7.11 Run-Length Encoding .................................................................................. 2.7.12 Algoritma Huffman...................................................................................... 2.7.12.1 Algoritma Huffman Statik ........................................................................... 2.7.12.2 Algoritma Huffman Adaptif......................................................................... 2.7.13 Perbandingan Antara Metode-Metode Kompresi Data...............................
6 6 7 8 9 10 14 15 16 19 19 20 20 21 21 22 23 24 25 26 26 27 27 28 32 33 35
viii
2.8 2.9 2.10 2.10.1 2.11 2.12 2.12.1 2.12.2 2.12.3 2.13
Android ........................................................................................................ Guidelines for Rappid APPLication Engineering (GRAPPLE).................. Unified Modelling Language (UML) .......................................................... Diagram UML ............................................................................................. Flowchart.................................................................................................... Software yang Digunakan ........................................................................... SDK Android ............................................................................................... JDK.............................................................................................................. SDK Eclipse ................................................................................................ Studi Pustaka ...............................................................................................
35 40 41 42 49 50 50 50 51 51
BAB III ANALISIS DAN PERANCANGAN ....................................................... 3.1 Pengumpulan Kebutuhan (Requirement Gathering) ................................... 3.1.1 Analisis Kebutuhan Pengguna..................................................................... 3.1.2 Analisis Domain .......................................................................................... 3.1.3 Analisis Fitur ............................................................................................... 3.1.4 Identifikasi Sistem ....................................................................................... 3.2 Analisa (Analysis)........................................................................................ 3.2.1 Diagram Use Case ....................................................................................... 3.2.2 Diagram Class ............................................................................................. 3.2.3 Diagram Sequence ....................................................................................... 3.2.3.1 Diagram Sequence Kompresi ...................................................................... 3.2.3.2 Diagram Sequence Dekompresi .................................................................. 3.2.3.3 Diagram Sequence Bagikan......................................................................... 3.2.3.4 Diagram Sequence Bantuan......................................................................... 3.2.3.5 Diagram Sequence Tentang Aplikasi .......................................................... 3.2.3.6 Diagram Sequence Keluar ........................................................................... 3.3 Perancangan................................................................................................. 3.3.1 Diagram Activity .......................................................................................... 3.3.1.1 Diagram Activity KompresiActivity ............................................................. 3.3.1.2 Diagram Activity DekompresiActivity ......................................................... 3.3.1.3 Diagram Activity BagikanActivity ............................................................... 3.3.1.4 Diagram Activity BantuanActivity............................................................... 3.3.1.5 Diagram Activity TtgAplikasiActivity .......................................................... 3.3.1.6 Diagram Activity prosesKeluarActivity ....................................................... 3.3.2 Flowchart ..................................................................................................... 3.3.2.1 Flowchart Kompresi .................................................................................... 3.3.2.2 Flowchart Dekompresi ................................................................................ 3.3.3 Rancangan Struktur Menu ........................................................................... 3.3.4 Rancangan Antarmuka Aplikasi .................................................................. 3.3.4.1 Rancangan Antarmuka activity_main ......................................................... 3.3.4.2 Rancangan antarmuka kompresi_layout ...................................................... 3.3.4.3 Rancangan antarmuka dekompresi_layout .................................................. 3.3.4.4 Rancangan antarmuka bantuan_layout ....................................................... 3.3.4.5 Rancangan antarmuka tentang_layout ........................................................
54 54 54 55 55 56 57 57 58 60 62 63 64 64 65 65 66 66 66 68 70 70 71 72 72 73 74 76 77 77 77 78 79 80
BAB IV IMPLEMENTASI ..................................................................................... 82 4.1 Perangkat Lunak yang Digunakan Untuk Membangun Aplikasi ................ 82 4.2 Perangkat Keras yang Digunakan Untuk Membangun Aplikasi................. 82 ix
4.3 4.3.1 4.3.2 4.3.3 4.3.4 4.3.5 4.3.6 4.3.7 4.3.8 4.3.9 4.3.10 4.3.11 4.3.12 4.3.13 4.3.14 4.4 4.4.1 4.4.1.1 4.4.1.2 4.4.1.3 4.4.1.4 4.4.2 4.4.2.1
Implementasi Aplikasi ................................................................................. Implementasi Halaman Menu Utama .......................................................... Implementasi Halaman Kompresi ............................................................... Implementasi Halaman Dekompresi ........................................................... Implementasi Bagikan ................................................................................. Implementasi Halaman Bantuan ................................................................. Implementasi Halaman Tentang Aplikasi ................................................... Implementasi Keluar ................................................................................... Implementasi Source CHuffmanEncoder.java ............................................ Implementasi Source CHuffmanDecoder.java ............................................ Implementasi Source CPriorityQueue.java ................................................. Implementasi Source HuffmanNode.java ................................................... Implementasi Source huffmanSignature.java.............................................. Implementasi Source CFileBitReader.java. ................................................ Implementasi Source CFileBitWriter.java .................................................. Pengujian Sistem.......................................................................................... Pengujian Kompresi .................................................................................... Pengujian Kompresi Pada Gambar.............................................................. Pengujian Kompresi Pada Teks ................................................................... Pengujian Kompresi Pada Audio ................................................................ Pengujian Kompresi Pada Video ................................................................. Pengujian Dekompresi ................................................................................ Pengujian Dekompresi Pada Beberapa File ................................................
83 83 90 98 106 108 111 114 115 119 121 122 122 122 124 126 126 128 134 138 139 140 140
BAB V PENUTUP ................................................................................................... 142 5.1 Kesimpulan.................................................................................................. 142 5.2 Saran ............................................................................................................ 143 DAFTAR PUSTAKA .............................................................................................. 144
x
DAFTAR GAMBAR Gambar 2.1 Gambar 2.2 Gambar 2.3 Gambar 2.4 Gambar 2.5 Gambar 2.6 Gambar 2.7 Gambar 2.8 Gambar 2.9 Gambar 2.10 Gambar 2.11 Gambar 2.12 Gambar 2.13 Gambar 2.14 Gambar 2.15 Gambar 2.16 Gambar 2.17 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 4.1 Gambar 4.2 Gambar 4.3 Gambar 4.4 Gambar 4.5 Gambar 4.6 Gambar 4.7
Karakter ASCII .................................................................................. Pohon Berakar dengan v1 Sebagai Akar ............................................ Pohon Biner ....................................................................................... Alur kompresi dan dekompresi data .................................................. Klasifikasi dari beberapa teknik kompresi data ................................. Lossless compression ......................................................................... Lossy compression ............................................................................. Tiga buah karakter. ............................................................................ Pohon Biner untuk Kode Awalan ...................................................... Pohon Kode Huffman ......................................................................... Pohon dengan 2 simbol ...................................................................... Pohon dengan 3 simbol ...................................................................... Arsitektur sistem operasi Android ..................................................... Contoh diagram use case ................................................................... Contoh diagram class hubungan antar class ...................................... Contoh diagram sequence .................................................................. Contoh diagram activity ..................................................................... Arsitektur sistem ................................................................................ Diagram use case ............................................................................... Diagram class..................................................................................... Diagram Sequence Kompresi ............................................................. Diagram Sequence Dekompresi ......................................................... Diagram Sequence Bagikan ............................................................... Diagram Sequence Bantuan ............................................................... Diagram Sequence Tentang Aplikasi ................................................. Diagram Sequence Keluar.................................................................. Diagram Activity KompresiActivity.................................................... Diagram Activity DekompresiActivity ................................................ Diagram Activity BagikanActivity ...................................................... Diagram Activity BantuanActivity...................................................... Diagram Activity TtgAplikasiActivity ................................................. Diagram Activity prosesKeluarActivity.............................................. Flowchart Kompresi........................................................................... Flowchart Dekompresi ....................................................................... Struktur menu..................................................................................... Rancangan antarmuka activity_main ................................................. Rancangan antarmuka kompresi_layout ............................................ Rancangan antarmuka dekompresi_layout ........................................ Rancangan antarmuka bantuan_layout .............................................. Rancangan antarmuka tentang_layout ............................................... Halaman menu utama ........................................................................ Halaman Kompresi ............................................................................ Halaman Dekompresi......................................................................... Halaman Bagikan ............................................................................... Halaman Bantuan ............................................................................... Halaman Tentang Aplikasi ................................................................ Halaman Keluar ................................................................................. xi
9 15 16 18 22 23 24 25 30 31 33 33 36 43 45 47 49 57 58 59 61 63 64 64 65 65 67 69 70 71 71 72 73 75 76 77 78 79 80 81 83 90 98 107 108 112 114
DAFTAR TABEL 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 2.15 Tabel 2.16 Tabel 2.17 Tabel 2.18 Tabel 2.19 Tabel 4.1 Tabel 4.2 Tabel 4.3 Tabel 4.4 Tabel 4.5 Tabel 4.6 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
Daftar Satuan yang Menyatakan Jumlah Byte...................................... 9 ASCII ...................................................................................................... 10 Lanjutan ASCII....................................................................................... 11 Lanjutan ASCII....................................................................................... 12 Lanjutan ASCII....................................................................................... 13 Lanjutan ASCII....................................................................................... 14 Contoh Kode ASCII............................................................................... 30 Tabel Kode Huffman.............................................................................. 31 Perbandingan antara metode-metode kompresi data .............................. 35 Notasi Diagram Use Case....................................................................... 43 Notasi Diagram Class ............................................................................. 44 Lanjutan Notasi Diagram Class .............................................................. 45 Notasi Diagram Sequence ....................................................................... 46 Lanjutan Notasi Diagram Sequence........................................................ 47 Notasi Diagram Activity .......................................................................... 48 Simbol-simbol Flowchart Program ........................................................ 49 Lanjutan Simbol-simbol Flowchart Program ......................................... 50 Perbandingan Aplikasi yang dibangun dengan Penelitian Sebelumnya . 52 Lanjutan Perbandingan Aplikasi yang dibangun dengan Penelitian Sebelumnya............................................................................................ 53 Tabel Kebutuhan Perangkat Lunak (Software)....................................... 82 Tabel Kebutuhan Perangkat Keras (Hardware) ..................................... 83 Tabel Pengujian Gambar Berwarna berformat *.bmp ............................ 128 Tabel Pengujian Gambar Hitam Putih berformat *.bmp ........................ 129 Tabel Pengujian Gambar berformat *.gif ............................................... 130 Tabel Pengujian Gambar berformat *.png.............................................. 131 Tabel Pengujian Gambar kecil ke besar berformat *.png....................... 132 Tabel Pengujian Gambar berformat *.jpg .............................................. 133 Tabel Pengujian Teks beragam karakter dengan beragam format file ... 134 Tabel Pengujian Teks dua ragam karakter dengan beragam format file 134 Tabel Pengujian Teks satu ragam karakter (jumlah sedikit) dengan beragam format file................................................................................................ 135 Tabel Pengujian Teks satu ragam karakter (jumlah banyak) dengan beragam format file................................................................................................ 136 Tabel Pengujian Teks empat ragam karakter berformat file *.txt .......... 136 Tabel Pengujian Audio dengan beragam format file .............................. 138 Tabel Pengujian Video dengan beragam format file .............................. 139 Tabel Pengujian Dekompresi pada beberapa file.................................... 141
xii
DAFTAR MODUL PROGRAM Modul Program 2.1 Modul Program 2.2 Modul Program 4.1 Modul Program 4.2 Modul Program 4.3 Modul Program 4.4 Modul Program 4.5 Modul Program 4.6 Modul Program 4.7 Modul Program 4.8 Modul Program 4.9 Modul Program 4.10 Modul Program 4.11 Modul Program 4.12 Modul Program 4.13 Modul Program 4.14 Modul Program 4.15 Modul Program 4.16 Modul Program 4.17 Modul Program 4.18 Modul Program 4.19 Modul Program 4.20 Modul Program 4.21 Modul Program 4.22 Modul Program 4.23 Modul Program 4.24 Modul Program 4.25 Modul Program 4.26 Modul Program 4.27 Modul Program 4.28 Modul Program 4.29 Modul Program 4.30 Modul Program 4.31 Modul Program 4.32 Modul Program 4.33 Modul Program 4.34 Modul Program 4.35 Modul Program 4.36 Modul Program 4.37 Modul Program 4.38 Modul Program 4.39 Modul Program 4.40 Modul Program 4.41 Modul Program 4.42 Modul Program 4.43 Modul Program 4.44
Source Code encoder algoritma Huffman Adaptif............... 34 Source Code dekoder algoritma Huffman Adaptif .............. 34 Source Code MainActivity.java........................................... 83 Lanjutan Source Code MainActivity.java ........................... 84 Lanjutan Source Code MainActivity.java ........................... 85 Lanjutan Source Code MainActivity.java .......................... 86 Lanjutan Source Code MainActivity.java ........................... 87 Source Code activity_main.xml........................................... 87 Lanjutan Source Code activity_main.xml ........................... 88 Lanjutan Source Code activity_main.xml ........................... 89 Source Code KompresiActivity.java ................................... 90 Lanjutan Source Code KompresiActivity.java .................... 91 Lanjutan Source Code KompresiActivity.java .................... 92 Lanjutan Source Code KompresiActivity.java .................... 93 Lanjutan Source Code KompresiActivity.java .................... 94 Lanjutan Source Code KompresiActivity.java .................... 95 Source Code kompresi_layout.xml ...................................... 95 Lanjutan Source Code kompresi_layout.xml ...................... 96 Lanjutan Source Code kompresi_layout.xml ...................... 97 Lanjutan Source Code kompresi_layout.xml ...................... 98 Source Code DekompresiActivity.java ............................... 99 Lanjutan Source Code DekompresiActivity.java ................ 100 Lanjutan Source Code DekompresiActivity.java ................ 101 Lanjutan Source Code DekompresiActivity.java ................ 102 Lanjutan Source Code DekompresiActivity.java ................ 103 Lanjutan Source Code DekompresiActivity.java ................ 104 Source Code dekompresi_layout.xml .................................. 104 Lanjutan Source Code dekompresi_layout.xml ................... 105 Lanjutan Source Code dekompresi_layout.xml ................... 106 Potongan Source Code Bagikan di MainActivity.java ........ 107 Lanjutan Potongan Source Code Bagikan di MainActivity.java .............................................................................................. 108 Source Code BantuanActivity.java ...................................... 109 Source Code bantuan_layout.xml ........................................ 109 Lanjutan Source Code bantuan_layout.xml ......................... 110 Lanjutan Source Code bantuan_layout.xml ......................... 111 Source Code TtgAplikasiActivity.java ................................ 112 Source Code tentang_layout.xml ......................................... 112 Lanjutan Source Code tentang_layout.xml.......................... 113 Lanjutan Source Code tentang_layout.xml.......................... 114 Potongan Source Code Keluar di MainActivity.java .......... 115 Source Code CHuffmanEncoder.java .................................. 115 Lanjutan Source Code CHuffmanEncoder.java .................. 116 Lanjutan Source Code CHuffmanEncoder.java .................. 117 Lanjutan Source Code CHuffmanEncoder.java .................. 118 Source Code CHuffmanDecoder.java ................................. 119 Lanjutan Source Code CHuffmanDecoder.java .................. 120 xiii
Modul Program 4.45 Modul Program 4.46 Modul Program 4.47 Modul Program 4.48 Modul Program 4.49 Modul Program 4.50 Modul Program 4.51 Modul Program 4.52 Modul Program 4.53
Source Code CPriorityQueue.java ....................................... Source Code HuffmanNode.java ......................................... Source Code huffmanSignature.java ................................... Source Code CFileBitReader.java ....................................... Lanjutan Source Code CFileBitReader.java ........................ Lanjutan Source Code CFileBitReader.java ........................ Source Code CFileBitWriter.java ........................................ Lanjutan Source Code CFileBitWriter.java ......................... Lanjutan Source Code CFileBitWriter.java .........................
xiv
121 122 122 122 123 124 124 125 126
