STUDI PERBANDINGAN ALGORITMA HUFFMAN DAN SHANNON-FANO DALAM PEMAMPATAN FILE TEKS
SKRIPSI
NURFITA SARI HASIBUAN 051411012
PROGRAM STUDI SARJANA MATEMATIKA DEPARTEMEN MATEMATIKA FAKULTAS MATEMATIKA DAN ILMU PENGETAHUAN ALAM UNIVERSITAS SUMATERA UTARA MEDAN 2008
STUDI PERBANDINGAN ALGORITMA HUFFMAN DAN SHANNON-FANO DALAM PEMAMPATAN FILE TEKS
SKRIPSI
Diajukan untuk melengkapi tugas dan memenuhi syarat mencapai gelar Sarjana Sains
NURFITA SARI HASIBUAN 051411012
PROGRAM STUDI SARJANA MATEMATIKA DEPARTEMEN MATEMATIKA FAKULTAS MATEMATIKA DAN ILMU PENGETAHUAN ALAM UNIVERSITAS SUMATERA UTARA MEDAN 2008
PERSETUJUAN
Judul
Kategori Nama Nomor Induk Mahasiswaa Program Studi Departemen Fakultas
: STUDI PERBANDINGAN ALGORITMA HUFFMAN DAN SHANNON-FANO DALAM PEMAMPATAN FILE TEKS : SKRIPSI : NURFITA SARI HASIBUAN : 051411012 : SARJANA (S1) MATEMATIKA : MATEMATIKA : MATEMATIKA DAN ILMU PENGETAHUAN ALAM (FMIPA) UNIVERSITAS SUMATERA UTARA
Medan,
Komisi Pembimbing
Mei 2008
:
Pembimbing 2,
Pembimbing1,
Drs. Bambang Irawan, M.Sc. NIP. 130535840
Syahriol Sitorus, S.Si, M.IT. NIP. 132174687
Diketahui/Disetujui oleh Departemen Matematika FMIPA USU Ketua,
Dr. Saib Suwilo, M.Sc. NIP. 131796149
PERNYATAAN
STUDI PERBANDINGAN ALGORITMA HUFFMAN DAN SHANNON-FANO DALAM PEMAMPATAN FILE TEKS
SKRIPSI
Saya mengakui bahwa skripsi ini adalah hasil kerja saya sendiri, kecuali beberapa kutipan dan ringkasan yang masing-masing disebutkan sumbernya.
Medan,
Mei 2008
Nurfita Sari Hasibuan 051411012
PENGHARGAAN
Puji dan syukur penulis panjatkan kehadirat Tuhan Yang Maha Pemurah dan Maha Penyayang, dengan limpahan rahmat dan karunia-Nya skripsi ini berhasil diselesaikan dalam waktu yang telah ditetapkan. Ucapan terima kasih saya sampaikan kepada Bapak Syahriol Sitorus, S.Si, M.IT. dan Bapak Drs. Bambang Irawan, M.Sc., selaku pembimbing pada penyelesaian skripsi ini yang telah memberikan panduan dan penuh kepercayaan kepada saya untuk menyempurnakan skripsi ini. Panduan ringkas, padat dan profesional telah diberikan kepada saya agar penulis dapat menyelesaikan tugas ini. Ucapan terima kasih juga ditujukan kepada Ketua dan Sekretaris Departemen Dr. Saib Suwilo, M.Sc. dan Bapak Drs. Henri Rani Sitepu, M.Si., Dekan dan Pembantu Dekan Fakultas Matematika dan Ilmu Pengetahuan Alam Universitas Sumatera Utara, semua dosen pada Departemen Matematika FMIPA USU, pegawai di FMIPA USU, dan rekan-rekan kuliah. Akhirnya, tidak terlupakan kepada bapak, ibu dan semua ahli keluarga yang selama ini memberikan bantuan dan dorongan yang diperlukan. Semoga Tuhan Yang Maha Esa membalasnya.
ABSTRAK
Pemampatan data bertujuan untuk mengurangi ukuran file sebelum menyimpan atau memindahkan data ke dalam media penyimpanan. Huffman dan Shannon-Fano adalah dua algoritma yang digunakan untuk proses pemampatan pada tugas akhir ini. Pemampatan data dengan ke dua algoritma tersebut digunakan pada pemampatan file teks. Pada dasarnya ke dua algoritma ini mempunyai cara kerja yang sama. Dimulai dengan pengurutan karakter berdasarkan frekuensinya, pembentukan pohon biner dan diakhiri dengan pembentukan kode. Pada algoritma Huffman, pohon biner dibentuk dari daun hingga akar dan disebut dengan pembentukan pohon dari bawah ke atas. Sebaliknya, pada Shannon-Fano pohon biner dibentuk dari akar hingga daun dan disebut dengan pembentukan pohon dari atas ke bawah. Pada tugas akhir ini dibuat perangkat lunak yang menggunakan bahasa pemrograman Visual Basic 6.0 untuk membandingkan ke dua algoritma pemampatan tersebut. Perbandingan dilakukan dalam hal rasio pemampatan dan kecepatan proses file teks hasil pemampatan. File teks yang diuji adalah 16 tipe file teks dengan berbagai ukuran. Disimpulkan bahwa, secara rata-rata algoritma Huffman menghasilkan rasio file hasil pemampatan yang terbaik (61,3%) dari pada algoritma Shannon-Fano (76,9%). Akan tetapi, algoritma Shannon-Fano membutuhkan waktu pemampatan yang tersingkat (kecepatan pemampatannya 157,7 KByte/s) dari pada algoritma Huffman (kecepatan pemampatannya 154,8 KByte/s). Terdapat beberapa file teks yang tidak tepat untuk dimampatkan dengan algoritma Shannon-Fano karena dapat menghasilkan file hasil pemampatan yang berukuran lebih besar.
STUDY OF COMPARISON OF HUFFMAN AND SHANNON-FANO ALGORITHMS IN COMPRESSION OF TEXT FILE
ABSTRACT
The aim of data compression is to reduce the file size before storing or transferring it in media storage. Huffman and Shannon-Fano are two algorithms used to data compression process in this paper. Data compression with these algorithms is used to compression of text file. Basically, these algorithms have the same way. Starting from sorting the character of a source which associates with its frequency, then build a binary tree and deriving the binary code from the binary tree. At Huffman algorithm, a binary tree is builded from the leaves up to the root and called bottom-up approach. On the contrary, in Shannon-Fano algorithm, a binary tree is builded from the root down to the leaves and called top-down approach. These algorithms are implemented by using Visual Basic 6.0 to compare the compression algorithms. The comparison is used in the case of ratio of compression and compression speed the text file of result of compression. The text file is tested upon 16 type of text file by various sizes. It can be concluded that in the Huffman algorithm yield the best file ratio compression (61,3%) than Shannon-Fano algorithm (76,9%). However, Shannon-Fano algorithm requires the brief compression time (its compression speed 157,7 KBytes/s) than Huffman algorithm (its compression speed is 154,8 KBytes/s). There are several text files that are not suitable to be compressed by Shannon-Fano algorithm, because the compressed file becomes bigger in size.
DAFTAR ISI
Halaman Persetujuan Pernyataan Penghargaan Abstrak Abstract Daftar Isi Daftar Tabel Daftar Gambar
ii iii iv v vi vii ix x
Bab 1 Pendahuluan 1.1 Latar Belakang 1.2 Perumusan Masalah 1.3 Pembatasan Masalah 1.4 Tujuan Penelitian 1.5 Kontribusi Penelitian 1.6 Metode Penelitian 1.7 Tinjauan Pustaka 1.8 Diagram Konsepsi
1 1 3 3 3 4 4 4 7
Bab 2 Landasan Teori 2.1 Pengertian File Teks 2.1.1 Format Teks 2.1.2 Tipe Teks 2.2 Pohon (Tree) 2.3 Pohon Biner (Binary Tree) 2.4 Pemampatan Data 2.4.1 Pengertian Pemampatan Data 2.4.2 Metode Pemampatan 2.5 Algoritma Huffman 2.5.1 Kode Prefix (Prefix Code) 2.5.2 Algoritma Huffman 2.6 Algoritma Shannon-Fano 2.6.1 Algoritma Shannon-Fano
8 8 9 10 11 11 12 13 14 15 16 16 21 22
Bab 3 Pembahasan 3.1 Analisis Algoritma 3.2 Karakteristik Algoritma Huffman dan Shannon-Fano 3.3 Implementasi Pemampatan File Teks 3.3.1 Pemampatan File Teks dengan Algoritma Huffman 3.3.2 Pemampatan File Teks dengan Algoritma Shannon-Fano
3.4 Analisis Kebutuhan Perangkat Lunak 3.4.1 Perancangan Perangkat Lunak 3.4.2 Perancangan Flowchart 3.4.3 Halaman Utama 3.4.4 Halaman Hasil 3.4.5 Implementasi Prosedural 3.5 Hasil Analisis 3.5.1 Analisis Ukuran File 3.5.2 Analisis Kecepatan Proses
26 26 27 28 29 32
35 35 36 36 37 41 46 47 49
Bab 4 Kesimpulan dan Saran 4.1 Kesimpulan 4.2 Saran
51 51 51
Daftar Pustaka
52
Lampiran
DAFTAR TABEL
Halaman Tabel 2.1 Frekuensi Kemunculan Karakter yang telah Diurutkan Tabel 2.2 Tabel Kode Huffman untuk Masing-masing Karakter Tabel 2.3 Frekuensi Kemunculan Karakter yang telah Diurutkan Tabel 2.4 Tabel Kode Shannon-Fano untuk Masing-masing Karakter Tabel 3.1 Karakter yang telah Diurutkan Berdasarkan Frekuensinya Tabel 3.2 Kode Huffman yang telah Terbentuk Tabel 3.3 Karakter yang telah Diurutkan Berdasarkan Frekuensinya Tabel 3.4 Kode Shannon-Fano yang telah Terbentuk Tabel 3.5 Pemampatan Beberapa Tipe File Teks dengan Algoritma Huffman dan Algoritma Shannon-Fano Tabel 3.6 Waktu yang Digunakan (time spent) untuk Memampatkan Beberapa Tipe File Teks dengan Algoritma Huffman dan Shannon-Fano
18 20 23 24 29 31 32 34 47 49
DAFTAR GAMBAR
Halaman Gambar 1.1 Diagram Konsepsi Gambar 2.1 Karakter ASCII Gambar 2.2 Pohon Berakar dengan v1 Sebagai Akar Gambar 2.3 Pohon Biner Gambar 2.4 Pembentukan Pohon Huffman Gambar 2.5 Pembentukan Pohon Shannon-Fano Gambar 3.1 Pohon Huffman yang telah Terbentuk Gambar 3.2 Pohon Shannon-Fano yang telah Terbentuk Gambar 3.3 Flowchart Aplikasi Pemampatan File Teks Gambar 3.4 Tampilan Halaman Utama Gambar 3.5 Pemampatan File Teks dengan Algoritma Huffman Gambar 3.6 Penirmampatan File Teks dengan Algoritma Huffman Gambar 3.7 Pemampatan File Teks dengan Algoritma Shannon-Fano Gambar 3.8 Penirmampatan File Teks dengan Algoritma Shannon-Fano Gambar 3.9 File Teks yang akan Dimampatkan (Compression) Gambar 3.10 File Teks yang telah Dinirmampatkan (Decompression) Gambar 3.11 Grafik Perbandingan Rasio Pemampatan File Teks Gambar 3.12 Grafik Perbandingan Kecepatan Pemampatan File Teks
7 9 11 12 20 24 30 33 36 37 38 38 39 39 40 40 47 49
