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
