PERBANDINGAN ALGORITMA EVEN-RODEH CODE DAN ALGORITMA VARIABLE LENGTH BINARY ENCODING (VLBE) PADA KOMPRESI FILE TEKS
SKRIPSI
ADE RANI ABDULLAH 121401012
PROGRAM STUDI S1 ILMU KOMPUTER FAKULTAS ILMU KOMPUTER DAN TEKNOLOGI INFORMASI UNIVERSITAS SUMATERA UTARA MEDAN 2016
Universitas Sumatera Utara
PERBANDINGAN ALGORITMA EVEN-RODEH CODE DAN ALGORITMA VARIABLE LENGTH BINARY ENCODING (VLBE) PADA KOMPRESI FILE TEKS SKRIPSI
Diajukan untuk melengkapi tugas akhir dan memenuhi syarat mencapai gelar Sarjana Komputer
ADE RANI ABDULLAH 121401012
PROGRAM STUDI S1 ILMU KOMPUTER FAKULTAS ILMU KOMPUTER DAN TEKNOLOGI INFORMASI UNIVERSITAS SUMATERA UTARA MEDAN 2016
Universitas Sumatera Utara
PERSETUJUAN
Judul
: PERBANDINGAN ALGORITMA EVEN-RODEH CODE DAN
ALGORITMA
VARIABLE
LENGTH
BINARY
ENCODING (VLBE) PADA KOMPRESI FILE TEKS Kategori
:
SKRIPSI
Nama
:
ADE RANI ABDULLAH
Nomor Induk Mahasiswa
:
121401012
Program Studi
:
S1 ILMU KOMPUTER
Fakultas
: ILMU KOMPUTER DAN TEKNOLOGI INFORMASI UNIVERSITAS SUMATERA UTARA
Diluluskan di Medan, Mei 2016
Komisi Pembimbing :
Pembimbing 2
Pembimbing 1
Herriyance, ST, M.Kom
Mohammad Andri Budiman, ST, M.Comp.Sc, M.E.M
NIP. 198010242010121002
NIP. 197510082008011011
Diketahui/Disetujui oleh Program Studi S1 Ilmu Komputer Ketua,
Dr. Poltak Sihombing, M.Kom NIP. 196203171991031001
Universitas Sumatera Utara
PERNYATAAN
PERBANDINGAN ALGORITMA EVEN-RODEH CODE DAN ALGORITMA VARIABLE LENGTH BINARY ENCODING (VLBE) PADA KOMPRESI FILE TEKS
SKRIPSI
Saya mengakui bahwa skripsi ini adalah hasil karya saya sendiri, kecuali beberapa kutipan dan ringkasan yang masing-masing telah disebutkan sumbernya.
Medan, Mei 2016
Ade Rani Abdullah 121401012
Universitas Sumatera Utara
iv
PENGHARGAAN
Alhamdulillah. Puji dan syukur kehadirat Allah SWT, yang dengan rahmat dan karunia-Nya penulis dapat menyelesaikan penyusunan skripsi ini, sebagai syarat untuk memperoleh gelar Sarjana Komputer, pada Program Studi S1 Ilmu Komputer Fakultas Ilmu Komputer dan Teknologi Informasi Universitas Sumatera Utara.
Pada pengerjaan skripsi dengan judul Perbandingan Algoritma Even-Rodeh Code dan Algoritma Variable Length Binary Encoding (VLBE) pada Kompresi File Teks, penulis menyadari bahwa banyak pihak yang turut membantu, baik dari pihak keluarga, sahabat dan orang-orang terkasih yang memotivasi dalam pengerjaannya. Dalam kesempatan ini, penulis mengucapkan terima kasih kepada:
1. Bapak Prof. Dr. Runtung Sitepu, SH, M.Hum selaku Rektor Universitas Sumatera Utara. 2. Bapak Prof. Dr. Opim Salim Sitompul, M.Sc selaku Dekan Fakultas Ilmu Komputer dan Teknologi Informasi Universitas Sumatera Utara. 3. Bapak Dr. Poltak Sihombing, M.Kom selaku Dosen Pembanding I dan Ketua Program Studi S1 Ilmu Komputer Fakultas Ilmu Komputer dan Teknologi Informasi Universitas Sumatera Utara. 4. Bapak Mohammad Andri Budiman, ST, M.Comp.Sc, M.E.M selaku Dosen Pembimbing I yang telah memberikan arahan, kritik dan saran serta motivasi kepada penulis dalam pengerjaan skripsi ini. 5. Bapak Herriyance, ST, M.Kom selaku Dosen Pembimbing II yang telah memberikan arahan, kritik dan saran kepada penulis dalam pengerjaan skripsi ini. 6. Bapak Ade Candra, ST, M.Kom selaku Dosen Pembanding II yang telah banyak memberikan arahan dan masukan yang sangat berharga kepada penulis. 7. Seluruh tenaga pengajar dan pegawai di Fakultas Ilmu Komputer dan Teknologi Informasi USU.
Universitas Sumatera Utara
v
8. Ayahanda Selamet Dahlan, Ibunda Nurbaiti Rambe, Abangda Wawan Abdullah dan Wadi Abdullah serta Kakanda Lira Abdullah dan Wiwik Zahria Abdullah, yang mana telah banyak memberikan kasih sayang, semangat, serta dorongan kepada penulis. 9. Salawatbadar, yang selama ini telah menjadi keluarga kedua penulis selama mengikuti perkuliahan, tempat berbagi suka dan duka dalam pengerjaan skripsi ini, kepada Sari Rahmadani Siregar, Ade Mutiara Kartika Dewi Nasution, Astrid Febrina Ramadhani Siregar, S.Kom, dan T. Raisya Hannisa, S.Kom. 10. Teman-teman kuliah khususnya Nurhasbiah Nasution, S.Kom, Dwi Puspita Sari Syahnan, S.Kom, Muhammad Miftahul Huda, Indah Widya Sari, serta stambuk 2012 yang tidak dapat disebut satu-persatu, serta Abangda Singgih Tri Mukti Ardianto, S.Kom dan Abangda Farid Akbar Siregar, S.Kom yang telah memberikan semangat dan banyak membantu dalam selesainya pengerjaan skripsi ini. 11. Sahabat-sahabat seperjuangan menggapai gelar sarjana, kepada Melva Sari Yulia Saragih, Diah Permatasari, SE, Nike Jahrona Harahap, Amd.RMIK, Linda Nopita Sari Siregar, Nurkhoiriyah Siregar, S.Pd, Ardiansyah Putra, dan Edy Chandra Harahap. 12. Rekan-rekan pengurus IMILKOM (Ikatan Mahasiswa S1 Ilmu Komputer) Fasilkom-TI 2015-2016 yang telah memberikan banyak dukungan, tempat belajar berorganisasi yang benar, dan menimba pengalaman. 13. Semua pihak yang terlibat langsung maupun tidak langsung yang tidak dapat penulis ucapkan satu demi satu yang telah membantu penyelesaian laporan ini.
Semoga Allah SWT melimpahkan berkah kepada semua pihak yang telah memberikan bantuan, perhatian, serta dukungan kepada penulis dalam menyelesaikan skripsi ini.
Medan,
Mei 2016
Penulis,
Ade Rani Abdullah
Universitas Sumatera Utara
iv
ABSTRAK
Teknologi berperan penting dalam pengiriman informasi. Kompresi bertujuan untuk mengurangi ukuran data menjadi lebih kecil dari ukuran aslinya. Algoritma EvenRodeh Code dan Variable Length Binary Encoding (VLBE) merupakan jenis kompresi lossless yang digunakan dalam penelitian ini, yang mana akan diukur kinerjanya dengan Compression Ratio (CR), Ratio of Compression (RC), Redundancy (Rd), waktu kompresi (milisekon) dan waktu dekompresi (milisekon). Kompresi file melakukan proses dengan membaca string dalam file teks berekstensi *.rtf. Hasil akhir dari kompresi adalah file berekstensi *.erc atau *.vlbe. Penelitian ini menggunakan String Homogen (string dengan karakter yang sama) dan String Heterogen (string dengan karakter yang bervariasi). Algoritma Even-Rodeh Code dan algoritma Variable Length Binary Encoding (VLBE) dipengaruhi oleh jumlah variasi karakter. Dalam proses kompresi pada string homogen algoritma Variable Length Binary Binary Encoding (VLBE) lebih baik dibandingkan algoritma Even-Rodeh Code dengan Compression Ratio rata-rata sebesar 16.47% dan waktu dekompresi lebih cepat dengan rata-rata 0.153 milisekon. Dalam proses kompresi pada string heterogen algoritma Even-Rodeh Code lebih baik dibandingkan algoritma Variable Length Binary Binary Encoding (VLBE) dengan Compression Ratio rata-rata sebesar 60.546% dan waktu dekompresi lebih cepat dengan rata-rata 0.1187 milisekon.
Kata Kunci : Kompresi, File Teks, Even-Rodeh Code, Variable Length Binary Encoding (VLBE).
Universitas Sumatera Utara
v
A COMPARISON OF EVEN-RODEH CODE AND VARIABLE LENGTH BINARY ENCODING (VLBE) ALGORITHM IN TEXT FILE COMPRESSION
ABSTRACT
Technology has an important role in dispatch information. Compression has a purpose to diminish the measurement of the data becomes smaller from the authentic data. Even-Rodeh Code and Variable Length Binary Encoding (VLBE) Algorithm are the kinds of lossless compression that used in this research, it will be measured the performance by Compression Ratio (CR), Ratio of Compression (RC), Redundancy (RD), Time of Compression (millisecond) and Time of Decompression (millisecond). The file of compression does the process by reading the string in a text file of extension *.rtf. This research uses string homogenous (string by the same character) and string heterogeneous (string by the various characters). Even-Rodeh Code And Variable Length Binary Encoding (VLBE) algorithm are affected by the number of variations in character. In the compression process to the string homogenous Variable Length Binary Encoding (VLBE) algorithm is better than Even-Rodeh Code algorithm shows the Compression Ratio on the average in the amount about 16.47 % and the time of decompression is faster about 0.153 millisecond. In the compression process to the string heterogeneous Even-Rodeh Code algorithm is better than Variable Length Binary Encoding (VLBE) algorithm by the Compression Ratio about 60.546% and the time of decompression is faster about 0.1187 millisecond.
Keywords: Compression, Text File, Even-Rodeh Code, Variable Length Binary Encoding (VLBE).
Universitas Sumatera Utara
viii
DAFTAR ISI
Hal. Persetujuan
ii
Pernyataan
iii
Penghargaan
iv
Abstrak
vi
Abstract
vii
Daftar Isi
viii
Daftar Tabel
x
Daftar Gambar
xi
Daftar Lampiran
xii
Bab 1 Pendahuluan
1
1.1 Latar Belakang
2
1.2 Rumusan Masalah
2
1.3 Batasan Penelitian
3
1.4 Tujuan Penelitian
3
1.5 Manfaat Penelitian
3
1.6 Metodologi Penelitian
3
1.7 Sistematika Peneltian
4
Bab 2 Tinjauan Pustaka
6
Universitas Sumatera Utara
ix
2.1 Kompresi Data
6
2.2 Teknik Kompresi
7
2.2.1 Kompresi Loseless (Lossless Compression)
7
2.2.2 Kompresi Lossy (Lossy Compression)
8
2.2.3 Padding dan Flag Bits
9
2.2.4 Pengukuran kinerja kompresi data
9
2.3 Algoritma
11
2.3.1 Pengertian Algoritma
11
2.3.2 Ciri-ciri Algoritma
11
2.4 Algoritma Even-Rodeh Code
11
2.5 Algoritma Variable Length Binary Encoding (VLBE)
12
2.6 File Teks
13
2.7 Kompleksitas Algoritma
16
2.8 Penelitian yang Relevan
17
Bab 3 Analisis Dan Perancangan Sistem 3.1 Analisis Sistem
18 18
3.1.1 Analisis masalah
18
3.1.2 Analisis persyaratan
19
3.1.3 Pemodelan Sistem
20
3.1.4 Pseudocode
25
3.1.5 Flowchart
26
3.2 Perancangan Interface
28
Bab 4 Implementasi Dan Pengujian Sistem
35
4.1. Implementasi Algoritma
35
Universitas Sumatera Utara
x
4.1.1 Implementasi Algoritma Even-Rodeh Code
35
4.1.2 Implementasi Algoritma Variable Length Binary Encoding
42
(VLBE) 4.2 Implementasi Sistem
47
4.2.1 Form Beranda
47
4.2.2 Form Kompresi
47
4.2.3 Form Dekompresi
48
4.2.4 Form Bantuan
49
4.2.5 Form Tentang
49
4.3 Pengujian Sistem
50
4.3.1 Pengujian proses kompresi
50
4.3.2 Pengujian proses dekompresi
53
4.4 Hasil Pengujian
55
4.5 Kompleksitas Algoritma
64
4.5.1 Kompleksitas Algoritma Even-Rodeh Code
64
4.5.2 Kompleksitas Algoritma Variable Length Binary Encoding
65
(VLBE)
Bab 5 Kesimpulan Dan Saran 5.1 Kesimpulan 5.2 Saran
Daftaf Pustaka
67 67 68
69
Universitas Sumatera Utara
viii
DAFTAR TABEL
Hal. Tabel 2.1 Tabel 2.2 Tabel 2.3 Tabel 4.1 Tabel 4.2 Tabel 4.3 Tabel 4.4 Tabel 4.5
Kode Omega dan Even-Rodeh Code Kode Variable Length Binary Encoding (VLBE) ASCII Penjelasan string yang belum dikompresi String yang belum dikompresi Cara pengkodean algoritma Even-Rodeh Code String yang sudah dikompresi dengan Even-Rodeh Code Cara pengkodean algoritma Variable Length Binary Encoding (VLBE) Tabel 4.6 String yang sudah dikompresi dengan Variable Length Binary Encoding Tabel 4.7 Hasil Pengujian String Homogen dengan Even-Rodeh Code Tabel 4.8 Hasil Pengujian String Homogen dengan Variable Length Binary Encoding (VLBE) Tabel 4.9 Hasil Pengujian String Heterogen dengan Even-Rodeh Code Tabel 4.10 Hasil Pengujian String Heterogen dengan Variable Length Binary Encoding (VLBE) Tabel 4.11 Kompleksitas Algoritma Even-Rodeh Code Tabel 4.12 Kompleksitas Algoritma Variable Length Binary Encoding (VLBE)
12 13 14 35 37 39 38 43 44 55 56 60 60 64 65
Universitas Sumatera Utara
xi
DAFTAR GAMBAR
Hal. Gambar 2.1 Gambar 2.2 Gambar 2.3 Gambar 3.1 Gambar 3.2 Gambar 3.3 Gambar 3.4
Diagram Blok Proses Kompresi dan Dekompresi Data Teknik Kompresi Loseless Teknik Kompresi Lossy Diagram Ishikawa Use Case Diagram pada sistem Activity Diagram proses Kompresi Even-Rodeh Code Activity Diagram proses Kompresi Variable Length Binary Encoding Gambar 3.5 Sequence Diagram proses Kompresi Even-Rodeh Code Gambar 3.6 Sequence Diagram proses Kompresi Variable Length Binary Encoding (VLBE) Gambar 3.7 Flowchart Sistem Secara Umum Gambar 3.8 Flowchart algoritma Even-Rodeh Code Gambar 3.9 Flowchart algoritma Variable Length Binary Encoding (VLBE) Gambar 3.10 Form Beranda pada Sistem Gambar 3.11 Form Kompresi pada Sistem Gambar 3.12 Form Dekompresi pada Sistem Gambar 3.13 Form Bantuan pada Sistem Gambar 3.14 Form Tentang pada Sistem Gambar 4.1 Form Beranda Gambar 4.2 Form Kompresi Gambar 4.3 Form Dekompresi Gambar 4.4 Form Bantuan Gambar 4.5 Form Tentang Gambar 4.6 Open File Dialog untuk Input File Teks Gambar 4.7 Radio Button untuk memilih algoritma Gambar 4.8 Aplikasi setelah File input dan Output ditentukan Gambar 4.9 Informasi Hasil Kompresi Gambar 4.10 File Even-Rodeh Code Hasil Kompresi Gambar 4.11 File Variable Length Binary Encoding Hasil Kompresi Gambar 4.12 Open File Dialog untuk file VLBE Gambar 4.13 Informasi Hasil Dekompresi Gambar 4.14 Save Dialog untuk hasil Dekompresi Gambar 4.15 Grafik Ratio of Compression terhadap String Homogen Gambar 4.16 Grafik Compression Ratio terhadap String Homogen Gambar 4.17 Grafik Redundancy terhadap String Homogen Gambar 4.18 Grafik Waktu Kompresi terhadap String Homogen Gambar 4.19 Grafik Waktu Dekompresi terhadap String Homogen Gambar 4.20 Grafik Ratio of Compression terhadap String Heterogen Gambar 4.21 Grafik Compression Ratio terhadap String Heterogen Gambar 4.22 Grafik Redundancy terhadap String Heterogen Gambar 4.23 Grafik Waktu Kompresi terhadap String Heterogen Gambar 4.24 Grafik Waktu Dekompresi terhadap String Heterogen
7 8 8 19 21 22 23 24 24 26 27 28 29 30 31 33 34
47 48 49 49 50 51 51 52 52 53 53 54 54 55 56 57 58 58 59 61 61 62 63 63
Universitas Sumatera Utara
xii
DAFTAR LAMPIRAN
Lampiran 1 Lampiran 2
Listing Program Daftar Riwayat Hidup
Hal. A-1 B-1
Universitas Sumatera Utara
