ANALISIS PERBANDINGAN KINERJA ALGORITMA SHANNON-FANO, ARITHMETIC CODING, DAN HUFFMAN PADA KOMPRESI BERKAS TEKS DAN BERKAS CITRA DIGITAL SKRIPSI

ANALISIS PERBANDINGAN KINERJA ALGORITMA SHANNON-FANO, ARITHMETIC CODING, DAN HUFFMAN PADA KOMPRESI BERKAS TEKS DAN BERKAS CITRA DIGITAL

SKRIPSI

SYARIFAH KEUMALA ANDRIATY 091401084

PROGRAM STUDI S1 ILMU KOMPUTER FAKULTAS ILMU KOMPUTER DAN TEKNOLOGI INFORMASI UNIVERSITAS SUMATERA UTARA MEDAN 2013

Universitas Sumatera Utara


SKRIPSI Diajukan untuk melengkapi tugas dan memenuhi syarat memperoleh ijazah Sarjana Ilmu Komputer SYARIFAH KEUMALA ANDRIATY 091401084

PROGRAM STUDI S1 ILMU KOMPUTER FAKULTAS ILMU KOMPUTER DAN TEKNOLOGI INFORMASI UNIVERSITAS SUMATERA UTARA MEDAN 2013


ii

PERSETUJUAN

Judul

: ANALISIS PERBANDINGAN KINERJA ALGORITMA SHANNON-FANO, ARITHMETIC CODING, DAN HUFFMAN PADA KOMPRESI BERKAS TEKS DAN BERKAS CITRA DIGITAL

Kategori

: SKRIPSI

Nama

: SYARIFAH KEUMALA ANDRIATY

Nomor Induk Mahasiswa

: 091401084

Program Studi

: S1 ILMU KOMPUTER

Fakultas

: ILMU KOMPUTER DAN TEKNOLOGI INFORMASI UNIVERSITAS SUMATERA UTARA Diluluskan di Medan, 24 Juli 2013

Komisi Pembimbing

:

Pembimbing 2

Pembimbing 1

Syahriol Sitorus, S.SI, MIT

Drs. James Pieter Marbun, M.Kom

NIP. 19710310 199703 1 004

NIP. 19580611 198603 1 002

Diketahui/disetujui oleh Program Studi S1 Ilmu Komputer Ketua,

Dr. Poltak Sihombing, M.Kom NIP. 19620317 199103 1 001


iii

PERNYATAAN


SKRIPSI

Saya menyatakan bahwa skripsi ini adalah hasil karya saya sendiri, kecuali beberapa kutipan dan ringkasan yang masing-masing telah disebutkan sumbernya.

Medan,

Juli 2013

Syarifah Keumala Andriaty 091401084


iv

PENGHARGAAN

Puji dan syukur penulis panjatkan ke hadirat Allah SWT, yang telah memberikan rahmat dan hidayah-Nya, serta segala sesuatu dalam hidup, sehingga penulis dapat menyelesaikan penyusunan skripsi ini, sebagai syarat untuk memperoleh gelar Sarjana Komputer, Program Studi S1 Ilmu Komputer, Fakultas Ilmu Komputer dan Teknologi Informasi (Fasilkom-TI), Universitas Sumatera Utara. Ucapan terima kasih penulis sampaikan kepada semua pihak yang telah membantu penulis dalam menyelesaikan skripsi ini baik secara langsung maupun tidak langsung. Pada kesempatan ini penulis ingin mengucapkan terima kasih yang sebesar-besarnya kepada: 1. Bapak Prof. Dr. dr. Syahril Pasaribu, DTM&H, M.Sc.(CTM). Sp.A(K) selaku Rektor Universitas Sumatera Utara. 2. Bapak Prof. Dr. Muhammad Zarlis selaku Dekan Fasilkom-TI Universitas Sumatera Utara. 3. Bapak Dr. Poltak Sihombing, M. Kom. selaku Ketua Program Studi S1 Ilmu Komputer dan Dosen Penguji I. 4. Ibu Maya Silvi Lydia, B.Sc. M.Sc. selaku Sekretaris Program Studi S1 Ilmu Komputer dan Dosen Penguji II. 5. Bapak Drs. James Pieter Marbun, M. Kom. selaku Dosen Pembimbing I. 6. Bapak Syahriol Sitorus, S.Si., MIT. selaku Dosen Pembimbing II. 7. Seluruh dosen serta pegawai di Program Studi S1 Ilmu Komputer Fasilkom-TI USU. 8. Ayahanda Said Adnan dan Ibunda Darmiaty yang selalu memberikan dukungan, perhatian, dan doa tanpa henti kepada penulis. 9. Kakanda penulis Syarifah Dian Andriaty, SE, Ak., dr. Syarifah Nora Andriaty, Syarifah Lisa Andriati, SH, M.Hum., dan Syarifah Lia Andriaty, S.Hut. yang telah memberikan motivasi dan dukungan tanpa henti kepada penulis. 10. Muhammad Aidil Akbar, S.Kom. yang telah memberikan bimbingan, dukungan, dan perhatian kepada penulis. 11. Teman-teman sekaligus keluarga besar Program Studi S1 Ilmu Komputer Fasilkom-TI USU. 12. Semua pihak yang terlibat langsung maupun tidak langsung yang tidak dapat penulis ucapkan satu demi satu yang telah membantu penyelesaian skripsi ini. Penulis menyadari bahwa skripsi ini masih terdapat kekurangan. Oleh karena itu, penulis mengharapkan kritik dan saran yang bersifat membangun demi kesempurnaan skripsi ini.


