PERANCANGAN SISTEM PENGAMANAN DAN KOMPRESI DATA TEKS DENGAN FIBONACCI ENCODING DAN ALGORITMA SHANNON-FANO SERTA ALGORITMA DEFLATE
SKRIPSI
MUHAMMAD SOLIHIN 111421078
PROGRAM STUDI EKSTENSI S1 ILMU KOMPUTER FAKULTAS ILMU KOMPUTER DAN TEKNOLOGI INFORMASI UNIVERSITAS SUMATERA UTARA MEDAN 2013
Universitas Sumatera Utara
PERANCANGAN SISTEM PENGAMANAN DAN KOMPRESI DATA TEKS DENGAN FIBONACCI ENCODING DAN ALGORITMA SHANNON-FANO SERTA ALGORITMA DEFLATE
SKRIPSI
Diajukan untuk melengkapi tugas dan memenuhi syarat memperoleh ijazah Sarjana Ilmu Komputer
MUHAMMAD SOLIHIN 111421078
PROGRAM STUDI EKSTENSI S1 ILMU KOMPUTER FAKULTAS ILMU KOMPUTER DAN TEKNOLOGI INFORMASI UNIVERSITAS SUMATERA UTARA MEDAN 2013
Universitas Sumatera Utara
PERSETUJUAN
Judul
: PERANCANGAN SISTEM PENGAMANAN DAN KOMPRESI DATA TEKS DENGAN FIBONACCI ENCODING DAN ALGORITMA SHANNON-FANO SERTA ALGORITMA DEFLATE
Kategori
: SKRIPSI
Nama
: MUHAMMAD SOLIHIN
Nomor Induk Mahasiswa : 111421078 Program Studi
: EKSTENSI S1 ILMU KOMPUTER
Fakultas
: ILMU KOMPUTER DAN TEKNOLOGI INFORMASI UNIVERSITAS SUMATERA UTARA
Komisi Pembimbing
:
Pembimbing 2
Pembimbing 1
Dian Rachmawati, S.Si, M.Kom
Ade Candra, ST, M.Kom
NIP. 19830723 200912 2 004
NIP. 19790904 200912 1 002
Diketahui/disetujui oleh Program Studi Ekstensi S1 Ilmu Komputer Ketua,
Dr. Poltak Sihombing, M.Kom NIP. 19620217 199103 1 001
Universitas Sumatera Utara
PERANCANGAN SISTEM PENGAMANAN DAN KOMPRESI DATA TEKS DENGAN FIBONACCI ENCODING DAN ALGORITMA SHANNON-FANO SERTA ALGORITMA DEFLATE
SKRIPSI
Saya mengakui bahwa skripsi ini adalah hasil karya saya sendiri, kecuali beberapa kutipan dan ringkasan yang masing-masing telah disebutkan sumbernya.
Medan,
Oktober 2013
Muhammad Solihin 111421078
Universitas Sumatera Utara
PENGHARGAAN
Alhamdulillahirrabbila’lamin. Segala dan puji syukur penulis panjatkan hanya kepada Allah SWT, Pemelihara dan pengatur seluruh alam semesta, karena atas limpahan rahmat, taufik dan hidayah-Nya, penulis mampu menyelesaikan Skripsi ini, serta shalawat dan beriring salam penulis ucapakan kepada Nabi Besar Muhammad SAW.
Skripsi ini dikerjakan sebagai salah satu syarat guna memperoleh gelar Sarjana Ilmu Komputer Fakultas Ilmu Komputer dan Teknologi Informasi Universitas Sumatera Utara. Penulis menyadari bahwa terselesaikannya skripsi ini tentunya tak lepas dari dorongan dan bantuan berbagai pihak. Oleh karena itu, dengan segala kerendahan hati penulis mengungkapkan rasa terima kasih dan penghargaan kepada : 1. Bapak Ade Candra, ST, M.Kom, selaku Dosen Pembimbing I yang telah memberikan banyak sekali arahan, masukan, bimbingan, saran, serta motivasi yang membangun untuk penulis sehingga penulis dapat menyelesaikan skripsi ini dengan baik. 2. Ibu Dian Rachmawati, S.Si, M,Kom, selaku pembimbing II yang telah memberikan masukan, bimbingan, saran dan motivasi kepada penulis, serta sabar memberikan bantuan sehingga penulis dapat menyelesaikan skripsi ini dengan baik. 3. Bapak Dr. Poltak Sihombing, M, Kom selaku Ketua Program Studi Ilmu Komputer sekaligus sebagai Dosen Pembanding I, yang telah memberikan kritik dan saran yang membangun bagi penulis 4. Bapak Drs. Marihat Situmorang, M.Kom sebagai Dosen Pembanding II yang telah memberikan kritik dan saran yang membangun bagi penulis. 5. Dekan dan Pembantu Dekan Fakultas Ilmu Komputer dan Teknologi Informasi Universitas Sumatera Utara berserta para pegawai yang bertugas di Program Studi Ilmu Komputer FASILKOM-TI USU. 6. Orang tua tercinta, Ayahanda Sabirin, S.Pd dan Ibunda Rosyidah, atas semua doa, dukungan, dan motivasi yang tak ternilai harganya.
Universitas Sumatera Utara
7. Keluarga besar Ekstensi Ilmu Komputer, khususnya semua teman dan sahabat angkatan 2011 yang tidak dapat disebutkan satu persatu, terima kasih atas ide, saran, dan kerja samanya selama ini. Semoga Allah SWT membalas semua kebaikan yang telah kalian berikan.
Penulis,
(Muhammad Solihin)
Universitas Sumatera Utara
ABSTRAK
Penelitian ini bertujuan untuk merancang sebuah aplikasi komputer yang dapat mengamankan sekaligus mengkompresi ukuran teks. Pengamanan teks dilakukan dengan mengkodekan teks menggunakan Fibonacci Encoding, kemudian hasil pengkodean Fibonacci Encoding dikompresi menggunakan algoritma Shannon-Fano, lalu hasil kompresi menggunakan algoritma Shannon-Fano dikompresi menggunakan algoritma Deflate, hasil kompresi menggunakan algoritma Deflate adalah hasil akhir proses pengamanan dan kompresi data. Keluaran dari aplikasi ini adalah sebuah file baru yang terdiri dari file header serta file body yang berisi kode-kode hasil pengkodean dan kompresi file teks asli. Rasio kompresi rata-rata antara file input dengan file output untuk file dokumen input dengan ekstensi *.doc adalah 43,653%, sedangkan untuk file teks input dengan ekstensi *.txt adalah 78,444%. Waktu rata-rata yang dibutuhkan untuk melakukan kompresi pada file dokumen input dengan ekstensi *.doc adalah 5328,2 milisecond, sedangkan untuk file teks input dengan ekstensi *.txt adalah 15837,5 milisecond.
Kata kunci: kompresi teks, Fibonacci Encoding, algoritma Shannon-Fano, algoritma Deflate
Universitas Sumatera Utara
DESIGNING TEXT DATA SECURITY AND COMPRESSION SYSTEM WITH FIBONACCI ENCODING, SHANNON-FANO ALGORITHM, AND DEFLATE ALGORITHM
ABSTRACT
This research aimed to constructing a computer application that securing and also compressing the size of text. Text securing was done by text encoding using Fibonacci Encoding, then the result of Fibonacci Encoding was compressed using Shannon-Fano algorithm, then the result of compression using Shannon-Fano algorithm was compressed using Deflate algorithm, the Deflate compression result is the final result of text securing and compression. The output of this application is a new file that consists of file header and file body that contains the encoding and compression codes of original text file. The average of compreesion ratio between the input file and the output file for document file with *.doc extension is 43,653%, otherwise the average of compression ratio fot text file with *.txt extension is 78,444%. The average of compression time for document input file with *.doc extension is 5328,2 miliseconds, otherwise for text input file with *,txt extension is 15837,5 miliseconds.
Keywords: text compression, Fibonacci Encoding, Shannon-Fano algorithm, Deflate algorithm
Universitas Sumatera Utara
DAFTAR ISI
Hal.
PERSETUJUAN
ii
PERNYATAAAN
iii
PENGHARGAAN
iv
ABSTRAK
vi
ABSTRACT
vii
DAFTAR ISI
viii
DAFTAR TABEL
xi
DAFTAR GAMBAR
xiii
BAB 1 PENDAHULUAN 1.1 Latar Belakang
1
1.2 Rumusan Masalah
2
1.3 Batasan Masalah
2
1.4 Tujuan Penelitian
3
1.5 Manfaat Penelitian
3
1.6 Metodologi Penelitian
4
1.7 Sistematika Penulisan
5
BAB 2 TINJAUAN PUSTAKA
6
2.1 Kompresi Data
6
2.2 File Teks
8
2.3 Fibonacci Encoding
10
2.4 Algoritma Shannon-Fano
12
2.5 Algoritma Deflate
13
Universitas Sumatera Utara
BAB 3 ANALISIS DAN PERANCANGAN SISTEM
15
3.1 Analisis Masalah
15
3.2 Analisis Kebutuhan Sistem
16
3.3 Pemodelan Aplikasi
17
3.3.1 Use-Case Diagram
18
3.3.2 Activity Diagram
18
3.3.3 Class Diagram
23
3.3.4 Sequence Diagram
24
3.4 Perancangan Sistem
25
3.4.1 Pembuatan Algoritma Program
25
3.4.2 Alur Proses Sistem Secara Umum
25
3.4.3 Alur Proses Encoding Dan Decoding Dengan Fibonacci Encoding
28
3.4.4 Alur Proses Kompresi Dan Dekompresi Dengan Algoritma Shannon-Fano
34
3.4.5 Penerapan Algoritma Deflate
43
3.5 Pembuatan Rancangan Tampilan Aplikasi
50
3.5.1 Rancangan Form Splash Screen
50
3.5.2 Rancangan Form Tab Menu Kompresi
51
3.5.3 Rancangan Form Tab Menu Dekompresi
52
3.5.4 Rancangan Form Tab Menu Tentang Aplikasi
53
3.5.5 Rancangan Form Dialog Ringkasan
53
BAB 4 IMPLEMENTASI DAN PENGUJIAN 4.1 Implementasi Sistem
56
4.1.1 Implementasi Encoding Dan Decoding File Teks Maupun Dokumen Menggunakan Fibonacci Encoding Pada Aplikasi
62
4.1.2 Implementasi Kompresi Dan Dekompresi Menggunakan Algoritma Shannon-Fano
69
4.1.3 Implementasi Kompresi Dan Dekompresi Menggunakan Algoritma Deflate
76
Universitas Sumatera Utara
4.2 Pengujian Aplikasi
79
4.2.1 Pengujian Kompresi Dalam Aplikasi
80
4.2.2 Proses Dekompresi Dalam Aplikasi
83
4.3 Hasil Pengujian
86
BAB 5 KESIMPULAN DAN SARAN
100
5.1 Kesimpulan
100
5.2 Saran
101
Lampiran A: Questioner
102
Lampiran B: Listing Program
112
Universitas Sumatera Utara
DAFTAR TABEL
Hal.
2.1 Proses Pembentukan Kode Fibonacci
11
3.1 Hasil Fibonacci Encoding
28
3.2 Kode Program Untuk Encoding
30
3.3 Kode Program Untuk Decoding
33
3.4 Frekuensi Kemunculan Karakter
34
3.5 Kode Shannon-Fano
36
3.6 Kode Program Untuk Membuat Tabel Kemunculan Karakter
38
3.7 Kode Program Untuk Membuat Tabel Frekuensi
39
3.8 Kode Program Untuk Membuat Kode Shannon-Fano
41
3.9 Kompresi Teks Menggunakan Algoritma LZ77
43
3.10 Dekompresi Teks Menggunakan Algoritma LZ77
44
3.11 Kode Huffman
45
3.12 Kode Program Untuk Kompresi Dengan Algoritma Deflate
48
3.13 Kode Program Untuk Dekompresi Dengan Algoritma Deflate
49
4.1 Kode Fibonacci Dari Masing-Masing Karakter Dalam String Input
56
4.2 Kemunculan Masing-Masing Bilangan Byte Dalam Array Byte Fibonacci
58
4.3 Kode Shannon-Fano Untuk Byte Dalam Array Byte Fibonacci
59
4.4 Kode Program Untuk Membuat File Fibonacci Dari File Teks Maupun Dokumen Input Dan Sebaliknya
65
4.5 Kode Program Untuk Membuat File Shannon-Fano Dari File Fibonacci Dan Sebaliknya
72
4.6 Kode Program Untuk Membuat File Output Dari File Shannon-Fano Dan Sebaliknya
77
4.7 Hasil Pengujian Untuk Kompresi File Dokumen Dengan
Universitas Sumatera Utara
Ekstensi Doc
86
4.8 Hasil Pengujian Untuk Dekompresi File Dokumen Dengan Ekstensi Doc
87
4.9 Hasil Pengujian Untuk Kompresi File Teks Dengan Ekstensi Txt
93
4.10 Hasil Pengujian Untuk Dekompresi File Teks Dengan Ekstensi Txt
94
Universitas Sumatera Utara
DAFTAR GAMBAR
Hal.
2.1 Diagram Blok Proses Kompresi Dan Dekompresi Data
7
2.2 File Teks Sederhana
9
3.1 Diagram Ishikawa
15
3.2 Use-Case Diagram Pada Sistem
18
3.3 Activity Diagram Pada Sistem
19
3.4 Activity Diagram Fibonacci Processor
20
3.5 Activity Diagram Shannon-Fano Processor
21
3.6 Activity Diagram Deflate Processor
22
3.7 Class Diagram Pada Sistem
23
3.8 Sequence Diagram Pada Sistem
24
3.9 Flowchart Encoding Dan Kompresi File Teks Maupun Dokumen
26
3.10 Flowchart Decoding Dan Dekompresi File Teks Maupun Dokumen
27
3.11 Diagram Blok Proses Fibonacci Encoding
29
3.12 Flowchart Proses Encoding Dengan Fibonacci Encoding
30
3.13 Flowchart Proses Decoding Dengan Fibonacci Encoding
32
3.14 Proses Partisi Dan Pembentukan Kode Shannon-Fano Secara Manual
35
3.15 Pohon Shannon-Fano Yang Terbentuk
35
3.16 Diagram Blok Proses Kompresi Dan Dekompresi Algoritma Shannon-Fano
37
3.17 Flowchart Proses Kompresi Dengan Algoritma Shannon-Fano
38
3.18 Struktur File Hasil Kompresi Dengan Algoritma Shannon-Fano
43
3.19 Pohon Huffman
44
3.20 Flowchart Kompresi Deflate
45
3.21 Flowchart Dekompresi Deflate
46
Universitas Sumatera Utara
3.22 Diagram Blok Proses Kompresi Dan Dekompresi Algoritma Deflate
47
3.23 Struktur File Output Aplikasi
50
3.24 Rancangan Form Splash Screen
50
3.25 Rancangan Form Tab Menu Kompresi
51
3.26 Rancangan Form Tab Menu Dekompresi
52
3.27 Rancangan Form Tab Menu Tentang Aplikasi
53
3.28 Rancangan Form Dialog Ringkasan
54
4.1 Hasil Kompresi Ditampilkan Dengan Penyunting Teks
61
4.2 File Teks Input Dengan Ekstensi Txt
66
4.3 File Dokumen Input Dengan Ekstensi Doc
66
4.4 File Fibonacci Pada File Teks Input Dengan Ekstensi Txt
67
4.5 File Fibonacci Pada File Dokumen Input Dengan Ekstensi Doc
67
4.6 File Teks Hasil Decoding Dengan Ekstensi Txt
68
4.7 File Dokumen Hasil Decoding Dengan Ekstensi Doc
68
4.8 File Shannon-Fano Untuk File Teks Dengan Ekstensi Txt
73
4.9 File Shannon-Fano Untuk File Dokumen Dengan Ekstensi Doc
74
4.10 File Fibonacci Hasil Dekompresi Untuk File Teks Dengan Ekstensi Txt
75
4.11 File Fibonacci Hasil Dekompresi Untuk File Dokumen Dengan Ekstensi Doc
75
4.12 File Output Untuk File Teks Dengan Ekstensi Txt
77
4.13 File Output Untuk File Dokumen Dengan Ekstensi Doc
78
4.14 File Shannon-Fano Hasil Dekompresi Untuk File Teks Dengan Ekstensi Txt
79
4.15 File Shannon-Fano Hasil Dekompresi Untuk File Dokumen Dengan Ekstensi Doc
79
4.16 Splash Screen Aplikasi
80
4.17 Tab Menu Kompresi
80
4.18 Open File Dialog Pilih File Input Kompresi
81
4.19 Save File Dialog Untuk File Tujuan Output Kompresi
82
4.20 Tampilan Tab Menu Kompresi Setelah File Input Dan Output
Universitas Sumatera Utara
Ditentukan
82
4.21 Dialog Ringkasan Kompresi
83
4.22 Tampilan Tab Menu Dekompresi
83
4.23 Open File Dialog Pilih File Input Dekompresi
84
4.24 Tampilan Tab Menu Dekompresi Setelah File Input Ditentukan
84
4.25 Dialog Konfirmasi Ekstensi File Output Dekompresi
85
4.26 Save File Dialog File Tujuan Output Dekompresi
85
4.27 Dialog Ringkasan Dekompresi
86
4.28 Grafik Perbandingan Antara File Dokumen Input, File Fibonacci, Dan File Hasil Decoding Untuk File Dokumen Dengan Ekstensi Doc
89
4.29 Grafik Perbandingan Antara File Fibonacci, File Shannon-Fano, Dan File Hasil Dekompresi Shannon-Fano Untuk File Dokumen Dengan Ekstensi Doc
90
4.30 Grafik Perbandingan Antara File Shannon-Fano, File Output, Dan File Hasil Dekompresi Deflate Untuk File Dokumen Dengan Ekstensi Doc
91
4.31 Grafik Perbandingan Antara File Input, File Output, Dan File Hasil Dekompresi Untuk File Dokumen Dengan Ekstensi Doc
92
4.32 Grafik Perbandingan Antara Waktu Yang Dibutuhkan Untuk Kompresi dan Dekompresi Pada File Dokumen Dengan Ekstensi Doc
93
4.33 Grafik Perbandingan Antara File Teks Input, File Fibonacci, Dan File Hasil Decoding Untuk File Teks Dengan Ekstensi Txt
96
4.34 Grafik Perbandingan Antara File Fibonacci, File Shannon-Fano, Dan File Hasil Dekompresi Shannon-Fano Untuk File Teks Dengan Ekstensi Txt
97
4.35 Grafik Perbandingan Antara File Shannon-Fano, File Output, Dan File Hasil Dekompresi Deflate Untuk File Teks Dengan Ekstensi Txt
98
4.36 Grafik Perbandingan Antara File Input, File Output, Dan File Hasil Dekompresi Untuk File Teks Dengan Ekstensi Txt
99
Universitas Sumatera Utara
4.37 Grafik Perbandingan Antara Waktu Yang Dibutuhkan Untuk Kompresi dan Dekompresi Pada File Teks Dengan Ekstensi Txt
100
Universitas Sumatera Utara