STUDI PERBANDINGAN ALGORITMA HUFFMAN DAN LZW (LEMPEL ZIV WELCH) PADA PEMAMPATAN FILE TEKS
SKRIPSI
Diajukan untuk melengkapi tugas akhir dan memenuhi syarat mencapai gelar Sarjana Komputer
CANGGIH PRAMILO 041401010
PROGRAM STUDI S1 ILMU KOMPUTER DEPARTEMEN ILMU KOMPUTER FAKULTAS MATEMATIKA DAN ILMU PENGETAHUAN ALAM UNIVERSITAS SUMATERA UTARA MEDAN 2008
Universitas Sumatera Utara
Medan, 24 November 2008
LEMBAR PENGESAHAN
STUDI PERBANDINGAN ALGORITMA HUFFMAN DAN LZW ( LEMPEL ZIV WELCH ) PADA PEMAMPATAN FILE TEKS
Oleh
Canggih Pramilo NIM. 041401010
Telah diperiksa dan disetujui untuk diseminarkan oleh :
Dosen Pembimbing I
Dosen Pembimbing II
Syahriol Sitorus, S.Si, MIT
Drs. Agus Salim Harahap, M.Si
NIP. 132 174 687
NIP. 130 936 279
Universitas Sumatera Utara
PERSETUJUAN
Judul
Kategori Nama Nomor Induk Mahasiswa Program Studi Departemen Fakultas
: STUDI PERBANDINGAN ALGORITMA HUFFMAN DAN LZW PADA PEMAMPATAN FILE TEKS : SKRIPSI : CANGGIH PRAMILO : 041401010 : SARJANA (S1) ILMU KOMPUTER : ILMU KOMPUTER : MATEMATIKA DAN ILMU PENGETAHUAN ALAM (FMIPA) UNIVERSITAS SUMATERA UTARA
Diluluskan di Medan, Desember 2008 Komisi Pembimbing
:
Pembimbing 2
Pembimbing 1
Drs. Agus Salim Harahap, M.Si NIP. 130 936 279
Syahriol Sitorus, S.Si, MIT NIP. 132 174 687
Diketahui/Disetujui oleh Prog. Studi Ilmu Komputer S-1 Ketua,
Prof. Dr. Muhammad Zarlis NIP. 131 570 434
Universitas Sumatera Utara
PENGHARGAAN
Syukur alhamdulillah penulis nyatakan kehadirat ALLAH SWT Yang Maha Pengasih 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.Agus Salim Harahap, M.Si., selaku pembimbing pada penyelesaian skripsi ini yang telah memberikan panduan dan penuh kepercayaan kepada saya untuk menyempurnakan skripsi ini. Panduan ringkas, padat dan profesional yang telah diberikan kepada saya agar penulis dapatmenyelesaikan tugas ini. Ucapan terima kasih juga ditujukan kepada Ketua dan Sekretaris Departemen Prof.Dr.Muhammad Zarlis dan Bapak Syahriol Sitorus, S.Si, M.IT., Dekan dan Pembantu Dekan Fakultas Matematika dan Ilmu Pengetahuan Alam Universitas Sumatera Utara, semua dosen pada Departemen Ilmu Komputer FMIPA USU, pegawai di Ilmu Komputer USU, dan rekanrekan 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.
Universitas Sumatera Utara
PERNYATAAN
STUDI PERBANDINGAN ALGORITMA HUFFMAN DAN LZW (LEMPEL ZIV WELCH) PADA 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, Desember 2008
CANGGIH PRAMILO 041401010
Universitas Sumatera Utara
STUDY OF COMPARISON OF HUFFMAN AND LZW ALGORITHM 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 an LZW are two algorithm used to data compression process in this paper. These algorithms are implemented by using Visual C++ 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 than LZW algorithm. However, Huffman algorithm requires the brief compression time than LZW algorithm. There are several text files that are not suitable to be compressed by LZW algorithm, because the compressed file becomes same or bigger in size.
Universitas Sumatera Utara
ABSTRAK
Pemampatan data bertujuan untuk mengurangi ukuran file sebelum menyimpan atau memindahkan data ke dalam media penyimpanan. Huffman dan LZW adalah dua algoritma yang digunakan untuk proses pemampatan pada tugas akhir ini. Pada tugas akhir ini dibuat perangkat lunak yang menggunakan bahasa pemrograman Visual C++ 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 daripada algoritma LZW. Dan juga, secara rata-rata algoritma Huffman membutuhkan waktu pemampatan yang tersingkat daripada algoritma LZW. Terdapat beberapa file teks yang tidak tepat untuk dimampatkan dengan algoritma LZW karena dapat menghasilkan file hasil pemampatan yang berukuran sama atau lebih besar dari ukuran file sumber.
Universitas Sumatera Utara
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 Batasan Masalah 1.4 Tujuan Penelitian 1.5 Manfaat Penelitian 1.6 Metodologi Penelitian 1.7 Sistematika Penulisan
1 1 2 2 3 3 3 4
Bab 2 Landasan Teori 2.1 Pengertian File Teks 2.1.1 Tipe Teks 2.1.2 Format Teks 2.2 Pohon (Tree) 2.3 Pohon Biner (Binary Tree) 2.4 Pengertian Pemampatan Data 2.5 Metode Pemampatan 2.6 Algoritma Huffman 2.6.1 Kode Prefix (Prefix Code) 2.6.2 Kode Huffman 2.7 Algoritma LZW 2.7.1 Kode LZW ( Lempel-Ziv-Welch )
6 6 7 7 8 9 10 11 12 13 14 20 20
Bab 3 Analisis dan Perancangan Sistem 3.1 Analisis Algoritma 3.2 Karakteristik Algoritma Huffman dan LZW (Lempel Ziv Welch) 3.3 Analisis Pemampatan File Teks 3.3.1 Pemampatan File Teks dengan Algoritma Huffman 3.3.2 Pemampatan File Teks dengan Algoritma LZW 3.3.3 Penirmampatan File Teks dengan Algoritma Huffman 3.3.4 Penirmampatan File Teks dengan Algoritma LZW
24 24 25 26 26 31 32 33
Universitas Sumatera Utara
3.4 Analisis Fungsional Sistem 3.4.1 DFD Level 0 ( Context Diagram ) 3.4.2 DFD Level 1 3.4.3 DFD Level 2 Untuk Proses Encoding (Pemampatan) 3.4.4 DFD Level 2 Untuk Proses Decoding (Penirmampatan)
34 34 35 36 38
Bab 4 Implementasi dan Pengujian 4.1 Lingkungan Implementasi 4.2 Perangkat Keras yang Digunakan 4.3 Perangkat Lunak yang Digunakan 4.4 Implementasi Antar Muka 4.5 Pengujian Sistem Kompresi Teks Sederhana 4.5.1 Analisis Ukuran File 4.5.2 Analisis Kecepatan Proses
39 39 39 39 40 44 45 51
Bab 5 Penutup 5.1 Kesimpulan 5.2 Saran
60 60 61
Daftar Pustaka
62
Lampiran A: Pembentukan Pohon Huffman Lampiran B: Perbandingan Teks dengan Kamus Lampiran C: Kode LZW yang Dicocokkan dengan Kamus Lampiran D: Kode Program
63 71 79 84
Universitas Sumatera Utara
DAFTAR TABEL
Halaman Tabel 2.1 Frekuensi Kemunculan Karakter yang Telah Diurutkan 16 Tabel 2.2 Tabel Kode Huffman untuk Masing-Masing Karakter 19 Tabel 2.3 Proses Pemampatan LZW 22 Tabel 2.4 Proses Penirmampatan LZW 23 Tabel 3.1 Karakter yang telah Diurutkan Berdasarkan Frekuensinya 27 Tabel 3.2 Kode Huffman yang telah Terbentuk 29 Tabel 4.1 Hasil Pengujian Sistem 45 Tabel 4.2 Rasio Pemampatan 16 File (*.txt) dengan Algoritma Huffman dan LZW 46 Tabel 4.3 Rasio Pemampatan 16 File (*.doc) dengan Algoritma Huffman dan LZW 47 Tabel 4.4 Rasio Pemampatan 16 File (*.htm) dengan Algoritma Huffman dan LZW48 Tabel 4.5 Rasio Pemampatan 16 File (*.rtf) dengan Algoritma Huffman dan LZW 49 Tabel 4.6 Kecepatan Proses Pemampatan 16 File (*.txt) dengan Algoritma Huffman dan LZW 51 Tabel 4.7 Kecepatan Proses Pemampatan 16 File (*.doc) dengan Algoritma Huffman dan LZW 53 Tabel 4.8 Kecepatan Proses Pemampatan 16 File (*.htm) dengan Algoritma Huffman dan LZW 55 Tabel 4.9 Kecepatan Proses Pemampatan 16 File (*.rtf) dengan Algoritma Huffman dan LZW 57
Universitas Sumatera Utara
DAFTAR GAMBAR
Halaman Gambar 2.1 Pohon Berakar dengan v1 Sebagai Akar Gambar 2.2 Pohon Biner Gambar 2.3 Pembentukan Pohon Huffman Gambar 3.1 Pohon Huffman yang telah Terbentuk Gambar 3.2 Diagram Level 0 Gambar 3.3 Diagram Level 1 Gambar 3.4 Diagram Level 2 untuk Proses Encoding (Pemampatan) Gambar 3.5 Diagram Level 2 untuk Proses Decoding (Penirmampatan) Gambar 4.1 Tampilan Halaman Utama Gambar 4.2 File Teks yang akan Dimampatkan ( Compression ) Gambar 4.3 Pemampatan File Teks dengan Algoritma Huffman Gambar 4.4 Penirmampatan File Teks dengan Algoritma Huffman Gambar 4.5 Pemampatan File Teks dengan Algoritma LZW Gambar 4.6 Penirmampatan File Teks dengan Algoritma LZW Gambar 4.7 Grafik Rasio Pemampatan File (*.txt) Gambar 4.8 Grafik Rasio Pemampatan File (*.doc) Gambar 4.9 Grafik Rasio Pemampatan File (*.htm) Gambar 4.10 Grafik Rasio Pemampatan File (*.rtf) Gambar 4.11 Grafik Perbandingan Rasio Pemampatan Gambar 4.12 Grafik Kecepatan Pemampatan File (*.txt) Gambar 4.13 Grafik Kecepatan Pemampatan File (*.doc) Gambar 4.14 Grafik Kecepatan Pemampatan File (*.htm) Gambar 4.15 Grafik Kecepatan Pemampatan File (*.rtf) Gambar 4.16 Grafik Perbandingan Kecepatan Pemampatan
9 9 18 28 34 35 36 38 40 41 42 42 43 43 46 47 48 49 50 52 54 56 58 59
Universitas Sumatera Utara