v

Medan, Juli 2013 Penulis,

Syarifah Keumala Andriaty


vi

ABSTRAK

Kompresi data merupakan proses mereduksi ukuran suatu data untuk menghasilkan representasi digital yang padat atau mampat (compact) namun tetap dapat mewakili kuantitas informasi yang terkandung pada data tersebut. Proses kompresi data sangat diperlukan pada dunia komputerisasi, yaitu pada proses pengiriman data, dan pada penyimpanan data tersebut. Kompresi data dapat dilakukan secara lossy dan lossless. Pada kompresi data yang bersifat lossy, data dapat dimampatkan dan didekompresi dengan perubahan informasi di dalamnya, sehingga data asli berbeda dengan data hasil. Pada kompresi data yang bersifat lossless, data dapat dimampatkan dan didekompresi tanpa kehilangan informasi, sehingga metode kompresi dengan sifat lossless dapat diterapkan pada keperluan medis dan lain sebagainya. Pada penelitian ini dilakukan implementasi beberapa algoritma kompresi yang bersifat lossless, yaitu Shannon-Fano, Arithmetic Coding dan Huffman yang bertujuan untuk mengetahui algoritma paling optimal di antara ketiga algoritma tersebut. Parameter perbandingan kinerja algoritma yang digunakan adalah waktu kompresi, rasio kompresi, faktor kompresi, saving percentage, dan kompleksitas algoritma (Big-O). Aplikasi pendukung yang dibangun pada penelitian ini adalah suatu aplikasi kompresi dengan berkas teks dengan format *.txt dan berkas citra digital dengan format *.bmp. Berdasarkan percobaan pada lima buah berkas teks dan lima buah berkas citra digital, diketahui bahwa algoritma Shannon-Fano merupakan algoritma teroptimal dibandingkan Arithmetic Coding dan Huffman, notasi Big-O dari algoritma Shannon-Fano dan Arithmetic Coding adalah O(n), sedangkan nilai notasi Big-O dari algoritma Huffman adalah O(n2). Katakunci: kompresi data, Shannon-Fano, Arithmetic Coding, Huffman.


vii

COMPARATIVE PERFORMANCE ANALYSIS OF COMPRESSION ALGORITHMS SHANNON-FANO, ARITHMETIC CODING, AND HUFFMAN IN TEXT FILE AND DIGITAL FILE IMAGE

ABSTRACT

Data compression is process of reducing the size of data to produce a digital representation of a compressed or compact but still be able to represent the quantity of information that contained in the data. Data compression is required in computerization, which in the process of data sending, and in data storage. Data compression can be implemented in lossy method or lossles method. In lossy data compression, data can be compressed and decompressed with some differences of information between original data and result data. In lossless data compression, data can be compressed and decompressed without lossing any information, so that nature of lossless compression method can be applied to medical purposes and so on. In this research, algorithms of compression data implemented with lossless method, which are Shannon-Fano, Arithmetic Coding, and Huffman that aims to find the most optimal algorithm between them. The comparison parameters of the performance of the algorithms used are compression time, compression ratio, compression factor, saving percentage of memory, and algorithmic complexity (Big-O). Supporting application that built in this research is a compression application with text file formatted in *.txt and digital image file formatted in *.bmp. Based on experiments on five text files and five image files, concluded that Shannon-Fano algorithm is the most optimal algorithm compared to Arithmetic Coding and Huffman, Big-O notation from Shannon-Fano and Arithmetic Coding algorithm is O(n), and Big-O notation from Huffman algorithm is O(n2). Keyword: data compression, Shannon-Fano, Arithmetic Coding, Huffman.


