Edisi Khusus, Nopember 2004
Terakreditasioleh Dirjen Dikti Depdiknas
No. 52/Dikti/Kep/2002
Sistem Informasi Geografis Daerah Penangkapan Ikan di Perairan Natuna-Laut Cina Selatan Berbasis Data Satelit NOAAlAVHRR dan SEAWIFS . YusSholva
Perbandingan Model Two-Tier dengan Three-Tier dalamArsitektur ClientlServer·untuk Mengolah Perintah Query pada Aplikasi Database Wahyu Pujiyono, M, Idham Ananta Timur, Savitri
Teknologi Informasi Keruangan: Pengalarrian Penerapan di Lingkungan . Pemerintahan Kota di Indonesia Agus Prijadi Saido
Kompresi Data Menggunakan Algoritma Huffman Julio Adisantoso, Danny Dimas Sulistio, Bib Paruhum Silalahi
Memilih Vendor Pengembang Sistem Informasi Manajemen Menggunakan Metode Analytic Hierarchy Process: Kasus Pengembangan Sistem Informasi Akademik STIE Indonesia Agus Hidayat, Gatot Prabantoro
Pengkayaan UML dengan Metode Formal Pujianto Yugopuspito
Technology Acceptance Model untuk Memprediksi Adopsi Internet di Indonesia Fathul Wahid
Sistem Fuzzy Berorientasi Objek Teduh Dirgahayu
ISSN 0853-8697
111111111111111111111111 770853 869710
' : Ed" Kh 1ieknom : 151 usus
HI 1 84! m. !
Yogyakarta
No ember 2004,
;
ISSN: _
TEKNOIN Jurnal Teknologi Industri
Terakreditasi oleh Dirjen Dikti Depdiknas No. 52/Dikti/Kep/2002 Jurnal Teknologi lndustri TEKNOIN adalah jurnal yang mengkaji masalah yang berhubungan dengan teknologi industri. Penelitian yang dilaporkan dapat berupa penelitian untuk pengembangan keilmuan atau terapan . . Jurnal ini terbit ernpat kali dalam setahun, setiapbulan Maret, [uni, September, clan Desember,
Pelindung Bachrun
Sutrisno
Pemimpin Umum Hari Purnomo Pemimpin Redaksi Agus Taufiq Sekretaris Redaksi Fathul Wahid . Dwi Ana Ratna Wati Dewan Redaksi Adhi Susanto Adi Djoko Guritno Ahmad Zuhdan Fathoni Ali Parkhan Asmanto Subagyo Benny Sutrisno Gumbolo Hadi Susanto Indah Molektuz Zuchairah Ira Promasanti Rachmadewi Jamasri Paryana Puspaputra R. Chairul Saleh Soedjatmiko Sri Hartati Sri Kusumadewi Subanar
Fakultas
Alamat Redaksi Teknologi Industri Universitas Islam Indonesia JI. Kaliurang Km. 14 Yogyakarta 55501 Telp. (0274) 895287, Faks. (0274) 895007 E-mail:
[email protected]
Edisi Khusus, Nopember 2004
TEI{NOIN Jumal T ekrologl
Industri
ISSN0853-8697
DAFTARISI 1-14
Yus Sholva Sistem Informasi Geografis Daerah Penangkapan Ikan di Perairan Natuna-Laut Cina Selatan Berbasis Data Satelit NOAA/ AVHRR dan SEAWIFS
15-22
Wahyu PujiyoIlo, M. Idham Ananta Timur, Savitri Perbandingan
Model Two-Tier dengan Three-Tier dalam
Arsitektur Client/Server Aplikasi Database 23-31
untuk Mengolah Perintah Query pada
Agus Prijadi Saido Teknologi Informasi Keruangan: Pengalaman Lingkungan Pemerintahan Kota di Indonesia
Penerapan
33-41
Julio Adisantoso, Danny Dimas Sulistio, Bib Paruhum Kompresi Data Menggunakan Algoritma Huffman
43-53
Agus Hrd ayat, Gatot Prabantoto
di Silalahi
Memilih Vendor Pengembang Sistem Informasi Manajemen Menggunakan Metode Analytic Hierarchy Process: Kasus Pengernbangan Sistem Informasi Akademik STIE Indonesia 55-66
Pujianto Ytigopuspito Pengkayaan UML dengan Metode Formal
67-77
Fathul Wahid Technology Acceptance Model untuk Memprediksi Internet di Indonesia
79-84
Adopsi
Teduh Dirgahayu Sistem Fuzzy Berorientasi Objek ~<' .
Redaksi menerima tulisan yang belum pemah diierbitkan dari kalangan akademisi dan peneliti. Redaksi berhak menguban iuiisan tanpa mengurangi atau mengubah maksudnsja. Pedoman penulisan. iercantum pada oagian akhir Jurnal ini. Tallggullgjmuab isi tuiisan ada pada penulis scpenulinva. Untuk ntembantu kontinuiias pcnerbitan, sctiap tulisan yang ditnuat dikenakan biaya sebesar Rp 150.000 dan dapat dikirintkan ke rekellillg nomor 10040012324 Ballk Bukopin Caballg Petnbantu
[alan Kaliurang
Yogyakarta alas llama lr. Aglls Taufiq, M.Sc.
+ DARI REDAKSI TEKNOIN edisi k.husus ini memuat enam artikel terbaik dari Seminar Nasional Aplikasi Teknologi lnformasi (SNATI) 2004. SNATI 2004 diselenggarakan oleh Jurusan Teknik Informatika, Fakultas Teknologi Industri Universitas Islam Indonesia pada 19 [uni 2004 di Yogyakarta. Artikel-artikel tersebut membahas berbagai penerapan teknologi informasi dalam bidang yang sangat beragam. Artikel pertama yang ditulis oleh Sholva membahas pengembangan Sistem Informasi Geografis untuk membantu menentukan zona perikanan yang paling potensial di Perairan Natuna-Laut Cina Selatan menggunakan data satelit NOAA/ AVHRR dan SEAWIFS. Artikel selanjutnya yang ditulis oleh Pujiyono et al. meIaporkan penelitian yang membandingkan dua arsitektur client-server, yaitu model2-tier dan 3-tier untuk mengolah perintah query. Saido dalam artikelnya yang membahas salah satu aplikasi teknologi informasi dalam pemerintahan, yaitu untuk masalah keruangan. Pengalaman penerapannya di lingkungan beberapa pemerintahan kota diIndonesia membuat artikel uu semakin menarik. Artikel selanjutnya yang ditulis oleh Adisantoso et al. mernbahas kompresi data menggunakan algoritma Huffman. Selanjutnya, Hidayat dan Prabantoro dalam artikelnya menjelaskan contoh penerapan metode pengambilan keputusan Analytic Hierarchy Process pada sebuah ranah masalah yang sering dihadapi oleh para pengambil keputusan di bidang teknologi inforrnasi, yaitu menentukan pengembang sistem informasi manajernen. Artikel terakhir dari SNATI merribahas pengkayaan UML derigan metode formal yang ditulis oleh Yugopuspito. Selain enam artikel tersebut, TEKNOIN edisi khusus ini juga memuat dua artikel menarik yang ditulis masing-masingoleh Wahi<:Iqan Dirgahayu. Artikel Wahid membahas model penerimaan teknologi (technologtj acceptance mode0 untuk memprediksi adopsi Internet, sedang artikel Dirgahayu membahas penerapan metode berorientasi obyek pada sistem fuzzy. Kami telah dan akan semakin meneguhkan komitmen untuk menjadi salah satu media ilmiah penyebaran pengetahuan yang terkait dengan teknologi industri. Karenanya, kami men gun dang pada praktisi dan akademisi untuk memberikan kontribusinya dalam bentuk artikel bermutu.
Redaksi
ISSN 0853-8697
KOMPRESI DATA MENGGUNAKAN ALGORITMA HUFFMAN Julio Adisantoso, Danny Dimas SuHstio, Bib Paruhurn Silalahi
Departemen Ilmu Kompuier Institut Pertanian Bogor Kampus IPB Baranangsiang, [alan Raya Pajajaran Bogar Telp.jFaks. (0251) 356653 E-mail:
[email protected] ABSTRACT
Text compression algorithms are normally defined in terms of a source alphabet of 8bit ASCII codes. HJ1ffman algorithm is the most popular methods of text compression. This research used static and adaptif Huffman algorithms to compress text data, and also compare it. Variation of character occurs will decrease compression ratio. Iteration time of static Huffman algorithm for compress and decompress is faster than adapiif Huffman algorithm, but performance of adaptij Huffman algorithm is best. Keywords: text compression, static, and adaptif huffman algorithm. 1.·
PENDAHULUAN· Pad a saat ini kebutuhan akan informasi sangatlah diperlukan oleh masyarakat umum. Dengan semakin banyaknya informasi yang perIu disimpan secara digital, secara automatis akan meningkatkan keperluan untuk menyediakan . media penyimparian data yang Iebih besar lagi. Oleh karenaitu diperIukan suatu alternatif mekanisme penyimpanan data sehingga dengan media penyimpanan yang ada, kita dapat menyimpan data sebanyak-banyaknya. Pemampatan atau kompresi data merupakan salah satu metode untuk memperkecil ruang penyimpanan data pada suatu media penyimpanan, Selain berguna dalam penyimpanan data, kompresi data dapat membantu memperkecil ukuran data yang drtransmisikan di dalam suatu media jaringan, seperti internet sehingga memperkedl waktu transfer data. Salah satu metode kompresi data yang telah banyak dikenal ialah dengan menggunakan metode Huffman. Algoritma Huffman merupakan salah satu pelopor lahirnya kompresi data, sehingga ukuran data yang perIu disimpan menjadi lebih kecil dibandingkan dengan ukuran data sebenarnya . .Penelitian mengenai kompresi terhadap data teks menggunakan algoritma Huffman telah dilakukan sebelumnya oleh Hutasoit [3] mengenai pengaruh ngram dalam pembentukan kode Huffman pada file teks berbahasa Indonesia dan Layungsari [4] mengenai implementasi kompresi multi tahap menggunakan algoritma Huffman pada file teks. Kesimpulan dari Hutasoit [3] adalah pengaruh n-gram dapat menghasilkan rasio kompresi yang lebih baik yang ditunjukan dengan rasio kompresi untuk tree yang monogram lebih kecil dibandingkan dengan tree digram. Sedangkan Layungsari [4] menyimpulkan bahwa hasil kompresi file teks menggunakan kompresi multi tahap Huffman menunjukan hasil
33
yang tidak memuaskan. Hal ini dikarenakan file hasil kompresi oleh kompresi tahap pertama telah menghasilkan kode prefiks yang optimal. . Penelitian yang menelaah tentang pengembangan algoritma Huffman itu sendiri belum banyak dilakukan. Hal ini diperlukan agar semakin sempurna metode kompresi data yang dilakukan. Salah satu pengembangan algoritma Huffman statik adalah algoritma adaptif. Oleh karena itu penelitian ini bertujuan untuk menelaah algoritma Huffman adaptif dibanding dengan algoritma Huffman statik pad a mekanisme kompresi data berbasis teks. 2.
LANDASAN
Kompresi
TEORI data dapat
teori informasi dim ana memperkecil ukuran data yang akan ditransmisikan [5]. Secara sederhana, karakteristik dari kompresi data dapat dianalogikan sebagai sebuah proses untuk mengubah sebuah string yang merupakan kumpulan karakter menjadi sebuah string yang baru dengan informasi yang sarna namun dengan lebar atau ukuran yang lebih kecil, Suatu cara untuk mengembalikan data yang telah terkompresi menjadi seperti sedia kala dikenal dengan istilah dekompresi data. Secara garis besar kompresi data dapat dikelompokkan ke dalam dua metode yaitu metode kompresi lossy dan metode kompresi lossless. Metode kompresi lossy adalah suatu metode kompresi data dim ana data yang telah terkompresi apabila dikembalikan ke dalam benruk semula akan terdapat beberapa inforrnasi yang hilang. Contoh dari metode ini adalah pemampatan data gambar d an suara. Sedangkan metode kompresi loss less merupakan suatu metode kornpresi data dimana data yang telah terkompresi .akan dapat dikembalikan seperti sernula tanpaada informasi yang hilang. Implementasi dari metode ini yaitu pada pemampatan data teks atau dokumen ASCII.
tujuan
utamanya
adalah
dilihat untuk
sebagai kumpulan
2.1
Model Kompresi Data Pad a metode kompresi lossless terdapat dua buah model utama yaitu metode loss less dengan menggunakan model statistik dan model kamus, Pada model statistik, kompresi data diawali dengan melakukan perhitungan setiap karakter yang ada di dalam file, kemudian dengan statistik karakter yang ada akan dilakukan pengkodean karakter dengan representasi lain. Representasi tersebut apabila dibandingkan dengan karakter asli diharapkan akan lebih kecil ukurannya. Model ini digunakan pada algoritma Huffman dan algoritma Aritmatik Sedangkan untuk model kamus, kompresi data diawali dengan melakukan perhitungan setiap string yang terdapat di dalam file. String-string terse but akan disusun seperti sebuah indeks dan string-string tersebut akan disimbolkan dengan sebuah representasi yang unik, Model ini digunakan pada algoritma Lempel-Ziv dan turunannya (LZW, LZSS, LZRW, dan sebagainya). Pada setiap model kompresi, dilakukan proses konversi simbol dari representasi string menjadi representasi kode lain, dan sebaliknya. Ada dua alat konversi dalam hal ini, yaitu mesin enkoder dan mesin dekoder. Mesin enkoder merupakan sebuah alat yang menjalankan suatu mekanisme untuk melakukan
34
Adisantoso
et al. - Kompresi Data Menggunakan
Algoritma
Huffman
konversi simbol dari suatu representasistring menjadi suatu representasi kode lainnya yang bersifat unik. Mekanism.e yang dilakukan oleh alat ini sering dikenal dengan istilah pengkodean (encoding). Sedangkan mesin dekoder merupakan sebuah alat yang menjalankan suatu mekanisme untuk mengembalikan representasi unik dari suatu string menjadi sebuah representasi string seperti sedia kala. Mekanisme yang dilakukan oleh alat ini sering dikenal dengan :istilah pendekodean (decoding). 2.2
AIgoritma Huffman AIgoritma Huffman diperkenalkan oleh D.A. Huffman pad a paper yang ia tulis sebagai salah satu tugas kuliahnya di MIT pada tahun 1950 [2]. Algoritm.a ini merupakan pengembangan lebih lanjut dari algoritma_kompresi yangdilakukan oleh Claude Shannon dan R.M. Fano pada tahun yang sarna. Ide dasar dari algoritma ini adalah membuat kode dengan representasi bit yang lebih pendek untuk karakter ASCII yang sering muncul didalam file dan mernbuat kode dengan representasi bit yang lebih panjang untuk karakter ASCII yang jarang muneul didalam file. Di dalam perkembangannya algoritma Huffman terpeeah menjadi dua buah kategori yaitu statik dan adaptif. Algoritma Huffman Statik _ _ Algoritma Huffman Statik menggunakan kemungkinan kemuneulan dari setiap karakter yang telah ditetapkan pada awal pengkodean dan kemungkinan kernunculan karakter tersebut juga dapat diketahui baik oleh enkoder maupun dekoder. Cara kerja dari algoritma Huffman Statik untuk mengkompresi data yaitu dengan cara sebagai berikut: a. Hitung jumlah karakter yang muncul di dalam file, sehingga masing-masing karakter yang ada akan memiliki bobot sesuai dengan banyaknya karakter tersebut didalam file. Kemudian susunlah suatu pohon bineryang dibangun berdasarkan bobot karakter yang ada. Inti dari pem.bangunan pohon biner adalah menggabungkan dua buah karakter dengan tingkat kemunculan (bobot) yang lebih kecil, kemudian membangkitkan satu buah node parent yang memiliki bobot gabungan dari kedua kara kter tersebut. b. Lakukan pengkodean (encoding) karakter yang ada didalam file menjadi suatu representasi bit sesuai dengan urutan pada pohon biner yang telah dibangun. 2.2.1
2.2.2 Algoritma Huffman Adaptif AIgoritma Huffman Adaptif adalah algoritma dengan kemungkinan kemunculan dari setiap simbol tidak dapat ditentukan dengan pasti selama pengkodean. Hal ini disebabkan oleh perubahan pengkodean secara dinamis berdasarkan frekuensi dari sim.bolyang telah diolah sebelum.nya. Algoritrna Huffman Adaptif merupakan pengembangan lebih lanjut dari algoritma Huffman. Ide dasar dari algoritma ini adalah meringkas tahapan algoritrna Huffman tanpa perlu menghitung jurnlah karakter keseluruhan dalam membangun pohon biner. Algoritma ini dikembangkan oleh trio Faller, Gallager, dan Knuth dan kemudian dikembangkan lebih lanjut oleh Vitter, sehingga tercipta TEKNOIN,
Edisi Khusus, Nopember 2004, 33-41
35
dua buah algorima Huffman adaptif yaitu algoritma FGK dan algoritma V. Secara umum algoritma Huffman Adaptif adalah sebagai berikut: a. Pada mesin enkoder: initialize dol
model(); -
c=getc(input); encode (e,output): update model (e); )while (e!=eof);
b.
Pada mesin dekoder: initialize model(); while((c=decode(input» I
!=eof);
putc(c/output); update_model(c);
3.
METODE PENELITIAN Secara umum kompresi data menggunakan algoritma Huffman statik diawali denganmembacadahulu file teks yang akan dikompresi. Hal ini dilakukan untuk mendapatkan informasi mengenai jumlah dari masing-masing karakter yang terdapat d id a larn file. Setelah itu kita ~kan rnernbarigtm sebuah pohon biner' yang dibangun dengan kriteria yang telah dijelaskan sebelumnya. Kernudian kita akan mengubah representasi dari masing-masing karakter yang ada di daiam file sesuai dengan representasi yang dihasilkan oleh pohon biner yang dituliskan pada file baru. Proses penulisah pada file hasil kompresi diawali dengan penulisan pohon biner yang kern ud ian d isarnburig deiigan isi file yang tela h dikodekan. Untuk dekompresi data, yang pertama kali dilakukan adalah membangun pohon Huffman yang merepresentasikan statistik data. Kemudian dilakukan pembacaan setiap bit sampai ditemukan node leaf yang sesuai. Hal ini dilakukan terus menerus sampai bit terakhir. Sedangkan proses kompresi data dengan menggunakan algoritma Huffman Adaptif diawali dengan membentuk sebuah pohon biner yang berisi sebuah node NYT dengan bobot nol. Kemudian dilakukan pembacaan file sumber setiap karakter. Apabila ditemui sebuah karakter yang belum didefinisikan didalarn pohon biner, maka kode NYT akan dituliskan kedalam file baru disambung dengan kode ASCII dari karakter barn tersebut. Setelah itu akan dibuatkan sebuah node yang berisi informasi tentang karakter baru dengan bobot satu dan kemudian pohon biner dimodifikasi ulang. Setelah itu dibaca karakter selanjutnya sampai . akhir file. Pada saat dibaca karakter yang telah didefinisikan pad a pohon, rnaka bobot karakter tersebut ditambah satu, kernudianpohon akan dirnocliffkast ulang. Modifikasi dari pohon biner berlangsung selama proses pembacaan karakter. Sehingga pada file baru tidak perlu tambahkan informasi mengenai pohon biner. 3.1
Bahan Penelitian Data yang digunakan adalah data teks dengan berbagai ukuran file, yaitu kurang dari 20.000 byte, 20.000 - 40.000 byte, dan lebih dari 40.000 byte. File teks tersebut berisi potongan tajuk rencana harian sebuah media cetak online (Media 36
Adisanioso
et al. - Kampresi Data MengguniJkan Algaritma Huffman
Indonesia) yang beredar antara bulan [uni sampai November 2003. Selain itu digunakan sebuah mekanisme untuk membangkitkan karakter dengan rentang bervariasi dari satu buah variasi karakter. 3.2
Analisis Data Dalam penelitian ini dilakukan beberapa pengujian yang antara lain: a. Melihat pola rasio pemampatan dan lamanya eksekusi algoritmadengan menggunakan data yang berasal dari potongan artikel. b. Melakukan simulasi dengan menggunakan file teks yang hanya memiliki sebuah variasi karakter kemudian diIihat pola rasio pemampatan dan lamanya eksekusi dalam rentang 1.000 byte, 2.000 byte, 3.000 byte sampai 100.000 byte. c. Mengamati rasio dan lamanya eksekusi algoritma pada file yang memiliki lima buah karakter yang berbeda, dan 256 karakter yang berbeda. d. Penarikan kesimpulan menggunakan uji Analisis Keragaman (ANOV A) Percobaan yang telah dirancang selanjutnya diuji coba dan dilakukan analisis terhadap kinerja algoritma yang dibatasi dengan melihat rasia pemampatan dan waktu proses kompresi. Rasio pemampatan (R) . didefinisikan sebagai:
d imaria f" a da lah ukuran
4.
filea wal, clan fb aclalah
ukuran
file hasil k o m pres i.
HASIL PENELITIAN
4.1
Ukuran File Lama waktu kompresi file berukuran kurang dari 20.000 byte oleh Huffman Statik berkisar antara 0,05 detik sampai 0,06 detik, sedangkan Huffman adaptif memerlukan waktu sekitar 0,11 detik sampai 0,13 detik dengan pola menaik untuk ukuran file yang semakin besar. Rasia kampresi kedua algoritma rnenunjukan nilai yang fluktuatif. Hal ini disebabkan perbedaan banyaknya variasi karakter yang muncul dari kesepuluh file yang digunakan, Pada lamanya dekompresi Huffmanstatik memerlukan waktu antara 0,035 detik sampai 0,04 detik, sedangkan Huffman adaptif memerIukan waktu antara 0,105 detik sampai 0,12 detik. Untuk file berukuran antara 20.000 - 40.000 bytes, lamanya waktu kompresi yang diperIukan oleh Huffman Statile berkisar an tara 0,05 detik sampai 0,06 detik. sedangkan Huffman adaptif memerlukan waktu sekitar 0,11 detik sampai 0,13 detik dengan pola menaik untuk ukuran file yang semakin besar, Rasio kompresi ke dua algoritma meriunjukan nilai yang fluktuatif. Hal ini disebabkan perbedaan banyaknya variasi karakter yang muneul dari kesepuluh file yang digunakan, Pada lamanya dekompresi Huffman statik memerlukan waktu antara 0,035 detik sampai 0,04 detik, sedangkan Huffman adaptif memerlukan waktu antara 0,105 detik sampai 0,12 detik. Sedangkan untuk file berukuran lebih dari 40.000 bytes, hasil kompresi kurang Iebih sarna dengan percobaan sebelumnya yaitu iterasi yang diperlukan
TEKNOIN,
Edisi Khusus, Nopember 2004, 33-41
37
oleh algoritma Huffman adaptif Iebih lamb at dibandingkan algoritma Huffman statik, namun dengan rasio kompresi yang lebih baik. Tabell menunjukkan bahwa waktu iterasi untuk kompresi dan dekompresi Huffman statik lebih cepat dibandingkan waktu iterasi kompresi dan dekompresi Huffman adaptif. Namun rasio pemampatan Huffman adaptif lebih besar dibandingkan rasio pemampatan Huffman Statik. Hal ini menjadikan file kompresi yang dihasilkan oIeh Huffman Adaptif akan Iebih kecil ukurannya dibandingkan dengan file kompresi yang dihasilkan oleh Huffman Statik. Selain itu dapat kita lihat semakin besar ukuran file yang akan dikompresi berimpikasi pada lama iterasi yang semakin lama. Tabell. Rata-rata lama dan rasio kompresi Ukuranfile
Ra5io(%)'
Lamats)
. Huffman Statik
Huffman Adaptif
4.2
._
Kont'!1'esi
<20KB 20s/d 40 KB . >40KB <20KB 20 sid 40 KB > 40 KB
..
-
Dekompresi Lama (5)
Ra5io(%)
0,0564441
42,6445
0,03934281
-74,363
0,0656619 0,0763654 0,1235163 0,2234394 . 0,3226191
43,1081 43,2218. 4:3,3365 43,4659
0,04878656 0,05559875 0;11193219 0,18995875 {),26700437
-75,777
43,4665
-76,13 -
-76,493 . -76,889 -76,893
Variasi Karakter
Tujuan ·dari pereobaan ini adalah untuk mendapatkan rasio dan lamanya waktu eksekusi dari kedua algoritma untuk file yang memiliki karakter deng
Adisantoso et
at - Kompresi Data Menggunakan Algoritma Huffrnan
0.125 0.1 0.075 0.05
1
6
1i
16 21
26
31
36
41
46
51
56
61
File uji
Gambar 1. Lama kompresi kedua algoritma pad a satu karakter
'cIVo ~0.125
.
B
-'"
.
0.1
j.
~ 0075
[
oS
I, ODS!
!
0.025
1
6
11
16 21 26 31 36 41 46 51 56 61 66
71 76 1'---"
___._.~lIe
Gambar 2. Lama dekompresi
1
6
11 16 21
26
31
ujl
.
kedua algoritma pada satu karakter
36
41 46
51 56 61
File uji
Carnbar 3. Rasia kompresi
81 86 91 96
j __HStat.~"W\daPtlti
66 71
76
i'
I-+-_.__L~_.
81 86
H.Statik
91
96
,···0····
_
kedua algorihna pada satu karakter
TEKNOIN, Edisi Khusus, Nopember 2004,33-41
39
Karena tree yang dibentuk pada Huffman Adaptif tidak perlu disimpan, hal ini menjadikan rasio kompresi Huffman Adaptif lebih baik dibandingkan dengan rasio kompresi Huffman Statik. . Pad a percobaan dengan file berisi 256 karakter terjadi pula anomali seperti halnya yang terjadi pada percobaan 5 karakter, Seperti yang dapat dilihat pada Tabel 3, rasio kompresi kedua algorihna ruenu.njukari riila i negatif yang berarti hasil kompresi mengalami pembengkakan ukuran. Tabel2. Kompresi file 5 buah karakter Huffman Statile
Huffman Adaptif
Lama iterasi (detikl Rasio pampati%)
0,01328 -400
Ukuran hasil(byte)
25
Lama iterasi (detik) Rasio pampat (%) Ukuran hasil (byte)
0,008969 -40 7
Tabe13. Kompresi file 256 karakter Hufftnan
I
Statile
Huff!nan Adaetif
L.
I Lama iterasi (detik) . Rasio 2ampat (%) Ukuran hasil (byte} Lama iterasi (detik) Rasio pampat (%) .. Uk uran hasil (byte)
0,025 -304,297 1035 0,011344 -100,781 514
Padaalgoritma Huffrrian Sta tik lebih ' disebabkan karena besarnya tempat yang diperlukan untuk menyimpan statistik karakter. Karena pada percobaan ini digunakan 256 karakter yang berbeda, maka secant otornatis ak.ari diperlukan minimal 512 byte untuk menyimpan informasi karakter. Hal ini belum termasuk penyimpanan header, dan penyimpanan hasil pengkodean file sumber. Sedangkan pada algoritma huffman statik selain menyimpan 256 byte yang merepresentasikan karakter yang berbeda, perlu juga disimpan hasil pengkodean file sumber. SIMPULAN Semakin variatif karakter yang muncul, akan memperkecil r asio korrrprest yang dihasilkan, baik oleh algoritma Huffman Statik, maupun pada algoritma Huffman Adaptif. Rasio kompresi terbaik terjadipada file yang rnernifiki kara kte r dengan peluang kemuncu lan mendekati 1 (bobot karakter hampir sebesar ukuran file). Rasio terbaik yang didapat selama penelitian yaitu sebesar 87,489 %. Rasio kompresi terburuk terjadi pada file yang memiliki variasi karakter besar dan pada file yang berukuran kecil, Hal ini ditandai dengan terjadinya pembesaran ukuran file hasil dibandingkan ukuran file awal. 5.
40
Adisantoso
et al. - Kornpresi Data Menggunatcan Algontma
Huffman
Dengan menggunakan metode kompresi apapun memiliki trade off, dimana kita akan diberi pilihan hasil maksimum dengan iterasi yang lama atau iterasi yang sangat cepat namun dengan hasil yang biasa. Hasil percobaan yang terdapat pada pembahasan menunjukan bahwa waktu iterasi yang diperlukan oleh algoritma Huffman Stahl untuk melakukan kompresi dan dekompersi adalah cenderung lebih kecil dibandingkan dengan yang dilakukan oleh algoritma Huffman Adaptif. Namun untuk hasil kompresi terIihat unjuk kerja Huffman Adaptif adalah lebih baik dibandingkan Huffman Statik. 6.
SARAN Pada saat mengimplementasikan algoritma Huffman Adaptif digunakan prosedur yang menjadikan kompleksitas aIgoritma Huffman Adaptif menjadi O(n.m). Seharusnya kompleksitas Huffman adaptif hampir sama dengan algoritma Huffman Statis yaitu O(n 19 m). Pengembangan selanjutnya untuk perbandingan kompresi Huffman statik dan adaptif ini dapat diterapkan pada mekanisme pengiriman paket data terkompresi pada media jaringan. PUSTAKA [1] Cormen, T. H., Leiserson, C. E., dan Rivest, R. L. (1990). Introduction to Algorithms. Mc Graw Hill Company. [2] Huffman, D. A. (1952). A Method for the Construction of MinimumRedundancy Codes. Proc. IRE, Vol. 40, 1098-1101. [3] Hutasoit, Y. E. (2001). Huffman Coding Untuk Kompresi Data Teks Berbahasa Indonesia. Skripsi. jur usan Ilmu Komputer Fakultas MIPA IPB. Bogor, Indonesia. [4] Layungsar-i. (2003). Penyempurnaan dan Implementasi Software Kompresi Multi Tahap Menggunakan Huffman Coding. Skripsi. [urusan Ilinu Komputer Fakultas MIP A IPB. Bogar, Indonesia. [5] Lelewer, D. A., dan HirschbergD. S. (1987). Data Compression: ACM Computing Suroefs, Vol. 19, 261-296. . [6] Moore, D. S. (1994). The Basic Practice of Statistics. ISBN 0-7167-2628-9. W.H. Freeman and Company. New York [7] Vitter, J. S. (1987). Design and Analysis of Dynamic Huffman Codes. Journal of ACM, Vol. 344, 825-845. [8] Vitter, J. S. (1989). ALGORITHM 673: Dyriarnic Huffman Codes. ACM Transactions on Mathematical Software, Vol. 15, No.2, 158-167.
TEKNOIN, Edisi Khusus, Nopember 2004,33-41
41