PEMBANDINGAN METODE HUFPMAN DAN LEMPEL-ZIVWELCH UNTUK PEMAMPATAN BERKAS TEKS
MEGA ASTRIGINA
JURUSAN ILMU KOMPUTER FAKULTAS MATEMATIKA DAN ILMU PENGETAHUAN ALAM INSTITUT PERTANIAN BOGOR BOGOR 2001
RINGKASAN MEGA ASTRIGINA. Pembandingan Metode Huffman dan Lempel-Ziv-Welch Untuk Pemampatan Berkas Teks (The Comparison Between Huffan and Lemnpel-Ziv-Welch Methods /or File Text Comm~pression).Dibimbing oleh JULIO ADISANTOSO dan AGUS BUONO. Pemampatan teks bertujuan untuk mengurangi pengulangan penggunaan simbol atau karakter yang menyusun teks dengan cara mengkodekan simbol-simbol atau karakter tersebut sehingga kebutuhan ruang penyimpanan dapat dikurangi dan waktu transfer data dapat lebih cepat. Proses pemampatan teks dapat dilakukan dengan cara mengkodekan segmen-segmen dari teks asli yang kemudian diletakkan dalam kamus. Cara kompresi ini dikenal dengan model kamus yang merupakan karakteristik dari metode Lempel-Ziv-Welch. Selain itu ada model lain yaitu model statistik yang meruprkan karakteristik dari metode Huffman. Metode ini mengkodekan simbol-simbol atau karakter dengan bantuan binary tree dengan cara menggabungkan dua buah frekuensi kemunculan karakter paling kecil hingga terbentuk pohon kode. Penelitian ini bertujuan untuk mempelajari metode Huffman dan Lempel-Ziv-Welch (LZW) untuk pemampatan teks dan membandingkan hasil pemampatannya. Dalam penelitian ini digunakan program pemampatan teks yang merupakan implemetasi dari metode Huffman dan LZW. Berkas yang digunakan adalah : 1) berkas berbahasa Indonesia dan lnggris yang berisi kata ulang dan kata acak dengan diberikan perlakuan perbandingan huruf, angka, dan tanda baca; 2) berkas teks biasa dengan ukuran yang semakin meningkat; dan 3) berkas teks yang berisi kata ulang dengan perbandingan tertentu yang semakin meningkat di dalam berkas acak. Kinerja pemampatan dinilai berdasarkan kebutuhan ruang penyimpanan, rasio pemampatan, waktu proses dan analisis rtrnning [irrte program. Metode LZW memberikan hasil yang lebih baik dibanding metode Huffman terutama pada berkas teks yang berisi pengulangan kata. Rasio pemampatan LZW berkisar antara 30%-95% dengan rata-ratanya adalah 62,28%, sedangkan metode Huffman berkisar antara 30%-50% dengan rata-ratanya adalah 39,56%. Metode Huffman membutuhkan ruang ~enyimpananhasil pemampatan dan waktu dua kali lebih besar dibandingkan metode LZW.
PEMBANDINGAN METODE HUFFMAN DAN LEMPEL-ZIVWELCH UNTUK PEMAMPATAN BERKAS TEKS
MEGA ASTIUGINA
Skripsi sebagai salah satu syarat untuk memperoleh gelat Sarjana Komputer pada Program Studi Ilmu Komputer
JURUSAN ILMU KOMPUTER FAKULTAS MATEMATIKA DAN ILMU PENGETAHUAN ALAM INSTITUT PERTANIAN BOGOR BOGOR 2001
.I~~clul: I'cnlbantlingan Metode I-Iul'finan dan Lempel-Ziv-Welch Untuk I'emal1lpatan Berltas 'l'clts Nama : Mega /\strigina NIII' : ti00400002
Menyetujui,
Penulis dilalurkan di Jakarta pada tanggal 9 Fcbniari 1978 dari pasangan Asnawi Raufdan Des~iciniar scbagai a u k kc cmpat dari l i ~ i ubcrsautlaia. Taliun 1996 pe~iulislulus dari SMA Negcri 52 Jtlkarla dan pada tali ill^ yang s a n a pei~ulisinemolai mass studi di Institut Pertalua~Bogor rnelalui jalur Undiu~gan Seleksi Masuk IPB sebagai civitas akaderluka Jurusan Illnu Komputer Fakultas Matematika dm1 Ilmu Pengetaluan A l a n yang saat itu masih berstatus P r o g r a ~Studi. i~ Selama masa perkulial~upenulis pcrtu~limenjabat sebagai Sekretaris Hili~punanMahasiswa Ilmu Komputer pada lnasa jabatan 199811999.
PRAKATA Puji dan syukur penulis panjatkan kehadirat Allah S W T karena atas berkat, rahmat dan hidayah-Nya karya ilmiah ini dapat diselesaikan. Tema yang dipilih dalam penelitian ini adalah pemampatan data, dengan judul Pembandingan Metode Huffman dan Lempel-Ziv-Welch untuk Pemampatan Berkas Teks. Penulis mengucapkan terima kasih kepada semua pihak yang telah memberikan bantuan, bimbingan dan dorongan selama penyelesaian karya ilmiah ini, antara lain kepada : I . Bapak Ir. Julio Adisantoso, M.Komp. dan Bapak Ir. Agus Buono, M.Si, M.Komp, selaku pembimbing yang- te!ah memberikan bimbingan, arahan, saran dan bantuan dalam penyiisunan -. karya ilmiah ini. 2. Teman-teman mahasiswali terutama Panji, Tuti 'kla', Mira, Erwin, Tuti, Dini, Jarot, Tiza, teh Hani, Yusuf, Mela, Umar, Inez, Sisi dan Yadi dan seluruh ilkomers 33 atas segala bentuk bantuannya. 3. Papa dan mama tersayang atas segala doa, perhatian dan kasih sayangnya, serta uni mona, uda ari, uni lisa dan rafki atas segala bantuannya baik moril maupun materil. 4. Terkhusus kepada 'si kembar' Andri yang telah memberikan bantuan, perhatian, pengertian dan dorongan semangat yang tidak ternilai harganya. Thanks for beinglvilh me. 5 . Staf dan karvawan lurusan llmu Komputer IPB untuksegala bantuannya. 6. Serta seluruk pihak yang telah rnernbantu yang tidak dapat penuliscantumkan namanya satu persatu. Semoga karya ilmiah ini dapat bermanfaat dan dapat digunakan sebaik-baiknya Bogor, luli 2001
mega Aslriginu
DAFTAR IS1 Halaman DAFTAR TABEL
...........................
. . ..............................................................................
DAFTAR GAMBAR
...
vlll Viii
DAFTAR LAMPIRAN .................... . .
ix
PENDAHULUAN Latar Belakang Tujuan
1 1 1
TINJAUAN PUSTAKA
1 1 2 2
Kode Huffman Lempel-Ziv-Welch (L
3
METODOLOGI Bahan Percobaan Analisis
4 4 4
HASIL DAN PEMBAHASAN Kebutuhan Ruang Pe Waktu Proses Pemampata Dekompresi Berkas Hasil Analisis R~mningTirn
5 5 8 9
4
.,,,................. .
....
9
KESIMPULAN DA Kesimpulan Saran
10 10 II
DAFTAR PUSTAKA
11
DAFTAR TABEL
I . Contoh simbol dan frekuensi kemunculannya ..........................................................................
2
2 . Struktur kode dari Huffman free ..................................................................................................
3
3 . Urutan proses kompresi algoritma LZw(inp~~f slring : ""WEDAWE"WEE"WEB"WET")
...........
3
4 . Urutan proses dekompresi dari algoritma LZW (""WED<256>E<260><261><257>8<26O>T"
sebagai input string) ....................................................................................................................
4
5 . Kebutuhan ruang penyimpanan hasil pemampatan untuk berkas perlakuan ..................................
5
6. Kebutuhan ruang penyimpanan berkas tanpa perlakuan pada percobaan pertama .........................
6
..............
7
........
7
9 . Rasio hasil pemampatan berkas berisi kata ulang dengan persentase tertentu dalam kata acak .....
8
10. Waktu proses kompresi dan dekompresi berkas perlakuan dan tanpa perlakuan ..........................
8
I I . Waktu proses kompresi dan dekompresi berkas tanpa perlakuan dengan ukuran semakin meningkat ......................................................................................................................................
9
7 . Rasio mampat berkas tanpa perlakuan pada percobaan pertama ...................................
S. Kebutuhan ruang penyimpanan berkas tanpa perlakuan dengan ukuran semakin meningkat
12. Waktu proses kompresi dan dekompresi berkas yang berisi kata ulang dengan persentase
tertentu dalam kata acak ..............................................................................................................
9
DAFTAR GAMBAR Halaman I . Tree hasil algoritma Huffman untuk data contoh pada Tabel I .................................................
3
2 . Grafik rasio pemampatan berkas teks berulang Indonesia dan lnggris dengan metode
tluffman dan LZW ...................................
.....................................................................................
6
3 . Grafik perbandingan rasio berkas teks acak Indonesia dan Inggris dengan berkas teks
ulang menggunakan metode Huffman ...........................................................................................
6
4. Grafik perbandingan rasio berkas acak Indonesia dan lnggris dengan metode LZW dan
...........................................................................................................................
6
5. Grafik rasio pemampatan berkas acak Indonesia dengan ukuran semakin meningkat ....................
7
6 . Grafik rasio pemampatan berkas acak Inggris dengan ukuran semakin meningkat ........................
7
7. Grafik rasio pemampatan berkas ulang Indonesia dengan ukuran semakin meningkat ..................
7
Huffman
8 . Grafik rasio pemampatan berkas ulang lnggris dengan ukuran semakin meningkat .....................
8
9. Kode program kompresi algoritma LZW ..........................
9
....................................................... . .
10. Prosedurfind-??rarch(j pada algoritma LZW .................................
................................................
11. Tahap penghitungan frekuensi karakter pada algoritma Huffman ............................................
10 10
DAFTAR LAMPIRAN Halaman
I . Keterangan mengenai berkas teks yang digunakan .........................................................................
13
2 . Tabel kebutuhan ruang penyimpanan hasil pemampatan berkas perlakuan dan tanpa perlakuan ...
I4
3 . Rasio hasil dekompresi berkas termampatkan
I5
.........................................................................
.................
I6
5 . Tahap pengkodean pada algoritma Huffman ..................................................................................
17
4. Tahap pembuatan tree pada algoritma kompresi Huffman ...................................
PENDAHULUAN
dari metode Huffinan. Metode ini adalah metode statistik yang optimal (Chrochemory & Lecroq, 1996), yang menggantikan tiap simbol dengan Latar Belakang Penyajian informasi dapat dilakukan secara sebuah kode baru. Penelitian mengenai pemampatan (kompresi) lisan, tulisan atau dalam bentuk gambarlcitra. Penyajian informasi dalam bentuk tulisan biasa berkas teks telah lama dilakukan. Agus (1997) dikenal dengan data teks. Meskipun kemampuan melakukan penelitian pada berkas teks Kamus data teks lebih sederhana dalam memberikan Besar Bahasa Indonesia Elektronik. Pada makna dibandingkan data gambarlcitra, namun penelitiannya kompresi dilakukan terhadap basis informasi berupa data teks masih sangat data teks, dan hasil dekompresi menampilkan sebagian kecil data dari berkas yang terkompres. diperlukan. Tetapi karena dekompresi teks hanya dapat Sebelum berkembangnya teknologi informasi, data biasanya disimpan dan disajikan dalam media dilakukan berdasarkan kata dasar, maka proses kertas. Cara ini kurang menguntungkan, karena tipdare pada kamus, misalnya penambahan istilah data dalam jumlah besar akar, memerlukan ke~tas baru, sulit untuk dilakukan. Selain itu Firdaus dan ruang penyimpanan yang besar pula. Selain itu (1993) melakukan penelitian pada berkas teks tetap. Penelitian ini memberikan alternatif data tersebut tidak tersimpan secara baik serta pemalnpatan data dengan perancangan kode yang pengirimannya akan memakan waktu yang lama. optimal, tetapi metode ini tidak memberikan Seiring dengan berkembangnya teknologi, penyimpanan dan pengiriman data dapat dilakukan alternatif dalam pemecahan kembali (dekompresi), apakah berkas yang terkompresi akan dengan menggunakan media komputer, yaitu dikembalikan ke dalam bentuk aslinya. dengan menyimpan dalam media disk. Karena berkas teks sangat beragam jenisnya, Seperti kita ketahui bahwa ukuran data teks maka penulis membatasi penelitian dengan lebih kecil bila dibandingkan dengan ukuran menggunakan berkas teks bertipe .txt, dengan gambarlcitra, dan kita ketahui pula beberapa metode Huffman dan LZW. instansi biasanya selalu menyimpan data teks dalam jangka waktu lama karena akan dibutuhkan Tujuan sewaktu-waktu. Meskipun demikian, untuk Penelitian ini bertujuan untuk mernpelajari keefisie~ianruang penyimpanan dan mendapatkan metode Huffman dan Lempel-Ziv-Welch (LZW) waktu transmisi data yang lebih cepat, maka untuk pemampatan teks dan membandingkan hasil dianggap perlu untuk melakukan pemampatan pemampatannya. untuk berkas teks ini. Pemampatan data pada berkas teks adalah dengan mengkodekan simbol-simbol yang menyusun teks. Salah satu cara pemampatan berkas ini adalah dengan metode kamus, yang TINJAUAN PUSTAKA merupakan karakteristik dari metode Lempel-Ziv. Metode Lempel-Ziv diperkenalkan oleh Jacob Ziv Kompresi Data Kompresi data merupakan representasi data dan Abraham Lempel, yaitu pada tahun 1977 yang kemudian dikenal dengan LZ77 dan tahun 1978 dengan menggunakan kode-kode yang lebih yang dikenal dengan LZ7S. Kemudian pada tahun efisien. Kompresi data digunakan untuk 1984, Terry Welch mengembangkan LZ78 yang memperkecil kebutuhan ruang penyimpanan dan dipublikasikan dengan nama LZW. M e n u ~ t mempercepat waktu transfer data. Chrochemory & Lecroq (2000). pengkodean Ada dua jenis kompresi data, yaitu lossless dan dengan metode ini seringkali menghasilkan rasio lossy. Dalam kompresi data lossless, data yang pemampatan yang lebih baik. Metode ini telah dikompresi dapat dikembalikan ke bentuk mengkodekan segmen-segmen dari teks asli yang format aslinya. Metode ini biasanya diterapkan dalam kompresi teks. Sedangkan pada kompresi kemudian diletakkan dalam kamus. Setiap kali segmen-segmen tersebut dijumpai dalam kamus data lossy, data yang telah dikompresi tidak dapat 100% dikembalikan ke bentuk aslinya, namun saat pembacaan teks asli, maka segmen-segmen demikian, komponen yang hilang dalam kompresi tersebut digantikan dengan indeksnya pada kamus. Selain itu ada teknik yang berbeda, yaitu lossy ini cukup kecil sehingga dapat diabaikan. pengkodean statistik yang merupakan karakteristik
Metode ini biasanya diterapkan dalam kompresi irnage, yaitu image suara dan inrage citra.
Huffman dapat dibuat dengan algoritma berikut (Agus, 1997):
Model Kompresi Data Penyimpanan data ke dalam bentuk yang lebih mampat memerlukan model yang dapat merepresentasikan data ke dalam bentuk lain yang ukurannya lebih kecil namun dapat dikembalikan lagi ke bentuk semula. Pada saat ini terdapat dua model utama dalam kompresi data lassless, yaitu ~iiodelstatistik dan model kamus (Nelson, 1992). Pada model statistik, kompresi dilakukan dengan membaca tiap karakter atau satuan lain dan membuat simhol baru yang merepresentasikan data tersebut. Ukuran dari simbol ini diusahakan lebih kecil dari aslinya. Pembuatan simbol berdasarkan frekuensi kemuculan data. Model statistik ini diimplementasikan dengan algoritma Huffman Tree dan Arithmetic Coding. Pada model kalnus digunakan simbol baru untuk menggantikan string data. Dalam model ini terdapat tabel yang berisikan kumpulan string beserta simbol yang merepresentasikannya. Algoritma y a n g mengimplementasikan model ini umumnya adalah algoritma yang berdasarkan ide dari dua tulisan A.Lempel dan J.Ziv yaitu LZ77 dan LZ78, sedangkan algoritma LZW (LempelZiv-Welch) adalah pengembangan dari algoritma LZ7S.
I . Urutkan simbol-simbol berdasarkan peluang kemunculan. 2. Gabungkan dua simbol yang memiliki peluang kemunculan terendah secara berturut-turut, membentuk simpul baru hasil gabungan dari kedua simbol tersebut, sehingga dapat terbentuk suatu binary tree dengan tiap simpul merupakan peluang dari seluruh simpul yang ada dibawahnya. 3 . Telusuri sebuah path dari root menuju setiap leaf dengan memperhatikan arah pada setiap simpul.
Kode Iluifmnn Kode I-luffman adalah teknik kompresi data statistik yang menghasilkan pengurangan panjang rata-rata kode yang digunakan untuk mewakili simbol suatu alphabet. Panjang kode dari sebuah karakter ditentukan oleh frekuensi relatif kemunculannya dalam data. Untuk karakter dengan frekuensi atau peluang kemunculannya tinggi akan ditandai dengan kode yang pendek, sedangkan untuk karakter yang memiliki peluang kemunculannya rendah ditandai dengan kode yang panjang. Kode Huffman memiliki atribut prefix yang unik, sebingga kode tersebut dapat dikembalikan ke bentuk asalnya dengan benar meskipun panjang kodenya b e ~ a r i a s i . Suatu kode Huffman dapat dihasilkan dengan bantuan binary tree yaitu dengan cara menggabungkan dua buah frekuensi kemunculan karakter paling kecil hingga terbentuk pohon kode. Pohon kode yang dihasilkan disertakan dengan teks yang terkompresi, agar mudah di dalam proses dekompres (Chrochemory & Lecroq, 1996). Kode
Sebagai ilustrasi, misalkan terdapat lima simbol dalam data dengan frekuensi kemunculan masingmasing terlihat pada Tabel I . : Tabel I. Contoh simbol dan frekuensi kemunculannya Simbol Frekuensi
1EI 1 17 1
D 16
IC 1 1 11 1
A 4
I 1
B 3
Kelima simbol ini akan ditempatkan sebagai simpul terbawah (lean dari pohon decoding. Bobot dari masing-masing simpul tersebut adalah frekuensi dari simbol-simbol yang bersangkutan. Simbol-simbol tersebut menyusun dafiar semua simpul-simpul bebas (yaitu simpul yang belum mempunyai parent). Tahap pertama adalah menggabungkan dua simpul bebas dengan frekuensi terkecil, yaitu simpul A dan B dengan masing-masing frekuensi (bobot) 4 dan 3. Kedua simpul digabungkan dengan sebuah simpul parent dengan bobot 7 (penjumlahan dari bobot A dan bobot B). Simpul A dan B kemudian dihapus dari daftar simpul bebas. Cabang A ditandai dengan digit 0 dan cabang B dengan digit 1. Tahap berikutnya, dua simpul bebas yang memiliki bobot paling sedikit digabungkan, yaitu simpul C (dengan bobot I I) dengan simpul parent ( dengan bobot 7) yang terbentuk dari simpul A dan simpul B). Keduanya digabungkan dengan sebuah simpul parent barn berbobot 18. Parent dari gabungan A dan B dihapuskan dari simpul bebas. Demikian seterusnya sehingga terbentuk tree seperti tercantum pada Gambar 1.
setiap string karakter baru yang baru dijumpai ke dalam sebuah tabel string. Kompresi yang terjadi adalah satu string karakter digantikan oleh satu kode tunggal dari output (Tabel 3). Kode keluaran algoritma LZW dapat memiliki panjang yang beragam, tetapi harus memiliki bit yang lebih panjang dari karakter tunggal yang biasanya menggunakan 8 bit. LZW menggunakan sebuah kamus berukuran 4 Kb, yang berarti kode 0-255 menunjukkan byte individu dan kode 256-4095 menunjukkan stibstring. Algoritma LZW adalah sebagai berikut :
17
Set rv=NIL
E
C
D
A
B
Gambar I. P e e h a i l algoritma i-luffman untuk data
loopread a character K ifwK cxirt in thc dictionary w=wK
contoh pada Tabel I. Dari tree yang terbentuk dapat diketahui kode dari simbol dengan menelusuri mulai dari simpul leaf ke arah root, dengan menambahkan bit baru setiap melewati parent. Dengan menggunakan strategi ini, bit-bit akan dikembalikan dalam urutan terbalik, sehingga diperlukan sebuah stack untuk ~ne~ilbangkitkan kode-kode tersebut. Strategi ini menghasilkan struktur kode yang dapat dilihat pada Tabel 2. Tabel 2. Struklur kodc dari IIuflman tree
Fi 111
Seperti yang terlihat pada Tabel 2, setiap kode nlerupakan kode prefik, yaitu tidak ada satu kode pun merupakan awalan dari kode-kode yang lain. Kode prefik ini menguntungkan karena menyederhanakan proses kompresi dan dekompresi. Lempel-Ziv-Welch (LZW) Algoritma LZW mempakan turunan dari algoritma LZ78, yang dikembangkan oleh Terry Welch (1984) dalam Dobbs (1989). Secara ~ a r i sbesar, kompresi LZW mengganti string karakter (substring) dengan kode tunggal, dengan tidak memperhatikan teks berikutnya yang akan muncul tetapi hanya dengan menambahkan
oulput the code for w add wK lo the swing table end loop
Sebuah string baru ditambahkan ke dalam tabel string setiap kali sebuah kode baru (new code) dihasilkan. String-string baru dibentuk dengan menambahkan karakter saat itu, yang disimbolkan dengan K, ke akhir dari string yang ada, yang disimbolkan dengan w. Proses kompresi dari algoritma LZW dapat dilihat padaTabel 3. Tabel 3. Urutan proses kompresi algoritma LZW (input srring : ""WED"WEAWEE"WEB"WET").
-
Tabel 4. Urutan proses dekompresi dari algoritma LZW. (""WED<256>Ec260><261><257>B<260>T' sebagai inprrl slring). W
I
K
I
output
I
I
A
l
A
l
index
I
2.
simbol
I
RAM Hardisk Perangkat
: 64MB : 8,4GB
lunak : MS.DOS berbasis windows dan Windows 98.
Percobaan Pada penelitian ini, dilakukan perancangan percobaan pengkompresian.
Seperti pada proses kompresi, proses dekompresi (Tabel 4) menambahkan string baru ke dalam kamus setiap membaca kode baru. Penambahan string tersebut bertujuan untuk mengubah setiap kode yang datang ke dalam string dan mengirimkannya sebagai orrlptrt.
METODOLOGI
1. Percobaan pertama, diberikan perlakuan terhadap berkas teks, yaitu dibedakan dalam tiga jenis : huruf, angka dan bukan keduanya b a n g selanjutnya dikategorikan sebagai tanda baca). Kemudian diberikan perbandingan terhadap ketiga jenis tersebut dengan jumlah 9. perbandingan keseluruhan adalah Perbandingan yang dibuat memiliki kriteria, yaitu : a. berkas yang mengandung huruf lebih banyak, dengan perbandingan 7: 1 :1, b. berkas yang mengandung angka lebih banyak, dengan perbandingan 1:7:1, c. berkas yang mengandung tanda baca lebih banyak, dengan perbandingan 1:1:7, d. berkas yang mengandung jumlah ketiga faktor penyusunnya sama, dengan perbandingan 3:3:3. Sebagai pembanding, digunakan berkas teks biasa tanpa perlakuan.
Bahan Penelitian ini menggunakan dua program pemampatan data teks, yaitu : I . Program yang merupakan implementasi dari 2. Percobaan kedua, yaitu menggunakan berkas teks tanpa perlakuan dengan ukuran yang algoritma LZW yang dibuat oleh Mark R. berbeda untuk melihat bagaimana kebutuhan Nelson, di downlood dari internet ruang pada hasil kompresi berkas teks. (htlo://dornra. n c t / ~ n o r k n ~ a ~ ' t i c l e s / l nhtnr ~~/I~~. ).
2. Static Huffman, implementasi dari algoritma Huffman, yang dibuat oleh Shaun Case, di doivload dari internet (fl~:NA~.cvf-kr.edu.pl ). Kedua program tersebut terdiri dari proses pengkodean dan pendekodean, yang dibangun dengan menggunakan bahasa pemrograman C. Berkas-berkas teks yang digunakan adalah berkas bortipe .txt ditulis dengan menggunakan editor kata, yaitu Notepad, yang terdiri dari berkas berbahasa - Indonesia dan berbahasa Inggris. Masing-masing berkas berisi teks pengulangan dan teks acak, Keterangan mengenai berkas teks yang digunakan dapat dilihat pada Lampiran I. Percobaan pada penelitian ini menggunakan : 1. Perangkat keras, dengan spesifikasi : Prosesor : AMDK61350 MHz
-
3.
Percobaan ketiga, yaitu menggunakan kata bemlang dengan persentase tertentu di dalam berkas teks acak.
Analisis Percobaan yang telah dirancang selanjutnya diujicoba dan dilakukan analisis terhadap kinerja kedua algoritma, yaitu : 1. Kebutuhan Ruang Penyimpanan Seluruh berkas teks dikompresi dengan menggunakan metode LZW baik berkas yang telah dirancang pada percobaan pertama, kedua, maupun ketiga, kemudian dilakukan pula percobaan yang sama dengan menggunakan metode Huffman. Untuk percobaan ini dieatat
lndo Ulang
lngg Ulang
Hufflnun
Haffinm
lnda Ulang lngg Ulang UW UW
Gambar 2. Grafik rasio pemampalan berkas teks berulang lndonesia dan Inggris dengan metodc Huffman dan LZW. Rasio pemampatan berkas teks acak, baik teks berbahasa lndonesia maupun Inggris, dengan metode Huffman rata-rata hampir sama besar, tetapi masih lebih kecil dari rasio berkas berulang (Gambar 3). Hal ini disebabkan pada berkas acak simbol-simbol bervariasi dan kemungkinan kemunculannya tidak terlalu sering seperti pada berkas berulang.
lndo Aesk
lngg
lndo lngg Acak Ulnng Ulnng : 7 : l E'1:1:7' 0'7:l:l' 0'3:3:Y
lndo
lngg
lndo
lngg
Acak
Acak
Acak
Acak
UW
LZW
Hulf
Fluff
Gambar 4. Gntik perbandingan rasio berkas acak Indonesia dan lnggris dengan metode LZW dan tluffman. Untuk hasil pemampatan berkas tanpa perlakuan dengan menggunakan metode Huffman ataupun LZW, ruang penyimpanannya 0,9 kali lebih kecil dari berkas dengan perlakuan, sehingga rasio pemampatannya sekitar satu kali lebih besar dibandingkan rasio pemampatan berkas dengan perlakuan (Tabel 6 ) . Namun dari pemampatan berkas tanpa perlakuan ini, ruang mampat hasil metode Huffman masih dua kali lebih besar dari LZW, yaitu sebesar 2,09 kali. Tabel 6. Kebutuhan ~ a n penyimpanan g berkas tanpa perlakuan pada percobaan pertma.
Gambar 3. Grafik perbandingan rasio berkas teks acak lndonesia dan lnggris dengan berkas teks ulang menggunakan metode Huffman. Bila menggunakan metode LZW, rasio pemampatan pada berkas teks acak lndonesia maupun inggris lebih kecil dari pemampatan teks berulang menggunakan metode yang sama. Hal ini dikarenakan berkas teks acak mengandung teks yang bewariasi yang menyebabkan substring yang terbentuk tidak selalu sama, sehingga kode yang dihasilkan agak lebih panjang. Tetapi hasil ini masih lebih besar dibandingkan hasil pada metode Huffman (Gambar 4).
Sedangkan untuk masing-masing jenis berkas, rasio mampat rata-rata berkas berbahasa lndonesia agak lebih tinggi dibandingkan berkas berbahasa Inggris, yaitu sekitar 1,03 kali. Selain itu, rasio mampat untuk berkas berulang pada metode LZW lebih besar l,85 kali dari berkas acak dan lebih besar 1,98 kali dari berkas ulang hasil metode Huffman (Tabel 7). Berbeda dengan LZW, rasio mampat berkas ulang dan berkas acak dengan metode Huffman
relatif sama besar tetapi masih lebih kecil dari hasil dengan metode LZW. 60
Tabel 7. Rasio [nampat berkas tanpa perlakuan pada pcrcobaan pertnma.
-.0
Jenis
Rasio Mampat
Rvsio &lampat
Berk-
Acak
Ulane
(.at) Indonesia lnggris
-
2 Ram-
-
m - m
so.
t-----+-----*
40 30
~
2o10
rsta
Fluffman1 LZW Huffman 1 U W 43.8441 49.314 51.4921 93.988 59.66 43.0411 52.138 43.2781 93.863 58.08
B. Berkas T e k s T a n p a Pcriakuan Dengan Ukuran Berkas Semakin Meningkat
t Rasio HulTm~n
+Rario
U W
Garnbar 5. Grafik rasio pemampatan berkas acak Indonesia dengan ukuran semakin meningkat.
Pada uji coba berkas teks sembarang, yaitu teks yang biasa digunakan sehari-hari, kebutuhan ruang penyimpanan dan rasio pemampatan untuk berkas Indonesia dan Inggris dengan metode Huffman atau LZW cenderung berbanding lurus dengan ukuran berkas asli (Tabel 8). Makin besar ukuran berkas asli, makin besar pula ruang pemampatan yang diperlukan. Tabel 8. Kcbutuhan ruang penyimpanan berkas tanpa perlakuan dengan ukuran semakin mcningkat.
Gambar 6. Grafik rasio pemampatan berkas acak lnggris dengan ukuran semakin meningkat.
Sf071 muran B e r k u (bytes) +RasioHuRan +Rasio 61249
Besarnya rasio mampat kedua bahasa baik menggunakan metode Huffman maupun LZW pada berkas acak (Gambar 5 dan 6) relatif sama, namun metode LZW masih memberikan hasil yang lebih tinggi dibandingkan metode Huffman. Untuk berkas berulang tanpa perlakuan (Gambar 7 dan 8) terlihat bahwa dengan menggunakan metode Huffman, rasio mampat berkas Indonesia sedikit lebih tinggi dari berkas Inggris, sedangkan dengan metode LZW rasio mampatnya relatif sama untuk kedua bahasa.
104449
1
LZW
Garnbar 7. Grafik rasio pemampatan berkas ulang Indonesia dengan ukuran scmakin
: ,"
0
c----+-----*
!
berulangkali, sehingga kode yang dihasilkan lebih pendek. Metode ini juga tidak memperhatikan kata-kata yang . - muncul dalam teks, tetapi hanya memperhatikan kemunculan karakter atau simbol lain yang digunakan pada teks.
, +----------?-------
8 1928
+Rsio
141130
195778
Ukuran Berkns (bytts) Huffinan -+Rario
LZW
Gambar 8. Grafik rasio pemampatan berkas ulang Inggris dengan ukuran wmakin meningkat.
C. Berkas yang berisi kata berulang dengan persentase tertentu di dalam kata acak. Untuk hasil percobaan ketiga, metode LZW masih memberikan rasio pemampatan yang lebih besar (1,25 kali) dibanding metode Huffman. Besarnya rasio mampat semakin meningkat sejalan dengan besarnya rasio kata yang berulang dalam berkas acak (Tabel 9).
Waktu Proses Pemampatan Rata-rata waktu proses kompresi berkas teks pada percobaan pertama (Tabel lo), percobaan kedua (Tabel I I) dan percobaan ketiga (Tabel 12), dengan menggunakan metode Huffman, cenderung dua kali lebih besar dibandingkan dengan metode LZW. Hal ini disebabkan pada proses kompresi, algoritma Huffman melakukan tiga tahapan, yaitu ~nenghitungfrekuensi karakter, membuat pollon pengkodean (pohon Huffman) dan selanjutnya melakukan proses pengkodean. Tabel 10. Waktu proses kompresi dan dekompresi berkas perlakuan dan tanpa perlakuan.
Tabel 9. Rasio hasil pemampatan berkas berisi kala ulang dengan pcrsentase tenentu dalam kata acak.
Pada LZW, besarnya rasio rnampat disebabkan it^ pula pads proses dekompresi suatu substring (potongan kata) lebih sering menggunakan metode Huffman, waktu proses rataditemukan dalam kamus, sehingga semakin rata juga dua kali lebih besar dari metode LZW. banyak atau semakin panjang sllbsrring Yang Pads metode Huffman, jalannya proses perlama cocok, rasio kompresi yang dihasilkan akan kali adalah membaca pohon huffman yang telah baik. Metode LZW tidak dibentuk dari proses kompresi, selanjutnya semakin memperhatikan kata-kata dalam berkas, tetapi dilakukan pendekodean. Waktu dekompresi hanya memperhatikan kemunculan suatu h u ~ f Huffman berjalan sedikit lebih cepat dibandingkan l mungkin disebabkan atau simbol lain yangmembentuksubsfringdan proses kompresinya. ~ a ini kemudian dicocokkan pada kamus. Sedangkan dekompresi tidak dilakukan penghitlingan pada metode Huffman, besarnya mamPat frekuensi kemunculan simbol seperti proses disebabkan oleh karakter Yang sama muncul kompresi. Sedangkan pada metode LZW, waktu
Sedangkan pendekodean dari LZW, total rrmning tin~ejuga sebesar O(n) karena proses pendekodean dijalankan sebanyak simbol input, yang dalam ha1 ini adalah simbol yang ada dalam berkas yang telah termampatkan.
I
I
input-codc(F1LE 'input) (
unsigned int return-value; static int input-bit-count=O: static unsigned long input-bit-buffer-Ol while (input-bit-count <= 24) I
l=(unsigned long) getc(inpu1)<< (24-input-bit-count); input-bit-count += 8; input-bit-buffcr
1
rcturn-valuc=input-bit-buffer >> (32-BITS); input-bit-buffer <<= BITS;
'
input-bit-count -= BITS; rcturn(rctum-valuc);
Gambar 10. Prosedur Jnd-match0 LZW.
pada algoritma
Proses kompresi algoritma Huffman terdiri dari tiga tahap, yaitu tahap penghitungan frekuensi karakterlsimbol, tahap pembuatan tree, dan tahap pengkodean teks. Pada tahap penghitungan frekuensi karakterlsimbol. waktu yang diperlukan adalah sebesar n (Gambar 1 I).
selanjutnya adalah pembuatan free (Lampiran 4). Pada tahap ini besar kompleksitas waktunya juga sebesar a'. Waktu proses dalam tahap ini bergantung pada banyaknya simpul yang terbentuk dari simbol-simbol dalam berkas teks asal. Tahap terakhir, yaitu tahap pengkodean. Dalam tahap ini, memerlukan waktu proses sebesar n (Lampiran 5), dengan asumsi n adalah banyaknya karakter atau simbol lain dalam berkas input. Berdasarkan analisis kompleksitas tersebut, total waktu yang diperlukan untuk algoritma kompresi Huffman adalah : T(n) = n + a' + a' + n = 2n + 2a2, karena untuk penghitungan running time diambil nilai yang terbesar dan nilai konstanta bisa diabaikan untuk n besar (Weiss, 1994), maka bisa dikatakan nrnning time-nya adalah O(n + a'). Faktor a' diikut sertakan karena banyaknya simpul yang terbentukjuga mempengaruhi waktu proses. Untuk pendekodean pada metode Huffman, proses diawali dengan pembacaan tabel pendekodean, dalam ha1 ini dihasilkan waktu proses sebesar a, sclanjutnya dilakukan pendekodean terhadap berkas yang termampatkan. Proses ini berjalan dalam waktu sebesar n, karena proses dilakukan sebanyak input, dalam ha1 ini berkas yang termampatkan. Berdasarkan proses tersebut, maka waktu total dari proses pendekodean keseluruhan adalah : T(n) = a + n, sehingga running tittle adalah sebesar O(n+ a).
KESIMPULAN DAN SARAN 4. if(feol~infile))
Gambar I I. Tahap penghitungan frekuensi karakter pada algoritma Huffman. Proses dari baris 3 sampai baris 7, memerlukan waktu konstan serta berada dalam loop sebesar n, sedangkan n merupakan banyaknya simbol yang terdapat dalam berkas teks. Setelah ~enghitunganfrekuensi karakterlsimbol dilakukan, kemudian data diurutkan. Pengumtan dilakukan dengan menggunakan metode quicksort yang kompleksitasnya untuk kasus terbumk adalah sebesar a' (Standish,1995) dengan a adalah banyaknya simpul yang terbentuk. Tahap
Kesimpulan Dari hasil dan pembahasan diperoleh beberapa kesimpulan. Pertama, pemampatan data teks menggunakan algoritma LZW cenderung lebih baik dibanding algoritma Huffman ditinjau dari segi kebutuhan ruang penyimpanan dan waktu proses. Ruang penyimpanan dan waktu proses pada metode Huffman rata-rata dua kali lebih besar dari LZW. Kedua, rasio mampat U W berkisar antara 30%95% dengan rata-ratanya adalah 62,28%, sedangkan metode Huffman berkisar antara 30% 50% dengan rasio rata-ratanya adalah 39,56% untuk semua jenis teks. Ketiga, besarnya rasio pemampatan yang dihasilkan dengan metode Huffman maupun LZW tidak dipengamhi oleh banyaknya huruf, angka atau tanda baca dalam berkas, tetapi dipengamhi
oleh sering dan be~ariasinyasuatu simbol (pada Huffman) atau srrbstring (pada LZW) yang muncul atau digunakan di dalam penyusunan teks. Begitu pula untuk proporsi huruf : angka : tanda baca dengan perbandingan 7:l: I, 1:7: 1, 1:1:7, dan 3:3:3, juga tidak mempengaruhi besarnya rasio pemampatan. Semakin sering suatu simbol atau substring munculldigunakan, maka rasio pemampatannya semakin besar, sebaliknya semakin bervariasi simbol yang digunakan, akan semakin kecil rasio pemampatan yang dihasilkan. Keempat, dalam pemampatan data teks seluruh karakter dan simbol lain yang digunakan pada penyusunan teks selalu dikodekan, tidak ada karakter atau simbol lain yang dihilangkan. Kelima, bahasa tidak mempengaruhi besarnya rasio pemampatan, karena baik bahasa Indonesia maupun bahasa Inggris rasio hasil pemampatannya relatif sama. Keenam, algoritma LZW berjalan dalam waktu linier, sedangkan waktu untuk algoritma Huffman dipengaruhi oleh jumlah simpul yang terbentuk dalam tree (pohon Huffman). Saran Penelitian ini dapat dilanjutkan dengan mengganti algoritma Huffman dengan algoritma Arithmetic Coding untuk memperoleh rasio pelnampatan yang lebih baik. Disamping itu dapat juga dilakukan pengembangan terhadap algoritma LZW agar dapat digunakan untuk pemampatan data it~rogelcitra.
DAFTAR PUSTAKA Agus, I.A. 1997. Pemilihan Strategi dan Algoritme Pemampatan Data Teks Untuk Kamus Besar Bahasa Indonesia Elektronik. Skripsi. Jurusan Ilmu Komputer Fasilkom UI, Depok. CrocLemore, M. & T. Lecroq. 1996. Pattern matching and text compression algorithm. ACM Conrprrl. Strrveys. 28: 39-41. Crochemore, M. & T. Lecroq. 2000. Text data compression algorithm. http: 1lciteseer.nj.nec. com119499.htmI
Dobb's, DR. 1989. LZW Data Compression by hffp://dogma.net/ Mark Nelson. markn/articles/IavNnv.htm
Firdaus, F. 1993. Alternatif Penyimpanan Berkas Tetap Dalam Bentuk Kode Menggunakan Beberapa Struktur Pohon. Skripsi. Jurusan llmu Komputer Fasilkom UI, Depok. Hu ff-sc. zip. flp:/&p.cyf-kr.edu.pNpub/mirror/ Sinrtei.Net/r,rsdos/compress/hz~f-sc.zip Nelson, Mark. 1992. The Data Conrpression Book. 2" ed. M & T Books, New York. Standish, T.A. 1995. Data Strrrct~rre,Algorithms, and Sofhvare Principles i n C. Addison-Wesley Publishing Company, Inc. Weiss, Mark.A.
1994. Data Structlrres and in C++, The BenjaminICummings Publishing Company, Inc.
Algorithm
Analysis
LAMPIFUN
Lampiran 1. Keterangan mengenai berkas teks yang digunakan Berkas Teks IndoUlangl:7: I, IndoUlangl: l:7, IndoUlang7:l:l, lndoUlang3:3:3, InggUlangl:7:l, InggUlangl:l:7, InggUlang7: I:I,InggUlang3:3:3, IndoAcakl:7: I, IndoAcakl: l:7, IndoAcak7: I:1, IndoAcak3:3:3,
Keterangan Berkas teks lndonesia yang berisi pengulangan yang diberikan perlakuan dengan perbandingan 1:7:1, 1:1:7,7:1:1,3:3:3 Berkas teks lnggris yang berisi pengulangan yang diberikan dengan perlakuan 1:7:1, 1:1:7, 7:1:1,3:3:3 Berkas teks Indonesia yang berisi kata-kata acak yang diberikan perlakuan dengan perbandingan 1:7:1, 1:1:7,7:1:1,3:3:3
lnggAcak1:7: 1, InggAcakl:l:7, InggAcak7:l: I,InggAcak3:3:3,
Berkas teks lnggris yang berisi kata-kata acak yang diberikan perlakuan dengan perbandingan 1:7:1, 1:1:7, 7:1:1, 3:3:3
1ndoMurni.txt
Berkas teks Indonesia yang berisi kata-kata acak tanpa perlakuan yang digunakan sebagai pembanding dari berkas perlakuan Berkas teks lnggris yang berisi kata-kata acak tanpa perlakuan yang digunakan sebagai pembanding dari berkas perlakuan
UlangIndo.txt
Berkas teks Indonesia yang berisi pengulangan tanpa perlakuan yang digunakan sebagai pembanding dari berkas perlakuan
Repeatlngg.txt
Berkas teks lnggris yang berisi pengulangan tanpa perlakuan yang digunakan sebagai pembanding dari berkas perlakuan Berkas teks Indonesia acak tanpa perlakuan yang digunakan pada strategi kedua
Indo-l.txt, Indo-2.txt, Indo-3.txt
Ingg-l.txt, Ingg-Z.txt, Ingg-3.txt, IndoUlang-l.txt, IndoUlang3.txt
IndoUlang-2,txt,
InggUlang-l.tst, InggUlang-3.txt
InggUlang-2.txt.
Berkas teks lnggris acak tanpa perlakuan yang digunakan pada strategi kedua Berkas teks lndonesia yang berisi pengulangan tanpa perlakuan yang digunakan pada strategi kedua Berkas teks Indonesia yang berisi pengulangan tanpa perlakuan yang digunakan pada strategi kedua
The-l.txt, the-2.txt, the-3.txt, becosI.txt, becos-2.txt, becos3.txt
Berkas leks Inggris yang mengandung perulangan kata 'the' dan 'because' dengan rasio berturut-turut 17.01%. 28.66% dan 40.10%.
Dari-l.txt, dari-2.txt, dari3.txt, meskiI.txt, meski-2.txt. meski-33x1
Berkas teks Indonesia yang mengandung perulangan kata 'dari' dan 'meski' dengan rasio berturut-turut 14.61%. 25.80% dan 36.61%.
I
14
Lampiran 2. Tabel kebutuhan ruang penyimpanan hasil pemampatan berkas perlakuan dan tanpa perlakuan.
Lampiran 3. Rasio hasil dekompresi berkas tennampatkan.
Berkas Teks
Ukuran bcrkas tcrkornprcs (bytes)
Ukuran hasil pendekodcan (bytes) dan wakfu pcndckodcan (dctik)
Rasio
Lanipiran 4. Tahap pembuatan tree pada algoritma kompresi Huffman, short create-tree() I
double maxfreq = 0 ; struct chardata *new-node = NULL; while (maxfreq < 0.99999 ) { find-lowest-freqs(); if ((new-node = (struct chardata *)malloc(sizeof (struct chardata)) )== NULL) 1
puts("1nsufficient memory, malloc() failed in create-tree()."); reiurn FALSE;
1 new-node->up = NULL; new-node->left = ptr2; new-node->right = ptrl; new-node->charnum = -1; ptrl->up = new-node; ptr2->up = new-node;
maxfreq = new-node->frequency;
1
root = new-node;
Lampiran 5. Tahap pengkodean dengan algoritma Huffman. short compress(void) { if ((infile=fopen(infile-name, "rb")) ==NULL) { printf("Unable to open %s\nV,infile-name); return I ;
outfile=fopen("hasil.huf',"wb"); if(outfile=NULL) { printf("Unable to open hasil.huf'); return 1;
1 for (i=O; i 4 3 ; i++) fputc(origname[i], outfile); if (fwrite((void*)&array-rnax-index,
sizeof(short), I, outfile < l )
I
p r i n t r u n a b l e to write to %s -- out of disk space?", outtile-name); fclose(outfile); return 1; )
if ( fivrite((void*)&total, sizeof(unsigned long), 1, outfile)< I) ( printf("Unable to write to %s -- out of disk space?", outfile-name); fclose(outfile); return 1; ) if (fivrite((void*)decode-table, sizeof(struct decode-table-element), array-max-index array-max-index) (
printf("Unab1e to write to %s fclose(outfile); return 1:
+ 1, outfile
<
-- out of disk space?", outfile-name);
1
for (i=O; i< total; i++) I
I
c = fgetc(infi1e); if (c = EOF) { printKM\nReachedunexpected end of input file at position %Id.\nU,i); return I; I
array-index = find-match(c); if (outpqt-bits(huflable[array_index]->bitsequence (short)huflable[array-index]->seq_length)! { ~rintf("Unableto write to %s -- out of disk space?", outfile-name); return 1; }
1
output-bits(255.7); printf("%ld bytes encoded.\nU,i); fclose(outtile); return 0; )
0)