viii

DAFTAR ISI

Hal. ii iii iv vi vii viii xi xiii

Persetujuan Pernyataan Penghargaan Abstrak Abstract Daftar Isi Daftar Tabel Daftar Gambar Bab 1 Pendahuluan 1.1 Latar Belakang Masalah 1.2 Rumusan Masalah 1.3 Batasan Masalah 1.4 Tujuan Penelitian 1.5 Manfaat Penelitian 1.6 Metodologi Penelitian 1.7 Sistematika Penulisan

1 2 2 2 3 3 4

Bab 2 Landasan Teori 2.1 Definisi Data 2.2 Kompresi Data 2.3 Data Berlebihan (Data Redundancy) 2.4 Teknik Kompresi Citra 2.5 Berkas Teks 2.6 Citra Digital 2.7 Pengolahan Citra Digital 2.8 Format Berkas Bitmap (*.bmp) 2.9 Informasi Teori dan Entropi 2.10 Algoritma Shannon-Fano 2.11 Algoritma Arithmetic Coding 2.12 Algoritma Huffman 2.13 Kompleksitas Algoritma (Notasi Big-O) 2.14 Evaluasi Kinerja Algoritma 2.15 Penelitian yang Relevan 2.15.1 Studi perbandingan kinerja algoritma kompresi Shannon-Fano dan Huffman pada citra digital 2.15.2 Analisis kinerja dan implementasi algoritma kompresi Arithmetic Coding pada file teks dan citra digital 2.15.3 Implementasi Algoritma Huffman pada Kompresi Citra BMP

5 6 7 8 9 10 10 11 11 12 12 13 14 15 16 16 16 17


ix

2.15.4 Analisis Perbandingan Teknik Kompresi Menggunakan Algoritma Shannon-Fano, dan Run Length Encoding pada Citra Berformat BMP dan PNG Bab 3 Analisis Dan Perancangan Sistem 3.1 Analisis Sistem 3.1.1 Ruang lingkup masalah 3.1.2 Analisis masalah 3.1.3 Analisis kebutuhan 3.1.4 Desain logis 3.2 Pseudocode 3.2.1 Pseudocode pembacaan berkas 3.2.2 Pseudocode pengurutan frekuensi 3.2.3 Pseudocode kompresi algoritma Shannon-Fano 3.2.4 Pseudocode dekompresi algoritma Shannon-Fano 3.2.5 Pseudocode kompresi algoritma Arithmetic Coding 3.2.6 Pseudocode dekompresi algoritma Arithmetic Coding 3.2.7 Pseudocode kompresi algoritma Huffman 3.2.8 Pseudocode dekompresi algoritma Huffman 3.3 Perancangan Antarmuka 3.3.1 Struktur menu 3.3.2 Perancangan grafis antarmuka

Hal. 17

18 18 18 20 20 28 28 29 31 34 36 41 43 49 51 51 51

Bab 4 Implementasi Dan Pengujian 4.1 Implementasi Algoritma Shannon-Fano 4.1.1 Kompresi algoritma Shannon-Fano 4.1.2 Dekompresi algoritma Shannon-Fano 4.1.3 Kompleksitas waktu algoritma Shannon-Fano 4.2 Implementasi Algoritma Arithmetic Coding 4.2.1 Kompresi algoritma Arithmetic Coding 4.2.2 Dekompresi algoritma Arithmetic Coding 4.2.3 Kompleksitas waktu algoritma Arithmetic Coding 4.3 Implementasi Algoritma Huffman 4.3.1 Kompresi algoritma Huffman 4.3.2 Dekompresi algoritma Huffman 4.3.3 Kompleksitas waktu algoritma Huffman 4.4 Implementasi Perangkat Lunak 4.4.1 Konfigurasi perangkat keras 4.4.2 Konfigurasi perangkat lunak 4.4.3 Hasil eksekusi aplikasi 4.5 Pengujian Sistem 4.5.1 Skenario pengujian 4.5.2 Pengujian kompresi berkas teks 4.5.3 Pengujian kompresi berkas citra

54 54 57 57 61 61 64 68 73 73 77 78 82 82 82 82 93 93 95 114

Bab 5 Kesimpulan dan Saran 5.1 Kesimpulan 5.2 Saran

131 131 131


x

Daftar Pustaka

Hal. 133

Lampiran Listing Program Lampiran Curriculum Vitae

A-1 B-1


xi

DAFTAR TABEL

Nomor Tabel 3.1 3.2 3.3 3.4 4.1 4.2 4.3 4.4 4.5 4.6 4.7 4.8 4.9 4.10 4.11 4.12 4.13 4.14 4.15 4.16 4.17 4.18 4.19 4.20 4.21 4.22 4.23 4.24 4.25 4.26 4.27 4.28 4.29 4.30 4.31 4.32 4.33 4.34 4.35

Nama Tabel

Halaman

Penyebab dan Akibat Dokumentasi Naratif Use Case Kompresi Dokumentasi Naratif Use Case Dekompresi Dokumentasi Naratif Use Case Tentang Aplikasi Pendataan Karakter Shannon-Fano Pengurutan Frekuensi Shannon-Fano Pembagian Bobot Frekuensi I Pembagian Bobot Frekuensi II Pembagian Bobot Frekuensi III Pembagian Bobot Frekuensi IV Codebook Shannon-Fano Kompleksitas Waktu Kompresi Algoritma Shannon-Fano Kompleksitas Waktu Dekompresi Algoritma Shannon-Fano Pendataan Karakter Arithmetic Coding Probabilitas Frekuensi Kemunculan Setiap Karakter Jangkauan Setiap Karakter Kompresi Arithmetic Coding Library Arithmetic Coding Kompleksitas Waktu Kompresi Algoritma Arithmetic Coding Kompleksitas Waktu Dekompresi Algoritma Arithmetic Coding Pendataan Karakter Huffman Pengurutan Frekuensi Huffman I Frekuensi Huffman I Pengurutan Frekuensi Huffman II Frekuensi Huffman II Pengurutan Frekuensi Huffman III Frekuensi Huffman III Pengurutan Frekuensi Huffman IV Codebook Huffman Kompleksitas Waktu Kompresi Algoritma Huffman Kompleksitas Waktu Dekompresi Algoritma Huffman Berkas Teks Uji Berkas Citra Uji Properties Berkas Teks satu.txt Properties Berkas Teks bab4.txt Properties Berkas Teks excel.txt Properties Berkas Teks data.txt Properties Berkas Teks flower.txt Analisis Kompresi Berkas Teks Algoritma Shannon-Fano

19 22 23 24 54 55 55 55 56 56 56 58 60 61 61 62 62 65 69 71 73 73 74 74 74 75 75 75 76 78 81 94 94 96 97 98 99 100 101


xii

Nomor Tabel 4.36 4.37 4.38 4.39 4.40 4.41 4.42 4.43 4.44 4.45 4.46 4.47 4.48 4.49 4.50 4.51 4.52 4.53 4.54 4.55

Nama Tabel

Halaman

Analisis Kompresi Berkas Teks Algoritma Arithmetic Coding Analisis Kompresi Berkas Teks Algoritma Huffman Analisis Algoritma Kompresi pada Berkas Teks Kompleksitas Waktu Algoritma Shannon-Fano pada Berkas Teks Kompleksitas Waktu Algoritma Arithmetic Coding pada Berkas Teks Kompleksitas Waktu Algoritma Huffman pada Berkas Teks Kompleksitas Waktu Algoritma Shannon-Fano, Arithmetic Coding, dan Huffman pada Berkas Teks Properties Berkas Citra bee.bmp Properties Berkas Citra bow.bmp Properties Berkas Citra butterfly.bmp Properties Berkas Citra flower.bmp Properties Berkas Citra rainbow.bmp Analisis Kompresi Berkas Citra Algoritma Shannon-Fano Analisis Kompresi Berkas Citra Algoritma Arithmetic Coding Analisis Kompresi Berkas Citra Algoritma Huffman Analisis Algoritma Kompresi pada Berkas Citra Kompleksitas Waktu Algoritma Shannon-Fano pada Berkas Citra Kompleksitas Waktu Algoritma Arithmetic Coding pada Berkas Citra Kompleksitas Waktu Algoritma Huffman pada Berkas Citra Kompleksitas Waktu Algoritma Shannon-Fano, Arithmetic Coding, dan Huffman pada Berkas Citra

103 105 107 109 110 111 112 114 115 116 117 118 119 121 123 125 127 128 129 130


xiii

DAFTAR GAMBAR

Nomor Gambar 2.1 2.2 2.3 2.4 2.5 2.6 3.1 3.2 3.3 3.4 3.5 3.6 3.7 3.8 3.9 3.10 3.11 3.12 3.13 3.14 3.15 3.16 3.17 3.18 3.19 3.20 3.21 3.22 3.23 3.24 3.25 4.1 4.2 4.3 4.4 4.5 4.6 4.7 4.8 4.9 4.10

Nama Gambar

Halaman

Model Dasar Sistem Informasi Model Pengembangan Sistem Informasi Susunan Data Ilustrasi Kompresi Lossless Ilustrasi Kompresi Lossy Nilai-nilai pada Piksel Diagram Ishikawa Use Case Diagram pada Aplikasi Kompresi Diagram Aktivitas pada Aplikasi Kompresi Diagram Sekuensial Proses Kompresi Diagram Sekuensial Proses Dekompresi Flowchart Pembacaan Berkas Flowchart Pengurutan Frekuensi Karakter Flowchart Kompresi Algoritma Shannon-Fano 1 Flowchart Kompresi Algoritma Shannon-Fano 2 Flowchart Dekompresi Algoritma Shannon-Fano Flowchart Kompresi Algoritma Arithmetic Coding 1 Flowchart Kompresi Algoritma Arithmetic Coding 2 Gambar 3.13 Flowchart Method FindDecimal() Flowchart Method FindBinary() Flowchart Dekompresi Algoritma Arithmetic Coding 1 Flowchart Dekompresi Algoritma Arithmetic Coding 2 Flowchart Method FindLowest() 1 Flowchart Method FindLowest() 2 Flowchart Kompresi Algoritma Huffman Flowchart Dekompresi Algoritma Huffman Struktur Menu Aplikasi Kompresi Rancangan Halaman Utama Rancangan Halaman Kompresi Rancangan Halaman Dekompresi Rancangan Halaman About Rescaling Bilangan Desimal I Rescaling Bilangan Desimal II Rescaling Bilangan Desimal III Rescaling Library Arithmetic Coding Pencarian Bilangan Biner I Pencarian Bilangan Biner II Pencarian Bilangan Biner III Tree α Tree β Tree γ

5 5 6 9 9 10 19 21 25 27 27 29 30 32 33 35 38 39 39 40 42 43 46 47 48 50 51 52 52 53 53 63 63 64 66 66 67 68 73 74 75


xiv

No Gambar 4.11 4.12 4.13 4.14 4.15 4.16 4.17 4.18 4.19 4.20 4.21 4.22 4.23 4.24 4.25 4.26 4.27 4.28 4.29 4.30 4.31 4.32 4.33 4.34 4.35 4.36 4.37 4.38 4.39 4.40 4.41 4.42 4.43 4.44 4.45 4.46

Nama Gambar

Halaman

Tree δ Huffman’s Tree Tampilan Halaman Utama Tampilan Halaman Kompresi Tampilan Dialog Pilih Berkas Kompresi Tampilan Properties Berkas I Tampilan Berkas “bab4.txt” Tampilan Kompresi Algoritma Shannon-Fano Tampilan Berkas “bab4.sh” Tampilan Kompresi Algoritma Arithmetic Coding Tampilan Berkas “bab4.ar” Tampilan Kompresi Algoritma Huffman Tampilan Berkas “bab4.hf” Tampilan Halaman Dekompresi Tampilan Dialog Pilih Berkas Dekompresi Tampilan Properties Berkas II Tampilan Dekompresi Algoritma Tampilan Halaman Tentang Aplikasi Pengujian Berkas Teks satu.txt Pengujian Berkas Teks bab4.txt Pengujian Berkas Teks excel.txt Pengujian Berkas Teks data.txt Pengujian Berkas Teks flower.txt Grafik Analisis Algoritma Shannon-Fano pada Berkas Teks Grafik Analisis Algoritma Arithmetic Coding pada Berkas Teks Grafik Analisis Algoritma Huffman pada Berkas Teks Grafik Analisis Algoritma Shannon-Fano, Arithmetic Coding, dan Huffman pada Berkas Teks Pengujian Berkas Citra bee.bmp Pengujian Berkas Citra bow.bmp Pengujian Berkas Citra butterfly.bmp Pengujian Berkas Citra flower.bmp Pengujian Berkas Citra rainbow.bmp Grafik Analisis Algoritma Shannon-Fano pada Berkas Citra Grafik Analisis Algoritma Arithmetic Coding pada Berkas Citra Grafik Analisis Algoritma Huffman pada Berkas Citra Grafik Analisis Algoritma Shannon-Fano, Arithmetic Coding, dan Huffman pada Berkas Citra

76 76 83 83 84 84 85 85 86 87 88 89 89 90 91 91 92 93 96 97 98 99 100 102 104 106 108 114 115 116 117 118 120 122 124 126


ANALISIS PERBANDINGAN KINERJA ALGORITMA SHANNON-FANO, ARITHMETIC CODING, DAN HUFFMAN PADA KOMPRESI BERKAS TEKS DAN BERKAS CITRA DIGITAL SKRIPSI

Recommend Documents