halaman judul perbandingan kompresi teks … · gambar 2.2 pohon biner sempurna dan beberapa contoh...

i

HALAMAN JUDUL

PERBANDINGAN KOMPRESI TEKS MENGGUNAKAN

ALGORITMA HUFFMAN STATIS, HUFFMAN DINAMIS

DAN MODIFIKASI ALGORITMA HUFFMAN

SKRIPSI

Diajukan Untuk Memenuhi Salah Satu Syarat

Memperoleh Gelar Sarjana Komputer

Program Studi Teknik Informatika

Disusun oleh:

Yohanes Beny Prasetyo

115314040

PROGRAM STUDI TEKNIK INFORMATIKA

JURUSAN TEKNIK INFORMATIKA

FAKULTAS SAINS DAN TEKNOLOGI

UNIVERSITAS SANATA DHARMA

YOGYAKARTA

2016

PLAGIAT MERUPAKAN TINDAKAN TIDAK TERPUJI

ii

HALAMAN JUDUL (English)

COMPARISON TEXT COMPRESSION USING STATIC

HUFFMAN ALGORITHM, DYNAMIC HUFFMAN

ALGORITHM AND MODIFICATION HUFFMAN

ALGORITHM

A Thesis

Presented as Partial Fulfillment of The Requirements

To Obtain Sarjana Komputer Degree

In Informatics Engineering Study Program

Written by:


115314040

INFORMATICS ENGINEERING STUDY PROGRAM

DEPARTMENT OF INFORMATICS ENGINEERING

FACULTY OF SCIENCE AND TECHNOLOGY

SANATA DHARMA UNIVERSITY

YOGYAKARTA

2016


iii

HALAMAN PERSETUJUAN


iv

HALAMAN PENGESAHAN


v

HALAMAN PERSEMBAHAN

“ Mintalah, maka akan diberikan kepadamu;

carilah, maka kamu akan mendapat;

ketoklah, maka pintu akan dibukakan bagimu ” – Yesus Kristus

“ Orang muda terkasih,

jangan mengubur talenta-talenta, karunia yang diberikan Allah padamu.

Jangan takut memimpikan hal-hal besar “ – Paus Fransiskus

Aku persembahkan skripsi ini untuk :

Allah Bapa di surga yang sudah memberikan segalanya bagiku

dan semua yang selalu ada dalam suka dan duka ku


vi

PERNYATAAN KEASLIAN KARYA

Saya menyatakan dengan sesungguhnya bahwa skripsi yang saya tulis ini tidak

memuat karya atau bagian karya orang lain, kecuali yang telah disebutkan dalam

kutipan dan daftar pustaka sebagaimana layaknya karya ilmiah

Yogyakarta, 11 Januari 2016

Penulis



vii

LEMBAR PERNYATAAN PERSETUJUAN PUBLIKASI KARYA ILMIAH

UNTUK KEPENTINGAN AKADEMIS

Yang bertanda tangan di bawah ini, saya mahasiswa Universitas Sanata Dharma:

Nama : Yohanes Beny Prasetyo

NIM : 115314040

Demi pengembangan ilmu pengetahuan, saya memberikan kepada perpustakaan

Universitas Sanata Dharma karya ilmiah yang berjudul:

PERBANDINGAN KOMPRESI TEKS MENGGUNAKAN

ALGORITMA HUFFMAN STATIS, HUFFMAN DINAMIS


Beserta perangkat yang diperlukan (bila ada). Dengan demikian saya memberikan

kepada perpustakaan Universitas Sanata Dharma hak untuk menyimpan,

mengalihkan dalam bentuk media lain, mengelolanya dalam bentuk pangkalan

data, mendistribusikan secara terbatas, dan mempublikasikan di internet atau

media lain untuk kepentingan akademis tanpa perlu meminta ijin dari saya

maupun memberikan royalty kepada saya selama tetap mencantumkan nama saya

sebagai penulis.

Demikian pernyataan ini saya buat dengan sebenarnya.


Yang menyatakan,



viii

PERBANDINGAN KOMPRESI TEKS MENGGUNAKAN ALGORITMA

HUFFMAN STATIS, HUFFMAN DINAMIS


ABSTRAK

Permasalahan ukuran file dan waktu yang dibutuhkan menjadi suatu

kendala tersendiri dalam proses penyimpanan atau perpindahan antar media.

Solusi permasalahan tersebut telah ditemukan oleh David A. Huffman dengan

algoritma yang didasarkan pada pohon biner. Algoritma Huffman mempunyai

dua jenis yaitu Huffman Statis dan Huffman Dinamis. Algoritma ini terkenal

dalam bidang kompresi data, akan tetapi perkembangan zaman membuktikan

algoritma ini memiliki hasil kompresi yang kurang maksimal.

Dalam penelitian ini, akan dilakukan uji perbandingan hasil algoritma

Huffman Statis, Huffman Dinamis serta modifikasi algoritma Huffman yang

dibuat untuk penelitian ini. Secara umum ketiga algoritma ini mempunyai proses

yang sama yaitu proses pengubahan data asli menjadi kode biner (encoding) dan

proses pengubahan kode biner menjadi data asli (decoding). Pengujian dilakukan

untuk mengetahui perbandingan waktu kompresi dan besarnya ratio compression

dari ketiga algoritma. Dalam penelitian ini akan diuji teks dengan dua bahasa

yaitu Indonesia dan Inggris untuk mengetahui pengaruh bahasa dengan hasil

kompresi, yang didasarkan dengan kemunculan tiap karakter. Implementasi

algoritma dalam penelitian ini menggunakan bahasa pemrograman Java.


ix

ABSTRACT COMPARISON TEXT COMPRESSION USING STATIC HUFFMAN

ALGORITHM, DYNAMIC HUFFMAN ALGORITHM AND

MODIFICATION HUFFMAN ALGORITHM

ABSTRACT

Problems file size and time taken into an obstacle in the process of storage

or displacement between media. Solution these problems have been found by

David A . Huffman with the algorithms that based on binary tree. Huffman

algorithm have two types is huffman static and huffman dynamic. This algorithm

famous in the field of compression data, but time progress prove this algorithm

having results compression not optimal.

In this research , test will be done the comparison of the algorithms

huffman static , huffman dynamic and algorithms huffman modification made for

this study. In general third algorithm have similar process that is the process of

transformation data natives to be binary code ( encoding ) and process

transformation binary code be real data ( decoding ). Testing be held to find out

comparison time compression and the size of the ratio compression of the three

algorithm. In this research be tested a text by two languages Indonesian and

English to know the influence of language by the results of compression, based

with the emergence of every character. The implementation of algorithm in this

research using language Java programming.


x

KATA PENGANTAR

Dengan kerendahan hati, penulis mengucapkan puji dan syukur atas segala

berkat dan karunia Tuhan Yesus Kristus sehingga dapat menyelesaikan tugas

akhir ini. Selama pengerjaan tugas akhir ini, penulis tidak akan bisa

menyelesaikan sendirian tanpa orang-orang hebat yang telah membantu. Terucap

terima kasih kepada :

1. Kedua orang tua, bapak Yustinus Sugito dan ibu Chatarina Sutini yang selalu

memberikan semangat dan mendoakan setiap malam untuk penulis.

2. Br. Sarju selaku ketua LKM dan Mbak Iput yang telah memberikan

kesempatan dan membantu saya untuk menyelesaikan studi ini.

3. Bapak Alb. Agung Hadhiatma, S.T., M.T. selaku dosen pembimbing yang

telah memberikan pencerahan kepada penulis sehingga dapat menyelesaikan

tugas akhir ini.

4. Ibu Sri Hartati Wijono, S.Si., M.Kom. selaku wakil kepala program studi

Teknik Informatika yang juga telah memberikan pencerahan terhadap penulis

untuk dapat menyelesaikan studi ini.

5. Bapak Drs. Haris Sriwindono, M.Kom. selaku penguji tugas akhir penulis

telah memberikan masukan dan arahan yang bermanfaat dalam penulisan

tugas akhir ini.

6. Seluruh teman-teman seperjuangan Teknik Informatika angkatan 2011, yang

telah membuat penulis tertawa dan senang ketika pusing menyelesaikan tugas

akhir ini.

7. Semua pihak, baik langsung maupun tidak, yang telah membantu

penyelesaian tugas akhir ini.

Penulis menyadari bahwa masih banyak kekurangan dalam tugas akhir ini.

Saran dan kritik diharapkan untuk perbaikan-perbaikan pada masa yang akan

datang. Semoga bermanfaat.


Penulis,



xi

DAFTAR ISI

1 HALAMAN JUDUL ...............................................................................................i

HALAMAN JUDUL (English) .............................................................................. ii

HALAMAN PERSETUJUAN ............................................................................. iii

HALAMAN PENGESAHAN ............................................................................... iv

HALAMAN PERSEMBAHAN ............................................................................ v

PERNYATAAN KEASLIAN KARYA ............................................................... vi

LEMBAR PERNYATAAN PERSETUJUAN PUBLIKASI KARYA ILMIAH

UNTUK KEPENTINGAN AKADEMIS ........................................................... vii

ABSTRAK ........................................................................................................... viii

ABSTRACT ........................................................................................................... ix

KATA PENGANTAR ............................................................................................ x

DAFTAR ISI .......................................................................................................... xi

DAFTAR GAMBAR ........................................................................................... xiv

DAFTAR TABEL ............................................................................................... xvi

1 BAB I PENDAHULUAN .............................................................................. 1

1.1 Latar Belakang .......................................................................................... 1

1.2 Rumusan Masalah ..................................................................................... 3

1.3 Tujuan ........................................................................................................ 3

1.4 Batasan Masalah ....................................................................................... 3

1.5 Manfaat Penelitian .................................................................................... 4

1.6 Luaran Penelitian ...................................................................................... 4

1.7 Sistematika Penulisan ............................................................................... 5

2 BAB II LANDASAN TEORI ....................................................................... 6

2.1 Kompresi .................................................................................................... 6

2.1.1 Pengertian ............................................................................................ 6

2.1.2 Jenis Kompresi .................................................................................... 7


xii

2.2 Struktur Data ............................................................................................ 8

2.2.1 Pohon Biner (Binary Tree) .................................................................. 9

2.2.2 Quick Sort ........................................................................................... 10

2.3 Algoritma Huffman ................................................................................. 13

2.3.1 Pohon Biner Huffman ....................................................................... 13

2.3.2 Huffman Statis ................................................................................... 16

2.3.3 Huffman Dinamis .............................................................................. 19

2.4 Dekompresi .............................................................................................. 23

3 BAB III METODOLOGI DAN PERANCANGAN ................................. 25

3.1 Metode Pengembangan Sistem .............................................................. 25

3.2 Gambaran Umum Sistem ....................................................................... 26

3.3 Analisa Kebutuhan Proses ..................................................................... 27

3.3.1 Baca Teks ........................................................................................... 28

3.3.2 Pembentukan Pohon Huffman ........................................................ 28

3.3.3 Analisis Biner ..................................................................................... 29

3.3.4 Simpan File ........................................................................................ 30

3.3.5 Baca File ............................................................................................. 33

3.3.6 Pengubahan Kode ............................................................................. 34

3.3.7 Simpan File (Proses Decoding) ........................................................ 34

3.4 Optimalisasi Algoritma Huffman .......................................................... 35

3.5 Desain User Interface .............................................................................. 38

3.6 Spesifikasi Software dan Hardware ........................................................ 39

4 BAB IV IMPLEMENTASI DAN ANALISIS ........................................... 41

4.1 Proses Encoding ....................................................................................... 41

4.1.1 Implementasi Proses Baca Teks ....................................................... 41

4.1.2 Implementasi Proses Pembentukan Pohon Biner .......................... 43

4.1.3 Implementasi Proses Analisis Biner ................................................ 47

4.1.4 Implementasi Proses Encoding ........................................................ 55

4.1.5 Implementasi Proses Simpan File Hasil Kompresi ........................ 57


xiii

4.2 Proses Decoding ....................................................................................... 62

4.2.1 Implementasi Proses Baca Teks File Kompresi ............................. 62

4.2.2 Implementasi Proses Pengubahan Kode (Decoding) ..................... 64

4.2.3 Implementasi Proses Pembentukan File Hasil Decoding .............. 68

5 BAB V PENGUJIAN DAN ANALISIS ..................................................... 70

5.1 Perbandingan Jumlah Bit ....................................................................... 70

5.2 Perbandingan Ukuran File Kompresi dan Waktu Proses .................. 73

5.3 Hubungan Peluang Kemuculan Setiap Karakter dengan Jumlah Bit

Hasil Kompresi ................................................................................................ 79

5.3.1 Data Bahasa Indonesia ..................................................................... 80

5.3.2 Data Bahasa Inggris .......................................................................... 82

6 BAB VI PENUTUP ..................................................................................... 85

6.1 Kesimpulan .............................................................................................. 85

6.2 Saran ........................................................................................................ 86

DAFTAR PUSTAKA .......................................................................................... 88


xiv

DAFTAR GAMBAR

Gambar 2.1 Penentuan pivot dan cara kerja Quick Sort ....................................... 11

Gambar 2.2 Pohon biner sempurna dan beberapa contoh pohon biner ................. 13

Gambar 2.3 Flowchart pembentukan pohon biner Huffman ................................ 14

Gambar 2.4 Hasil dari pohon Huffman ................................................................. 18

Gambar 2.5 Proses pembentukan pohon Huffman Dinamis FGK ........................ 20

Gambar 2.6 Pembentukan pohon Huffman Dinamis ............................................ 21

Gambar 2.7 Proses dekompresi dengan pohon Huffman ...................................... 24

Gambar 3.1 Diagram konteks ............................................................................... 27

Gambar 3.2 Block diagram encoding.................................................................... 27

Gambar 3.3 Block diagram decoding.................................................................... 28

Gambar 3.4 Pembentukan pohon Huffman modifikasi......................................... 37

Gambar 3.5 Interface encoding ............................................................................. 38

Gambar 3.6 Interface decoding ............................................................................. 39

Gambar 4.1 Implementasi proses memilih file encoding ...................................... 42

Gambar 4.2 Implementasi proses membaca file encoding .................................... 42

Gambar 4.3 Implementasi pembentukan pohon Huffman Statis .......................... 43

Gambar 4.4 Implementasi pembentukan pohon Huffman Dinamis ..................... 44

Gambar 4.5 Implementasi pembentukan pohon Huffman Modifikasi ................. 46

Gambar 4.6 Source code kelas KodeHuffman.java .............................................. 48

Gambar 4.7 Implementasi analisis biner Huffman Statis dan Modifikasi ............ 49

Gambar 4.8 Implementasi analisis biner Huffman Statis method find() .............. 50

Gambar 4.9 Implementasi analisis biner Huffman Modifikasi method find() . 51-52

Gambar 4.10 Implementasi analisis biner Huffman Dinamis ............................... 53

Gambar 4.11 Implementasi analisis biner Huffman Dinamis .............................. 54

Gambar 4.12 Implementasi encoding Huffman Statis dan Dinamis ..................... 55

Gambar 4.13 Implementasi encoding Huffman Modifikasi ................................. 56

Gambar 4.14 Implementasi preprocessing ........................................................... 58

Gambar 4.15 Implementasi proses simpan file log ............................................... 60


xv

Gambar 4.16 Implementasi proses simpan file kompresi ..................................... 61

Gambar 4.17 Implementasi proses memilih file decoding .................................... 62

Gambar 4.18 Implementasi proses membaca file decoding .................................. 63

Gambar 4.19 Implementasi proses decoding header ............................................ 64

Gambar 4.20 Implementasi proses decoding isi ................................................... 65

Gambar 4.21 Implementasi proses decoding Huffman Dinamis dan Statis.......... 66

Gambar 4.22 Implementasi proses decoding Huffman Modifikasi ...................... 67

Gambar 4.23 Implementasi proses pembentukan file decoding............................ 68

Gambar 5.1 Kelas pengujian perbandingan jumlah bit ......................................... 71

Gambar 5.2 Capture hasil pengujian jumlah bit ................................................... 71

Gambar 5.3 Lanjutan capture hasil pengujian jumlah bit ..................................... 72

Gambar 5.4 Frame pengujian jumlah bit dan ratio compression ......................... 73

Gambar 5.5 Tampilan awal aplikasi ...................................................................... 74

Gambar 5.6 Tampilan klik browse untuk memilih file ......................................... 74

Gambar 5.7 Tampilan encoding untuk memilih salah satu algoritma .................. 75

Gambar 5.8 Tampilan loading proses encoding .................................................... 75

Gambar 5.9 Pemberitahuan jika proses encoding berhasil ................................... 76

Gambar 5.10 Grafik waktu yang dibutuhkan untuk kompresi .............................. 78

Gambar 5.11 Grafik ukuran file hasil kompresi .................................................... 78


xvi

DAFTAR TABEL

Tabel 2.1 Tabel kode Huffman ............................................................................. 18

Tabel 5.1 Tabel hasil perbandingan jumlah bit ..................................................... 72

Tabel 5.2 Tabel hasil pengujian jumlah bit dan ratio compression ...................... 73

Tabel 5.3 Data ukuran file pengujian .................................................................... 77

Tabel 5.4 Tabel hasil pengujian ............................................................................ 77

Tabel 5.5 Hasil pengujian jumlah bit data bahasa Indonesia ................................ 81

Tabel 5.6 Peluang karakter terbanyak data bahasa Indonesia ............................... 81

Tabel 5.7 Hasil pengujian jumlah bit data bahasa Inggris .................................... 83

Tabel 5.8 Peluang karakter terbanyak data bahasa Inggris ................................... 83


1

1 BAB I

PENDAHULUAN

1.1 Latar Belakang

Pada zaman sekarang ukuran suatu file menjadi bertambah semakin besar

dan membutuhkan memori penyimpanan yang lebih serta membutuhkan waktu

transfer yang lama. Ukuran file yang besar tidak terlalu menjadi masalah karena

ukuran hard disk semakin lama semakin besar dengan harga yang semakin

terjangkau. Tetapi jika mengenai file transfer, masalah ukuran file yang besar

menjadi penghambat dalam waktu transfer yang menjadi semakin lama.

Dalam bidang ilmu komputer, permasalahan kompresi data sudah menjadi

kasus klasik dan telah muncul beberapa algoritma dalam mengatasi permasalahan

tersebut. Beberapa algoritma yang ada antara lain algortima Huffman, Shannon-

Fano, Lempel Ziv Welch (LZW), Lempel Ziv Storer Szymanski (LZSS) dan masih

banyak algoritma lainnya. Namun pada skripsi ini, lebih dibahas tentang algoritma

Huffman. Kenapa memilih algoritma Huffman, karena algoritma Huffman

merupakan dasar dari berbagai algoritma pengkompresian serta algoritma yang

paling sederhana. Algoritma Huffman pertama kali diperkenalkan oleh David A.

Huffman pada tahun 1952 yang menanggapi tantangan oleh dosennya Robert M.

Fano untuk membuat sebuah pohon biner yang efisien. Dalam algoritma Huffman,

ada dua macam tipe algoritma yaitu algoritma Huffman Statis dan algoritma

Huffman Dinamis. Algoritma Huffman Dinamis lebih mudah dan fleksibel dalam


2

pembuatan Huffman Tree karena pohon Huffman akan otomatis berubah

menyesuaikan kode yang sering muncul dan akan ditempatkan di dekat root

sehingga tidak membutuhkan waktu preprocessing yang lama. Hal ini berbeda

dengan algoritma Huffman Statis yang harus melakukan preprocessing dengan

memindai setiap karakter dan mengurutkannya dari yang paling sering muncul

sampai yang paling sedikit muncul.

Dalam ilmu komputer dan informasi, Huffman coding adalah suatu entropi

algoritma yang digunakan untuk teknik lossless compression [3]

. Data yang

dikompres menggunakan algoritma ini akan menghasilkan hasil dekompresi yang

sama dengan aslinya. Penggunaan teknik ini banyak digunakan untuk kompresi

data teks serta informasi penting lainnya yang tidak diperbolehkan adanya data

informasi yang hilang.

Saat ini telah banyak tulisan yang mengangkat kasus tentang kompresi data

dengan berbagai macam algoritma yang ada. Banyak yang mengangkat kasus

tersebut dengan cara membandingkan efficiency dari algoritma-algoritma yang

ada, implementasi algoritma dengan menggabungkan dua algoritma kompresi dan

membandingkan kompleksitas dari semua algoritma. Dalam tulisan ini akan

dibahas tentang algoritma Huffman yang akan diimplementasikan pada data teks.

Dengan penggunaan algoritma Huffman sebagai dasar dari penelitian ini, maka

modifikasi untuk pengoptimalan akan dilakukan mengingat juga posisi algoritma

Huffman seperti yang telah disebutkan sebelumnya. Pengujian dalam penelitian

ini akan dilakukan untuk algoritma Huffman Statis, Huffman Dinamis dan

pengembangan algoritma Huffman. Sehingga nantinya akan didapat sebuah


3

pengembangan algoritma dari Huffman yang dapat berguna bagi optimalisasi

transfer data dan mengoptimalkan kapasitas penyimpanan memori.

1.2 Rumusan Masalah

Berdasarkan latar belakang yang dipaparkan sebelumnya maka dapat dibuat

beberapa rumusan masalah antara lain:

1. Bagaimana cara mengecilkan ukuran suatu file teks untuk mempercepat

transfer data antar media penyimpanan?

2. Bagaimana cara mengecilkan ukuran suatu file teks untuk mempercepat proses

upload atau download?

3. Bagaimana cara mengecilkan ukuran suatu file teks untuk menghemat

kapasitas memori penyimpanan serta mengoptimalkan kapasitas memori?

1.3 Tujuan

Tujuan dari penelitian ini adalah menemukan optimalisasi dari algoritma

Huffman untuk kompresi data teks sebagai suatu cara untuk mempercepat proses

transfer antar media penyimpanan, serta untuk menghemat dan mengoptimalkan

kapasitas memori penyimpanan.

1.4 Batasan Masalah

Dalam penelitian ini, penulis menentukan beberapa batasan masalah untuk

mempersempit lingkup permasalahan, antara lain :


4

1. Algoritma yang dibahas dalam tulisan ini hanya digunakan untuk data

bertipe teks. Data yang dimaksud adalah data berisi huruf, angka atau karakter

yang terdapat dalam standar ASCII.

2. Data teks yang digunakan hanya untuk file betipe .TXT (Text Document).

1.5 Manfaat Penelitian

Manfaat yang didapat dari penelitian ini, antara lain :

1. Memberikan analisis sejauh mana algoritma Huffman dapat

dikembangkan untuk menghasilkan algoritma kompresi yang lebih baik.

2. Membantu masyarakat dalam melakukan pengoptimalan memori

penyimpanan serta mempermudah dan mempercepat dalam proses transfer

(upload dan download) suatu file teks.

1.6 Luaran Penelitian

Luaran penelitian ini adalah sebuah algoritma kompresi file teks yang

merupakan pengembangan dari algoritma Huffman. Selain itu, produk yang

didapat adalah sebuah aplikasi untuk menjalankan ketiga algoritma.


5

1.7 Sistematika Penulisan

BAB I PENDAHULUAN

Berisi latar belakang, rumusan masalah, tujuan, batasan masalah, manfaat

penelitian, luaran penelitian dan sistematika penulisan untuk mempermudah

pemahamannya.

BAB II LANDASAN TEORI

Bab ini berisi mengenai berbagai macam landasan teori yang digunakan

untuk penelitian ini.

BAB III METODOLOGI DAN PERANCANGAN

Bab ini berisi analisa dan gambaran umum dari perancangan algoritma yang

akan dibuat dari pengembangan algoritma Huffman.

BAB IV IMPLEMENTASI

Berisi implementasi dari algoritma serta rancangan yang telah dibuat.

BAB V PENGUJIAN DAN ANALISIS

Berisi pengujian dari algoritma yang telah dibuat kedalam beberapa kondisi

pengujian.

BAB VI PENUTUP

Berisi kesimpulan yang diperoleh dari keseluruhan proses pembuatan tugas

akhir ini, serta beberapa saran yang dapat digunakan untuk pengembangan

algoritma lebih lanjut.


6

2 BAB II

LANDASAN TEORI

Pada bab ini penulis akan membahas serta menjelaskan mengenai teori-

teori yang mendukung penelitian dalam proses analisa dan implementasi

algoritma. Hal yang dibahas mencakup : pengertian kompresi file, jenis-jenis

kompresi file, struktur data, binary tree, pengurutan data, algoritma Huffman

Statis dan algoritma Huffman Dinamis.

2.1 Kompresi

2.1.1 Pengertian

Kompresi adalah mengurangi jumlah data dalam file, gambar atau video

tanpa mengurangi kualitas dari data asli. Itu juga berarti mengurangi jumlah bit

yang diperlukan untuk menyimpan dan atau mengirimkan melalui media digital[1]

.

Dalam kompresi, jika data tersebut akan dipergunakan kembali maka harus

dilakukan proses dekompresi. Dekompresi adalah suatu proses pengubahan

kembali kode-kode yang digunakan untuk mengurangi jumlah bit menjadi data

awal.

Pemilihan algoritma yang tepat dalam kompresi tidak hanya bagaimana

algoritma itu dapat mengembalikan data menjadi seperti semula, tetapi ada

beberapa faktor lain yang dipertimbangkan. Faktor tersebut antara lain :

1. Sumber daya yang dibutuhkan (memori, kecepatan komputer)


7

2. Kecepatan kompresi

3. Ukuran hasil kompresi

4. Besarnya redudansi

5. Ketepatan hasil dekompresi

6. Kompleksitas algoritma

2.1.2 Jenis Kompresi

Teknik kompresi itu sendiri terdiri dari dua jenis yaitu Lossless

Compression dan Lossy Compression. Kedua jenis kompresi tersebut akan

dijelaskan sebagai berikut :

2.1.2.1 Lossless Compression

Jika data dikompresi menggunakan teknik Lossless Compression, hasil

dekompresiakan menghasilkan data yang sama dengan aslinya. Teknik ini biasa

digunakan untuk aplikasi yang tidak diperbolehkan adanya perbedaan antara data

asli dengan data hasil dekompresi. Contoh : ZIP, RAR, GZIP, 7-ZIP.

Kelemahan dari metode ini adalah ratio kompresi yang rendah. Rasio

dapat dihitung dengan persamaan :

𝑅𝑎𝑠𝑖𝑜 = (1 −𝑈𝑘𝑢𝑟𝑎𝑛 𝑘𝑜𝑚𝑝𝑟𝑒𝑠𝑖

𝑈𝑘𝑢𝑟𝑎𝑛 𝑎𝑠𝑙𝑖) 𝑥 100%

Penerapan algoritma ini biasanya dilakukan pada data teks yang tidak

diperbolehkan adanya bit yang hilang, serta pada kompresi citra medis. Oleh


8

karena itu secara umum, compression ratio yang tinggi tidak akan mungkin terjadi

jika menggunakan teknik lossless compression[2]

.

2.1.2.2 Lossy Compression

Teknik Lossy Compression memperbolehkan adanya informasi dan data

yang hilang setelah proses dekompresi. Contoh : MP3, JPEG, MPEG dan WMA.

Kelebihan dari teknik ini adalah ukuran file yang lebih kecil namun

masih dapat memenuhi syarat setelah di dekompresi. Teknik ini sebenarnya

membuang bagian-bagian yang tidak berguna, tidak begitu dirasakan dan tidak

begitu dilihat sehingga manusia masih beranggapan bahwa data tersebut masih

memenuhi syarat dan masih bisa digunakan.

Jika dilihat dari contoh di atas, sebagian besar produk hasil dari teknik ini

merupakan file multimedia seperti lagu, gambar dan video. Hal itu didasarkan

karena file multimedia hanya untuk didengar atau dilihat, sehingga data yang

hilang tidak akan terlalu mempengaruhi selagi masih dalam batas wajar.

2.2 Struktur Data

Dalam penelitian ini, salah satu konsep terpenting yang diambil dari ilmu

komputer adalah struktur data. Struktur data merupakan sebuah cabang dari ilmu

komputer yang mempelajari tentang cara dan algoritma dalam pengolahan data.

Dalam algoritma Huffman, struktur data merupakan dasar terpenting di mana

pembentukan pohon biner tersebut diambil dari konsep struktur data.


9

Selain konsep pohon biner, dalam algoritma Huffman juga terdapat konsep

pengurutan data. Pengurutan data digunakan untuk preprocessing dalam algoritma

Huffman Statis di mana setelah data di cek frekuensi kemunculannya, maka data

akan diurutkan secara descending (dari besar ke kecil). Seperti yang telah dibahas

sebelumnya, data dengan kemunculan terbanyak ditempatkan dekat dengan akar.

2.2.1 Pohon Biner (Binary Tree)

Sebuah pohon biner terbuat dari titik – titik (nodes), di mana setiap titik

mempunyai pointer kiri dan kanan serta data element. Pointer akar terletak di

paling atas dari pohon. Pointer kiri dan kanan secara rekursif membentuk subtree

[5].

Dalam setiap pohon biner, terdapat sifat – sifat pohon antara lain [8]

:

1. Node / simpul : obyek sederhana elemen dari senarai berantai yang dapat

memiliki elemen dan penunjuk ke node lain.

2. Edge : garis yang menghubungkan dua buah node.

3. Path : sederetan node / edge dari awal node ke node lain (target).

4. Root node : node pertama dalam sebuah tree / subtree.

5. Subtree : tree yang merupakan bagian dari sebuah tree yang lebih besar.

6. Left Subtree : subtree yang berada di sebelah kiri sebuah tree.

7. Right subtree : subtree yang berada di sebelah kanan sebuah tree.

8. Parent : node yang berada tepat di atas sebuah node.

9. Child : node yang berada tepat di bawah sebuah node.


10

10. Left Child : node pertama dalam seuah left subtree / parentnode dari left

subtree.

11. Right Child : node pertama dalam seuah right subtree / parentnode dari

right subtree.

12. Sibling : node dengan parent yang sama.

13. Leaf Node / terrminal simpul : node yang tidak memiliki child.

14. Internal Node : node yang bukan leaf node.

Pohon biner secara umum mempunyai ciri bahwa setiap node hanya

mempunyai anak paling banyak dua. Sering kali pohon biner yang baik dan

sempurna adalah pohon biner yang seimbang. Pohon biner seimbang yaitu pohon

yang mempunyai tinggi subtree kanan dan kiri tidak lebih dari satu, semua daun

terisi dan semua simpul memiliki dua anak [8]

.

2.2.2 Quick Sort

Salah satu metode dalam pengurutan data adalah Quick Sort. Pengurutan

merupakan salah satu konsep dari struktur data yang digunakan dalam mengolah

data. Pengurutan itu sendiri dapat dibedakan menjadi dua yaitu ascending

(pengurutan dari data terkecil ke data terbesar) dan descending (pengurutan dari

data terbesar ke data terkecil). Banyak algoritma pengurutan yang ada seperti

bubble sort, selection sort, insertion sort, dan merge sort . Ide dasar metode quick

sort adalah mempartisi array ke dalam subarray kiri dan subarray kanan sehingga

setiap elemen di subarray kiri lebih kecil dari setiap elemen di subarray kanan [9]

.


11

Dari ide dasar metode quick sort tersebut, dapat dipahami bahwa inti dari

pengurutannya adalah membagi data menjadi dua bagian. Cara kerja quick sort [9]

:

1. Tentukan elemen sebagai pivot dari array, misalkan elemen awal.

2. Atur array sehingga semua elemen yang lebih kecil atau sama dengan

pivot di sebelah kiri pivot dan semua elemen yang lebih besar dari pivot berada di

sebelah kanan.

3. Secara rekursif quick sort subarray (kiri) dengan elemen yang lebih kecil

atau sama dengan dari pivot dan subarray (kanan) dengan elemen yang lebih besar

dari pivot.

Gambar 2.1 Penetuan pivot dan cara kerja Quick Sort

Menurut gambar cara kerja quick sort di atas, penentuan sebuah pivot atau

titik acuan didasarkan pada elemen awal dalam array. Penentuan ini akan terus

dilakukan pada setiap hasil pembagian data hingga tidak ada array yang tersisa


12

atau dengan kata lain semua data berdiri sendiri. Algoritma quick sort itu sendiri

adalah sebagai berikut [9]

:

Larik A dengan N elemen akan diurutkan secara menaik (ascending).

Pemanggilan fungsi quick sort rekursif dengan parameter array x, indek awal dan

indek akhir.

Parameter : x adalah array bertipe int.

awal = indek awal dari vektor / subvektor yang akan diurutkan =

0

akhir = indek akhir dari vektor / subvektor yang akan diurutkan =

N-1

Test apakah indek awal < akhir, jika ya kerjakan langkah – langkah sebagai

berikut:

Langkah 1 : tentukan i = awal + 1, j = akhir.

Langkah 2 : tambahkan nilai i dengan 1 selama i <= akhir dan x[i] <= x[awal].

Langkah 3 : kurangi nilai j dengan 1 selama j > awal dan x[j] > x[awal].

Langkah 4 : kerjakan langkah 5 sampai 7 selama i < j.

Langkah 5 : tukarkan nilai x[i] dengan x[j].

Langkah 6 : tambahkan nilai i dengan 1 selama i <= akhir dan x[i] <= x[awal].

Langkah 7 : kurangi nilai j dengan 1 selama j > awal dan x[j] > x[awal].

Langkah 8 : tukarkan nilai x[awal] dengan x[j].

Langkah 9 : panggil fungsi quick sort rekursif dengan parameter indek awal =

awal dan indek akhir = j -1.


13

Langkah 10 : panggil fungsi quick sort rekursif dengan parameter indek awal =

j + 1 dan indek akhir = akhir.

Langkah 11 : selesai.

2.3 Algoritma Huffman

2.3.1 Pohon Biner Huffman

Pohon adalah graf tak-berarah terhubung yang tidak mengandung sirkuit.

Sedangkan pohon biner adalah pohon berakar dimana setiap simpul cabangnya

mempunyai paling banyak dua anak. Pohon biner teratur adalah pohon biner

dimana setiap simpul cabangnya mempunyai dua buah anak[4]

.

Gambar 2.2 Pohon biner sempurna dan beberapa contoh pohon biner

Kompresi data pada pengkodean Huffman didasarkan pada frekuensi

kemunculan setiap karakternya. Struktur data yang terbentuk pada algoritma

Huffman adalah pohon biner berbobot, dimana skema pengkodeannya dapat

dilihat dari flowchart berikut :


14

Gambar 2.3 Flowchart pembentukan pohon biner Huffman

Dari pohon biner tersebut dapat diperoleh bahwa karakter dengan peluang

kemunculan terbesar memiliki jumlah bit yang kecil. Setelah terbentuk pohon

biner tersebut, maka karakter data asli tersebut diganti dengan kode bit

berdasarkan pohon biner tadi. Proses ini dinamakan encoding.

Semua data yang di kompresi harus dikembalikan lagi menjadi data

semula (decoding). Dalam Huffman terdapat 2 cara untuk melakukan decoding

yaitu menggunakan pohon biner atau menggunakan tabel kode.


15

2.3.1.1 Menggunakan Pohon Biner Huffman

Langkah-langkah yang dilakukan dalam proses decoding dengan pohon

biner Huffman adalah :

a. Baca bit pertama dari string biner masukan

b. Lakukan traversal pada pohon Huffman mulai dari akar sesuai dengan bit

yang dibaca. Jika bit yang dibaca adalah 0, baca anak kiri. Tetapi jika yang

dibaca adalah 1, baca anak kanan.

c. Jika anak dari pohon bukan daun, baca bit berikutnya dari string biner.

d. Traversal hingga ditemukan daun.

e. Pada daun tersebut, simbol ditemukan dan proses penguraian kode selesai.

f. Proses penguraian kode dilakukan hingga seluruh string biner masukan

diproses.

2.3.1.2 Menggunakan Tabel Kode Huffman

Kode Huffman itu sendiri disusun menggunakan kode awalan (prefiks

code) yang berarti kode awalan dari sebuah simbol/karakter tidak boleh menjadi

awalan suatu simbol lain. Oleh karena itu rangkaian bit hasil enkripsi dapat

dengan mudah diuraikan menjadi data semula. Yang perlu dilakukan hanyalah

melihat rangkaian setiap bit hasil enksripsi di dalam tabel kode Huffman.

Kompleksitas dari algoritma Huffman adalah T(𝑛) = 𝑂(𝑛 log 𝑛).

Dikarenakan dalam sekali proses iterasi, pada saat penggabungan dua buah pohon

yang mempunyai frekuensi terkecil pada sebuah akar membutuhkan waktu


16

𝑂(log 𝑛), dan proses tersebut dilakukan berulang kali sampai hanya tersisa satu

buah pohon Huffman, yang berarti dilakukan sebanyak n kali [5]

.

2.3.2 Huffman Statis

Algoritma Huffman Statis merupakan algoritma dasar dari Huffman

Coding. Untuk mendapatkan kode Huffman, mula-mula kita harus menghitung

dahulu peluang kemunculan tiap karakter dalam teks. Pada Huffman Statis

pembentukan pohon Huffman adalah sebagai berikut :

1. Pilih dua karakter dengan peluang terkecil. Kedua simbol tadi

dikombinasikan sebagai simpul orangtua sehingga menjadi simbol 2

karakter dengan peluang yang dijumlahkan.

2. Selanjutnya pilih 2 simbol berikutnya termasuk simbol baru yang

mempunyai peluang terkecil.

3. Prosedur yang sama dilakukan pada dua simbol berikutnya yang

mempunyai peluang terkecil [4]

.

Contoh :

Data teks : EBCDAAEA = 8 huruf

Membutuhkan memori : 8 x 8 bit = 64 bit (8 byte)

Kode ASCII :

E = 01000101

B = 01000010

C = 01000011

D = 01000100


17

A = 01000001

A = 01000001

E = 01000101

A = 01000001

Frekuensi kemunculan data string di atas A = 3, E = 2, B=1, C = 1 dan D

= 1.

Maka peluang yang didapat :

C dan D menjadi 1 (CD) sehingga probabilitas menjadi 1/8 + 1/8 =

2/8

CD dan B menjadi 1 (BCD) sehingga probabilitas menjadi 1/8 + 2/8

= 3/8

BCD dan E menjadi 1 (EBCD) sehingga probabilitas menjadi 2/8 +

3/8 = 5/8

EBCD dan A menjadi 1 (AEBCD) sehingga probabilitas menjadi 3/8

+ 5/8=8/8

Probabilitas yang lebih besar akan diletakkan di sebelah kiri dan paling

dekat dengan robot. Maka hasil pohon Huffman adalah sebagai berikut :


18

A

E

B

DC

EABCD

ABCD

BCD

CD

1

1

1

1

0

0

0

0

Gambar 2.4 Hasil dari pohon Huffman

Huruf Kode

A 1

E 01

B 001

C 0000

D 0001

Tabel 2.1 Tabel Kode Huffman

Dengan melakukan pengkodean di atas, maka didapat sebuah kode yang

sangat pendek. Sebagai contoh untuk karakter A yang sebelumnya berjumlah 8 bit

hanya menjadi 1 bit.

Sehingga kapasitas memori yang diperlukan :

Sebelum : 8 x 8 bit = 64 bit

Sesudah : (3 x 1 bit) + (2 x 2 bit) + (1 x 3 bit) + (2 x 4 bit) = 3 + 4 + 3 + 8 = 18 bit


19

2.3.3 Huffman Dinamis

Algoritma Huffman Dinamis atau Adaptive Huffman Coding (AHC)

merupakan suatu lanjutan dari algoritma Huffman Statis di mana AHC merupakan

algoritma yang lebih efisien dan mampat. AHC lebih sering dilakukan pada proses

transfer data (streaming). Berikut algoritma AHC FGK (Faller-Gallager-Knuth)[6]

:

1. Buat suatu simbol yang bernama NYT (Not Yet Transmitted) atau berarti

belum ditransmisi.

2. Jika simbol adalah NYT, tambahkan 2 anak NYT tersebut, satunya akan

menjadi NYT baru dan yang lainnya adalah untuk simbol, akan

menambahkan nilai dari NYT akar dan daun akan terbentuk. Jika daun

baru terbentuk lanjutkan langkah 4, jika telah ada sebelumnya periksa dulu

di langkah 3.

3. Jika simbol yang dimasukan terakhir memiliki probabilitas yang lebih

tinggi maka akan ditukar dengan yang sebelumnya menempati tempat

kemunculan tertinggi.

4. Tambahkan nilai dari akar tersebut.

5. Jika bukan akar, kembali ke akar inang lalu lanjutkan ke langkah 2, selain

itu selesai.

Dari algoritma di atas, maka dapat di masukan ke dalam contoh berikut.

Contoh :


20

Gambar 2.5 Proses pembentukan pohon Huffman Dinamis FGK

1. Pohon Huffman kosong dan berisi NYT 256 (2 byte).

2. Karakter pertama adalah a, dan disimpan pada anak NYT 256 yang

bobotnya bertambah 1 dan menambah anak NYT 254. Simbol a memiliki

bobot 1 dengan alamat 255.

3. Karakter kedua adalah b, dan disimpan pada anak NYT 254. Simbol b

memiliki bobot 1 dengan alamat 253 serta NYT 254 memiliki anak NYT

252.

4. Karakter berikutnya adalah b lagi, maka akan dimasukan ke 253 (proses

searching) dan bobotnya menjadi 2. Lalu dibandingkan dengan karakter a,

karena bobot b lebih besar dari a maka posisi a dan b ditukar.

Dari pohon di atas maka dapat disimpulkan bahwa karakter A memiliki

code “01” dan karakter B memiliki code “1”.

Dari contoh Huffman Dinamis FGK di atas, dapat diterapkan pada data

yang sama EBCDAAEA yaitu dengan langkah-langkah sebagai berikut :


21

E1

B1

C1

4

D1

E1

B1

C1

5

D1

A1

A2

B1

C1

6

D1

E1

E1

1

E1

B1

2

E1

B1

3

C1

A2

E2

C1

7

D1

B1

A3

E2

C1

8

D1

B1

Gambar 2.6 Pembentukan pohon Huffman Dinamis

1. Karakter pertama ‘E’ masuk, dan menempati posisi dekat dengan akar.

Bobot atau jumlah ‘E’ adalah 1.

2. Karakter kedua ‘B’ masuk dan mengecek posisi, karena posisi dekat

dengan akar sudah ditempati ‘E’ maka ‘B’ membentuk posisi di bawah

‘E’. Bobot karakter ‘B’ adalah 1.


22

3. Karakter ketiga ‘C’ masuk maka akan mengecek dan membuat posisi di

bawah ‘B’. Bobot karakter ‘C’ adalah 1.

4. Karakter keempat ‘D’ masuk maka akan mengecek dan membuat posisi di

bawah ‘C’. Bobot karakter ‘D’ adalah 1.

5. Karakter kelima ‘A’ masuk maka akan mengecek dan membuat posisi di

bawah ‘D’. Bobot karakter ‘A’ adalah 1.

6. Karakter keenam ‘A’ masuk dan akan mengecek setiap node. Karena

karakter ‘A’ sudah membuat node di posisi paling bawah maka bobot ‘A’

akan bertambah menjadi 2. Perubahan bobot ini akan mengubah posisi ‘A’

menjadi dekat dengan akar dan bertukar posisi dengan karakter ‘E’.

7. Karakter ketujuh ‘E’ masuk dan mengecek setiap node. Karakter ‘E’ juga

telah dibuat maka bobot ‘E’ bertambah menjadi 2. Karakter ‘E’ kembali

mengecek dari akar untuk mengubah posisi. Posisi dekat akar telah

ditempati ‘A’ dengan bobot sama, maka ‘E’ mengecek dengan turun satu

node. Karakter ‘B’ dengan bobot 1 ditukar posisinya dengan karakter ‘E’ .

Memang secara posisi pohon antara algoritma Huffman Statis dan

Dinamis hampir sama, hanya saja lebih efisien Huffman Dinamis. Hal itu didapat

karena peletakan daun pada Huffman Dinamis yang terus berubah-ubah (dynamic)

dalam menentukan jumlah kemunculan tiap karakter. Dibandingkan dengan

Huffman Statis yang terlebih dahulu harus menghitung peluang kemunculan tiap

karakter.


23

2.4 Dekompresi

Proses dekompresi (decoding) merupakan suatu proses kebalikan dari

proses kompresi (encoding). Dimana kode hasil kompresi dikembalikan dan

disusun kembali seperti data awal. Proses dekompresi seperti yang telah

disebutkan di awal, dapat dilakukan dengan 2 cara yaitu dengan menggunakan

pohon Huffman atau dengan tabel Huffman. Langkah-langkah dekompresi string

biner dengan pohon Huffman adalah sebagai berikut[7]

:

1. Baca sebuah bit dari string biner.

2. Mulai dari akar.

3. Periksa kiri.

4. Periksa kanan.

5. Ulangi langkah 1,2 dan 3 sampai bertemu daun. Kodekan rangkaian bit

yang telah dibaca dengan karakter di daun.

6. Ulangi dari langkah 1 sampai semua bit di dalam string habis.

Sebagai contoh sebuah biner “01001” akan di dekompresi, dengan pohon

biner seperti Gambar 2.3 .


24

Gambar 2.7 Proses dekompresi dengan pohon Huffman

Dengan menggunakan algoritma di awal tadi, maka jika kita telusuri dari

akar ditemukan bahwa kode “01” merupakan B dan kode “001” merupakan D.

Hal ini dengan mudah ditemukan karena dalam Huffman kode akhir suatu biner

bukan merupakan kode awalan biner lain. Jadi kode “01001” adalah kode

Huffman untuk string BD.

Jika kita dekompresi dengan cara kedua, yaitu menggunakan tabel Huffman,

seperti pada Tabel 2.1 akan lebih mudah dibandingkan daripada dengan

menggunakan pohon Huffman. Kita hanya harus mencari kode “01” dan “001”

tersebut dimiliki oleh karakter apa. Proses dekompresi algoritma Huffman relatif

mudah dibandingkan dengan algoritma lainnya.


25

3 BAB III

METODOLOGI DAN PERANCANGAN

Pada bab analisis dan desain ini akan dibahas mengenai analisa terhadap

kompresi data teks dengan algoritma Huffman serta desain program yang akan

dibuat. Hal–hal yang dibahas antara lain proses–proses yang dibutuhkan dalam

penelitian meliputi beberapa hal : gambaran umum sistem yang akan

dikembangkan, prosedur pengembangan sistem, gambaran algoritma

pengembangan dari Huffman, model analisis dan model desain.

3.1 Metode Pengembangan Sistem

Metodologi pengembangan yang penulis gunakan untuk pembuatan sistem

ini adalah metodologi model waterfall. Terdapat beberapa tahapan dalam

metodologi tersebut, antara lain :

1. System Engineering

Pada tahap ini merupakan tahap untuk mengumpulkan dan menentukan

semua kebutuhan elemen sistem.

2. Analisis

Pada tahap untuk menentukan analisis terhadap permasalahan yang

dihadapi.

3. Desain


26

Gambaran program yang akan diterjemahkan menjadi sebuah sistem.

Meliputi desain tampilan, diagram konteks dan block diagram.

4. Implementasi

Proses menterjemahkan desain ke dalam bentuk yang dapat dieksekusi.

Pada tahap ini juga merupakan proses coding program.

5. Pengujian

Memastikan apakah semua fungsi-fungsi program dapat berjalan dengan

baik dan menghasilkan output yang sesuai dengan yang dibutuhkan.

3.2 Gambaran Umum Sistem

Sistem yang akan dibangun merupakan sebuah sistem berbasis Java dengan

Netbeans sebagai Intregated Development Environment (IDE). Secara umum

sistem yang berjalan akan menitikberatkan pada operasi algoritma Huffman

sebagai proses kompresi dan dekompresi data. Dalam sistem ini hanya terdapat

satu tipe data yang digunakan sebagai masukan user yaitu data teks dengan

keluaran hasil dari sistem adalah sebuah file hasil kompresi data masukan

tersebut.

Aktivitas yang dilakukan antara user dan sistem dapat digambarkan pada

diagram konteks berikut :


27

UserSistem

Kompresi Data

1. Data teks

2. File hasil kompresi

1. File hasil kompresi

2. Data teks

Gambar 3.1 Diagram konteks

Selain masukan berupa data teks, dari diagram konteks tersebut user juga

bisa memasukan file hasil kompresi agar dapat di dekompresi kembali menjadi

data teks sebagai keluarannya. File hasil kompresi yang akan digunakan sebagai

masukan adalah file kompresi hasil dari sistem ini, karena file tipe hasil kompresi

sistem ini akan berbeda dari sistem kompresi yang lain.

3.3 Analisa Kebutuhan Proses

Setelah melihat gambaran umum sistem, maka tahap selanjutnya adalah

menganalisa semua proses yang dibutuhkan dalam sistem. Terdapat dua proses

sistem yaitu proses encoding dan decoding. Gambaran proses tersebut akan di

tampilkan dalam block diagram berikut :

Gambar 3.2 block diagram encoding


28

Gambar 3.3 block diagram decoding

Dari gambar detail proses encoding dan decoding tersebut maka diperoleh

beberapa proses di dalamnya antara lain : baca teks, pembentukan pohon

Huffman, analisis biner, simpan file, baca file dan pengubahan kode.

3.3.1 Baca Teks

Proses baca teks merupakan sebuah proses awal dimana user memilih data

yang akan di kompresi. Data yang dipilih hanya tipe data yang sesuai dengan

batasan masalah seperti telah disebutkan pada bab 1. Proses pemilihan

menggunakan kelas JFileChooser yang merupakan kelas bawaan pada Java untuk

membuka kotak dialog browse file.

File yang telah dipilih, akan di read setiap byte secara detail. Proses baca

akan membaca secara keseluruhan seperti karakter spasi, tanda baca hingga enter.

Hasil dari proses ini adalah berupa Arraylist bertipe String yang akan diolah

diproses selanjutya.

3.3.2 Pembentukan Pohon Huffman

Setelah proses baca teks dilakukan, maka proses selanjutnya adalah

pembentukan pohon Huffman. Proses ini saya sebut sebagai inti dari proses


29

encoding karena dari data teks tersebut disusun sebuah pohon biner Huffman

untuk membuat sebuah kode baru yang lebih singkat untuk masing-masing

karakter.

Proses ini akan berbeda di setiap algoritma, karena pembentukan pohon

biner yang memiliki ciri khas di masing-masing algoritma.Arraylist hasil proses

baca teks akan di loop dan diambil setiap karakternya lalu dibentuk pohon

binernya. Setelah terbentuk pohon biner, maka akan di identifikasi setiap karakter

beserta kode yang baru. Hasil proses identifikasi dimasukan ke dalam Arraylist

objek sebuah kelas yang berisi atribut karakter dan kode karakter. Hasil tersebut

juga merupakan keluaran dari proses ini.

3.3.3 Analisis Biner

Proses analisis biner adalah suatu proses yang meliputi proses identifikasi

kode baru tiap karakter serta proses pembentukan rangkaian kode biner baru.

Proses ini dapat juga disebut sebagai proses pembentukan sebuah file baru hasil

kompresi data yang dimasukan.

Hasil dari proses pembentukan pohon Huffman yang berupa

Arraylistobjek berisi karakter dan kode, akan di cocokan satu per satu dengan tiap

karakter hasil dari proses baca teks yang berupa Arraylist String. Hasil dari proses

ini adalah sebuah String yang berisi deretan kode 1 dan 0. Kode inilah merupakan

kode karakter yang baru dari setiap karakter pada teks.


30

3.3.4 Simpan File

Proses simpan file adalah sebuah proses untuk menyimpanan file hasil

kompresi tersebut atau dengan kata lain file yang telah di buat dalam proses

analisis biner akan di-stream di media penyimpanan.

Dalam proses ini terdapat 3 sub proses di dalamnya, proses-proses tersebut

antara lain stream byte, simpan log, dan buat file kompresi.

3.3.4.1 Simpan Log

Proses simpan log ini merupakan sebuah proses yang saya buat untuk

menyimpan tabel kode (Arraylist objek) dari hasil proses pembentukan pohon

Huffman. Proses ini nantinya akan membantu pada saat decoding dengan

mengambil tabel kode yang tersimpan dalam file log. File ini berada di dalam

project tepatnya di folder logs. Untuk menyimpan tabel kode di dalam file log,

saya menggunakan stream bertipe objek dengan implements Serializable pada

kelasnya.

Aturan penamaan file log ini adalah tanggal ditambah waktu pada saat

proses kompresi. Sebagai contoh kompresi dilakukan pada tanggal 24 Desember

2014 pukul 11:21:40, maka nama file log menjadi 24122014112140. Penamaan

ini secara singkatnya adalah tanggal dalam format angka ditambah waktu dari

format jam, menit dan detik yang semuanya digabung tanpa spasi.

Seperti file pada umumnya, file ini juga mempunyai extension yang saya

beri nama .ldt (Log Data). Pemberian extension bertujuan untuk mempermudah

program dalam mengidentifikasi file yang akan diproses.


31

3.3.4.2 Stream Byte

Pada awalnya, untuk proses stream hasil kompresi akan menggunakan

stream bit yaitu stream dengan menggunakan ukuran terkecil dalam data. Ukuran

terkecil yang dimaksud adalah jika program mencetak angka 1, maka yang ditulis

adalah biner angka 1 bukan angka 1 yang mempunyai kode biner (00000001)

seperti halnya String atau Integer. Melihat sangat sulit dilakukan dengan

pemrograman berbasis Java, maka stream untuk hasil kompresi menggunakan

stream byte.

Stream byte adalah program mencetak hasil ke dalam sebuah file dengan

menulis tiap karakter. Deretan kode hasil proses analisis biner yang berisi 1 dan 0,

akan dipotong menjadi beberapa Stringdengan panjang masing-masing 7 karakter.

Pemotongan menjadi 7 karakter ini didasarkan pada jumlah bit yang terdapat di

sebuah karakter maksimal adalah 8 yaitu 10000000. Jika pemotongan berjumlah 8

karakter, akan menjadi masalah jika terdapat angka 1 selain di depan dan otomatis

tidak akan ada karakter yang sesuai. Sebagai standar, saya menggunakan ASCII

dengan maksimal jumlah bit adalah 28.

Proses stream byte ini sama dengan proses stream bit, hanya saja terdapat

perbedaan jika dalam stream bit program akan mencetak tiap bit, sedangkan pada

stream byte program akan mencetak tiap 7 bit menjadi sebuah karakter.


32

3.3.4.3 Buat File Kompresi

Untuk file baru hasil kompresi ini, saya akan memberi sebuah extension

dengan format .NFC(New File Compression). Tujuan dari pemberian format file

ini dengan nama yang baru adalah untuk membedakan file hasil kompresi dengan

file hasil kompresi yang lainnya seperti RAR, ZIP, TAR atau sebagainya. Karena

proses kompresi ini berbeda dari aplikasi kompresi lainnya, sehingga akan terjadi

error jika file ini dibuka dengan aplikasi kompresi pada umumnya.

Seperti halnya file hasil kompresi umumnya, pada file ini juga terdapat

sebuah informasi yang terdapat di dalamnya. Informasi dalam file ini meliputi

nama file log untuk data tersebut. Secara singkat, file hasil kompresi akan

berpasangan dengan file log-nya masing-masing. Selain itu juga terdapat

informasi tentang metode atau algoritma yang dipakai. Saya memberikan

ketentuan sebagai berikut :

1. Algoritma Huffman Statis, diberi kode ‘S’.

2. Algoritma Huffman Dinamis, diberi kode ‘D’.

3. Algoritma Huffman Modifikasi, diberi kode ‘M’.

Pemberian kode tersebut digunakan untuk mempermudah program dalam

proses decoding sehingga otomatis akan memilih cara yang sesuai. Untuk

mempermudah proses pengambilan data atau tokenizer, maka saya menggunakan

kata ‘sb’ yang merupakan singkatan dari sub. Alasan saya menggunakan sebuah

kata, karena jika menggunakan karakter nantinya akan terjadi ambigu ketika

terdapat karakter yang sama seperti karakter pembatas. Kejadian ambigu akan

kecil kemungkinannya jika menggunakan sebuah kata.


33

Secara garis besar format penulisan dalam file hasil kompresi adalah

sebagai berikut :

nama file logsbkode metodesb isi karakter

Untuk penamaan file hasil kompresi, saya menyamakan dengan nama file

asli ditambah dengan metode yang dipakai. Sebagai contoh file bernama coba.txt

di kompresi dengan metode Huffman Dinamis, menghasilkan file hasil

coba_dinamis.nfc.

3.3.5 Baca File

Proses baca file adalah proses user untuk memilih file hasil kompresi

untuk kemudian di dekompresi menjadi file baru seperti file aslinya. Pada proses

ini hanya file berekstensi .NFC yang dapat dibuka, karena output file hasil dari

sistem ini adalah file berformat .NFC. Sistem tidak bisa men-decoding jika

masukan file tidak berformat seperti aturan tersebut.

Pada proses ini program juga akan membaca semua isi file dan akan

memasukannya ke dalam sebuah String, lalu kemudian program akan men-

tokenizer menjadi 3 data. Hasil pemotongan tersebut adalah nama file log, kode

metode dan yang terakhir isi file. Program akan mengambil file log sesuai

dengan nama yang terdapat dalam file dan membacanya lalu kemudian

memasukannya ke dalam Arraylist objek. Setelah ketiga komponen terpenuhi,

yaitu : Arraylist objek berisi tabel kode, kode metode yang dipakai dan isi

karakter, maka proses selanjutnya adalah pengubahan kode.


34

3.3.6 Pengubahan Kode

Proses ini merupakan kebalikan dari proses pembentukan pohon

Huffman pada saat encoding. Di dalam proses ini, ketiga komponen yang sudah

diambil pada proses baca file akan diolah. Isi karakter akan di loop dan di proses

per karakter lalu diubah menjadi bentuk biner. Hasil pengubahan ini adalah

sebuah String yang berisi deretan kode 1 dan 0 seperti kode pada saat encoding.

Setelah terbentuk deret tersebut, maka akan dicocokan dengan Arraylist

yang berisi tabel kode sehingga akan terbentuk sebuah kata yang sesuai dengan

kata aslinya. Hasil dari proses ini adalah sebuah String yang nantinya akan diolah

pada proses selanjutnya.

3.3.7 Simpan File (Proses Decoding)

Proses simpan file pada saat decoding berbeda dengan proses simpan file

pada saat encoding. Pada proses ini, String hasil dari pengubahan kode akan

langsung di stream ke dalam sebuah file baru. Karena melihat dari batasan

masalah di mana file masukan hanya untuk berekstensi .TXT, maka file hasil

decoding akan langsung diberi extension .TXT.

Untuk penamaan file hasil decoding, menggunakan nama dari file hasil

kompresi hanya diganti extension .NFC menjadi .TXT. Sebagai contoh file

coba_dinamis.nfc hasil decoding menjadi coba_dinamis.txt.


35

3.4 Optimalisasi Algoritma Huffman

Seperti yang telah disebutkan dari awal, bahwa algoritma Huffman

merupakan dasar dari algoritma kompresi yang ada pada saat ini. Melihat posisi

tersebut bukan tidak mungkin dilakukan suatu modifikasi untuk mengoptimalkan

hasil kompresi dari algoritma Huffman. Algoritma Huffman mempunyai dua

macam algoritma, yaitu Huffman Dinamis dan Huffman Statis.

Kedua algoritma tersebut mempunyai persamaan yaitu terbuat dari pohon

biner yang dikenal dengan pohon biner Huffman, hanya saja kedua algoritma

tersebut mempunyai perbedaan pada preprocessing data. Algoritma Huffman

Dinamis lebih fleksibel dan tanpa preprocessing karena data yang masuk akan

diolah penempatannya ketika berada di pohon biner, sedangkan algoritma

Huffman Statis melakukan pengurutan frekuensi kemunculan dahulu sebelum

membuat pohon biner. Kedua algoritma mempunyai persamaan menempatkan

karakter yang sering muncul berada di dekat akar sehingga mempunyai kode

terpendek.

Pada penelitian ini mencoba untuk memodifikasi algoritma Huffman

supaya lebih optimal dalam mendapatkan hasil ukuran kompresi. Secara garis

besar, modifikasi ini merupakan turunan dari algoritma Huffman Statis. Untuk

lebih memahaminya, maka sebuah contoh akan penulis berikan.

Data : E B C D A A E A

Langkah 1 : cek frekuensi kemunculan setiap huruf, dan di dapat :

Hasil : E = 2, B = 1, C = 1, D = 1, A = 3


36

Langkah 2 : urutkan data dari frekuensi kemunculan terbanyak hingga

sedikit :

Hasil : A = 3, E = 2, B = 1, C = 1, D = 1

Langkah 3 : pembentukan pohon biner berdasarkan letak setiap

karakter, jika pada posisi ganjil maka akan menuju ke

sebelah kanan pohon. Jika terletak pada posisi genap maka

akan menuju ke sebelah kiri pohon.

Secara umum dapat dinyatakan dengan pseudecode sebagai berikut :

1. Cek frekuensi kemunculan tiap karakter.

2. Urutkan frekuensi dari yang terbanyak muncul hingga paling

sedikit muncul.

3. Cek posisi karakter yang telah diurutkan, variabel cursor == akar :

Ganjil :

Jika cursor.getKanan( ) == null, buat node baru.

Jika cursor.getKanan( ) != null, maka cursor = cursor.getKanan( ).

Genap :

Jika cursor.getKiri( ) == null, buat node baru.

Jika cursor.getKiri( ) == null, maka cursor = cursor.getKiri( ).

4. Lakukan nomor 3 hingga semua karakter ditempatkan pada pohon

biner.


37

Langkah 4 : membuat pohon biner dari data yang telah diurutkan.

Gambar 3.4 Pembentukan pohon Huffman modifikasi

1. Pada awalnya hanya akar dan data belum masuk.

2. Kemudian masuk karakter A, karena posisinya di awal (ganjil) dan

data belum ada maka langsung membuat node A di sebelah kanan akar.

3. Kemudian masuk karakter E, karena posisinya kedua (genap) dan

data belum ada maka langsung membuat node E di sebelah kiri akar.

4. Masuk karakter B yang berada pada urutan ketiga (ganjil), tetapi

sudah ada data A di sebelah kanan maka cursor turun 1 langkah dan membuat

node B di bawah node A.

5. Karakter C lalu masuk sebagai urutan keempat (genap), tetapi

sudah ada data E di sebelah kiri maka cursor turun 1 langkah dan membuat node

C di bawah node E.


38

6. Karakter terakhir adalah D dengan posisi kelima (ganjil). Karakter

tersebut menempati di sebelah kanan akar, tetapi sudah ada data A dan B maka

currsor turun 2 langkah dan membuat node D.

3.5 Desain User Interface

Tampilan atau user inteface merupakan komponen yang penting dalam

sebuah aplikasi atau program, oleh karena itu untuk mempermudah penggunaan

aplikasi kompresi ini penulis membuat sebuah rancangan untuk user interface.

Tampilan aplikasi ini dibuat menggunakan kelas form dalam Java. Penggunaan

kelas JTabedPane untuk tampilan berguna mempersingkat dan mengurangi

banyaknya form yang digunakan. Untuk lebih memperjelasnya, berikut rancangan

yang akan dibuat :

Gambar 3.5 Interface encoding


39

Gambar 3.6 Interface decoding

Secara garis besar, tampilan untuk encoding dan decoding hampir sama.

Kedua tampilan mempunyai jumlah tombol dan susunan panel yang sama. Untuk

panel detail pada encoding, akan saya tampilkan ukuran asli dan ukuran file

setelah dikompresi beserta compression ratio. Selain itu pada tampilan encoding

juga ditambahkan panel untuk memilih algoritma yang akan digunakan. Pada

panel detail untuk decoding akan ditampilkan ukuran setelah di decoding beserta

metode atau algoritma yang digunakan.

3.6 Spesifikasi Software dan Hardware

Spesifikasi perangkat keras dan perangkat lunak yang digunakan untuk

proses implementasi adalah sebagai berikut :

1) Processor : Intel(R) Core(TM) i3 CPU M380 @ 2.53GHz

2) Memory : 2048 MB

3) Harddisk : 320 GB


40

4) Operating System :Windows 7 Ultimate

@ 2013 Microsoft Corporation. All Rights

Reserved

5) Software : NetBeans IDE 7.3


41

4 BAB IV

IMPLEMENTASI DAN ANALISIS

Pada bab ini akan dibahas tentang implementasi rancangan yang telah

dijelaskan pada bab sebelumnya dan hasil analisa dari pengujian program.

Implementasi tersebut meliputi ketiga algoritma yang akan dibuat dengan bahasa

pemrograman Java. Pada bab sebelumnya telah dijelaskan proses-proses yang

akan dilakukan oleh sistem, berikut adalah implementasi dari tiap proses tersebut.

4.1 Proses Encoding

Proses yang pertama adalah proses encoding yaitu proses data teks awal

akan diubah menjadi kode-kode biner yang baru. Proses ini menghasilkan

keluaran berupa file hasil kompresi.

4.1.1 Implementasi Proses Baca Teks

Pada proses ini, akan dibagi menjadi dua implementasi yaitu

implementasi untuk memilih file dan implementasi untuk membaca file.


42

4.1.1.1 Memilih File

Gambar 4.1 Implementasi proses memilih file encoding

Penulis menggunakan kelas JFileChooser untuk menampilkan kotak

dialog browse, serta menggunakan WindowsLookAndFeel yang memberi kesan

seperti halnya kotak dialog pada aplikasi umumnya yang berjalan di Windows.

Penggunaan kelas FileFilter berfungsi untuk menyaring dan hanya menampilkan

file yang telah diatur. Pada program, file yang akan di-filter atau diperbolehkan

hanya file berekstensi .TXT atau Text Format. Setelah file dipilih, maka file akan

disimpan pada sebuah variabel.

4.1.1.2 Membaca File

Gambar 4.2 Implementasi proses membaca file encoding

Pada proses baca file, penulis tidak menggunakan fungsi Stream seperti

halnya FileInputStream atau menggunakan kelas FileReader melainkan

menggunakan fungsi yang telah tersedia di kelas Files dalam package java.nio.file


43

dan memasukannya ke dalam kelas. Fungsi tersebut hampir sama seperti fungsi

Stream yaitu membaca file, hanya saja pada fungsi ini program akan membaca

seluruh karakter yang ada di dalam file masukan sehingga nantinya tidak akan ada

karakter yang tidak terbaca.

4.1.2 Implementasi Proses Pembentukan Pohon Biner

Pada proses ini akan ada tiga implementasi dari proses pembentukan

pohon biner. Ketiga implementasi tersebut menyesuaikan dengan jumlah

algoritma yang akan diuji pada skripsi ini yaitu pembentukan pohon biner

algoritma Huffman Statis, Huffman Dinamis dan Huffman Modifikasi.

4.1.2.1 Pohon Biner Huffman Statis

Gambar 4.3 Implementasi pembentukan pohon Huffman Statis


44

Pada implementasi pembentukan pohon biner Huffman Statis, node

yang berisi karakter selalu ditempatkan di lengan sebelah kanan. Implementasi

dari ciri khas Huffman Statis, program akan mengecek terlebih dahulu apakah

lengan sebelah kanan kosong (null) atau tidak, jika kosong maka karakter

membuat node baru. Tetapi jika di sebelah kanan terdapat node atau tidak kosong,

maka cursor akan bergerak ke bawah melewati node tersebut untuk mencari

hingga posisi lengan sebelah kanan kosong.

4.1.2.2 Pohon Biner Huffman Dinamis

Gambar 4.4 Implementasi pembentukan pohon Huffman Dinamis


45

Implementasi pembentukan pohon biner Huffman Dinamis terlihat lebih

panjang dan rumit, hal ini dikarenakan pohon biner akan selalu berubah

menyesuaikan jumlah frekuensi kemunculan setiap karakter yang masuk. Langkah

pertama program akan mengecek lengan sebelah kanan kosong atau tidak, jika

kosong maka karakter akan membentuk node baru dengan jumlah diisi 1

(cursor.setJumlah(1)). Jumlah ini merupakan frekuensi kemunculan karakter, hal

ini juga yang membedakan Huffman Dinamis dengan metode Huffman yang lain.

Langkah kedua jika sebelah kanan terdapat node maka program akan

mengecek, jika data node tidak sama dengan karakter maka variabel n akan diisi

dengan cursor dan cursor akan turun ke bawah melewati node tersebut. Tetapi

jika data node sama dengan karakter, maka jumlah akan ditambah dengan 1 dan

variabel n akan dibandingkan dengan data node. Proses perbandingan ini akan

mengecek jumlah pada variabel n dan pada node, jika pada variabel n lebih kecil

jumlahnya dibanding dengan node maka posisi keduanya akan ditukar.


46

4.1.2.3 Pohon Biner Huffman Modifikasi

Gambar 4.5 Implementasi pembentukan pohon Huffman Modifikasi

Pembentukan pohon biner Huffman Modifikasi penulis implementasikan

mirip seperti pembentukan pohon biner Huffman Statis, hanya saja terdapat

perbedaan pada peletakan node setiap karakter. Ciri khas yang saya berikan pada

algoritma ini adalah posisi tiap karakter (ganjil dan genap) akan menentukan

peletakan pada pohon biner,pada implementasi terdapat variabel boolean yaitu

isKanan_Ganjil. Variabel ini mempunyai arti jika posisi karakter adalah ganjil,

maka akan ditempatkan pada lengan sebelah kanan.

Cara kerja algoritma ini, pertama variabel isKanan_Ganjil diberi nilai

true karena karakter pertama pasti mempunyai posisi ganjil. Langkah berikutnya

akan mengecek sebelah kanan dari cursor jika kosong dan isKanan_Ganjil adalah

true maka akan membentuk node baru serta memberi nilai isKanan_Ganjil


47

menjadi false karena pasti posisi karakter berikutnya adalah genap. Jika tidak

kosong maka cursor akan menuju ke bawah dan melewati node tersebut.

Kemudian jika sebelah kiri dari cursor kosong dan isKanan_Ganjil

adalah false maka akan membentuk node baru serta memberi nilai isKanan_Ganjil

menjadi true. Jika tidak kosong akan melewati node tersebut dan cursor menuju

ke bawah.

4.1.3 Implementasi Proses Analisis Biner

Pada proses ini, akan dibahas tentang pembentukan kode biner(1 dan 0)

dari hasil pembentukan pohon biner pada proses sebelumnya. Pada implementasi

ini akan dibagi menjadi dua, yang pertama yaitu implementasi pada Huffman

Statis dan Huffman Modifikasi, serta yang kedua implementasi pada Huffman

Dinamis. Kedua implementasi tersebut menggunakan sebuah kelas utama yaitu

KodeHuffman, berikut isi dari kelas tersebut :


48

Gambar 4.6 Source code kelas KodeHuffman.java

Pada kelas tersebut terdapat dua atribut yaitu huruf dan kode yang

masing-masing bertipe String. Kelas ini pada dasarnya berfungsi untuk

menyimpan kode biner yang baru dari masing-masing huruf atau karakter. Di

dalam kelas terdapat method set dan get untuk mempermudah dalam

mengaksesnya.


49

4.1.3.1 Implementasi Huffman Statis dan Huffman Modifikasi

Gambar 4.7 Implementasi analisis biner Huffman Statis dan modifikasi method

generateKode()

Dalam proses ini nantinya terdapat dua method, salah satunya

adalah method generateKode(). Method ini secara garis besar berfungsi

untuk menentukan kode biner yang baru dari masing-masing karakter. Di

dalam potongan program di atas, dapat dibagi menjadi dua proses yaitu

proses membentuk pohon biner dengan membuat objek dari kelas

BinaryTree dan proses mencari kode di dalam pohon biner. Pencarian

kode tersebut dilakukan dengan memanggil method berikutnya yaitu

method find() dengan parameter objek pohon biner dan karakter yang di

cari. Dalam method ini terdapat perbedaan antara algoritma Huffman Statis

dan Huffman Modifikasi, perbedaan tersebut didasarkan pada bentuk

pohon biner yang berbeda dari kedua algoritma.


50

Gambar 4.8 Implementasi analisis biner Huffman Statis method find()

Method find() tersebut digunakan untuk algoritma Huffman Statis,

di mana jika dilihat hanya mengecek sebelah kanan dari pohon biner. Cara

kerja dari proses ini, pertama program akan terus berulang hingga cursor

sama dengan null. Program akan mengecek sebelah kanan, apakah data di

node sama dengan data yang dicari. Jika sesuai maka kode akan berisi 1

sertacursor akan berubah menjadi null dan looping berhenti.

Jika sebelah kanan data dalam node tidak sesuai dengan data yang

dicari maka kode akan berisi 0 dan cursor akan berpindah ke bawah serta


51

berulang untuk kembali mengecek dari awal. Tetapi jika sebelah kiri tidak

ada kata “simpul” hal itu berarti tidak ada cabang di bawahnya maka

program akan berhenti looping dengan membuat cursor menjadi null.


52

Gambar 4.9 Implementasi analisis biner Huffman Modifikasi method

find()

Method find() tersebut digunakan untuk algoritma Huffman

Modifikasi, terlihat lebih panjang karena program harus mengecek lengan

sebelah kanan dan kiri. Hal itu dikarenakan pohon biner pada algoritma ini

menggunakan semua lengannya untuk menyimpan karakter. Pada program

tersebut terdapat variabel boolean kanan yang diberi nilai awal true.

Variabel ini berfungsi supaya program mengecek lengan sebelah kanan

terlebih dahulu, jika sebelah kanan sudah tidak ada data dan karakter yang

dicari belum ditemukan maka variabel kanan menjadi false.

Perubahan nilai variabel kanan menjadi falseini membuat program

akan berpindah ke lengan sebelah kiri dimulai kembali dari atas (root).

Jika data tidak ditemukan maka proses akan berhenti dari looping.


53

4.1.3.2 Implementasi Huffman Dinamis

Gambar 4.10 Implementasi analisis biner Huffman Dinamis method

generateCode()

Pada implementasi Huffman Dinamis, proses analisis biner hampir sama

seperti pada Huffman Statis atau Huffman Modifikasi. Terdapat dua method yang

akan digunakan yaitu generateCode() dan prosesGenerate() dengan parameter

objek dari BinaryTree. Pada method prosesGenerate() berfungsi untuk mencari

kode baru pada setiap karakter yang sudah dimasukan di dalam pohon biner.

Proses pemasukan karakter terdapat di dalam method generateCode(). Untuk

proses analisis biner Huffman Dinamis ini juga menggunakan kelas

KodeHuffman yang sudah dibahas sebelumnya.


54

Gambar 4.11 Implementasi analisis biner Huffman Dinamis method

prosesGenerate()

Di dalam method prosesGenerate() ini berbeda dengan method find()

pada algoritma Huffman yang lain. Di sini penulis mengecek bukan dengan

karakter yang dicari, melainkan dari atas ke bawah dengan mengganti jumlah

frekuensi menjadi 0. Hal ini saya lakukan karena tidak mungkin ada frekuensi

karakter berjumlah 0 pada saat karakter masuk ke dalam pohon biner. Setiap

karakter yang baru dicek akan di masukan ke dalam Arraylist dan mengganti


55

frekuensi jumlahnya menjadi 0. Program akan melewati node jika jumlahnya

adalah 0 dan akan berhenti looping jika sudah tidak ada node di sebelah kanan.

4.1.4 Implementasi Proses Encoding

Proses encoding merupakan sebuah proses di mana program akan

mengubah setiap karakter pada data teks menjadi sekumpulan kode biner yang

baru. Pada implementasi proses ini, akan dibagi menjadi dua bagian yaitu

implementasi encoding pada Huffman Modifikasi, implementasi encoding pada

Huffman Statis dan Huffman Dinamis.

4.1.4.1 Implementasi Encoding Huffman Statis dan Huffman Dinamis

Gambar 4.12 Implementasi encoding Huffman Statis dan Dinamis

Implementasi pada Huffman Statis dan Huffman Dinamis mempunyai

proses yang sama, karena pada dasarnya pembentukan pohon biner kedua

algoritma tersebut juga sama. Pembentukan pohon biner yang hanya

menggunakan lengan sebelah kanan memberikan dampak positif serta


56

mempermudah dalam proses ini. Dampak yang dihasilkan adalah tidak adanya

kode biner yang bersifat ambigu, yang berarti akhiran dari sebuah kode bukan

merupakan awalan dari kode yang lain.

Pada method tersebut terdapat dua buah parameter yaitu Arraylist kelas

KodeHuffman dan data seluruh isi teks bertipe String. Cara kerja dari method ini

adalah membandingkan setiap karakter pada data teks dengan Arraylist

KodeHuffman, sehingga hasil dari proses ini berupa data String yang berisi

kumpulan kode biner.

4.1.4.2 Implementasi Encoding Huffman Modifikasi

Gambar 4.13 Implementasi encoding Huffman Modifikasi

Implementasi proses encoding pada algoritma Huffman Modifikasi

berbeda dari Huffman Statis atau Huffman Dinamis, perbedaan ini dikarenakan


57

struktur pohon biner yang berbeda dari algoritma lain. Algoritma ini

menggunakan semua lengannya untuk menyimpan node. Dampak dari

penggunaan semua lengan pada pohon biner, mengakibatkan adanya sifat ambigu.

Oleh karena itu penulis membuat sebuah aturan untuk pembatas antar kode yaitu :

Kanan separator 0

Kiri separator 1

Aturan tersebut merupakan kebalikan dari kode di setiap lengan. Jika

data berada di sebelah kanan mempunyai kode 1, maka akan selalu diakhiri

dengan 0 sebagai pembatas untuk kode berikutnya. Jika data berada di sebelah kiri

mempunyai kode 0, maka akan diakhiri dengan 1 sebagai pembatasnya.

Implementasi dari aturan tersebut dapat dilihat dengan penggunaan fungsi

endsWithyang merupakan fungsi dari Java untuk mengecek apakah sebuah data

diakhiri oleh karakter yang ditentukan.

Cara kerja dari proses encoding algoritma Huffman Modifikasi mirip

dengan proses pada algoritma Huffman Statis atau Huffman Dinamis,yaitu dengan

mencocokan setiap karakter pada data teks dengan Arraylist Kode Huffman.

Perbedaandari ketiga algoritma, pada algoritma Huffman Modifikasi hanya

ditambah dengan aturan pembatas.

4.1.5 Implementasi Proses Simpan File Hasil Kompresi

Proses selanjutnya adalah menyimpan sekumpulan kode biner hasil

proses sebelumnya ke dalam bentuk file hasil dari kompresi. Pada proses ini setiap


58

kode biner akan di simpan dalam bentuk bit yang merupakan satuan terkecil

dalam file. Proses ini penulis membuat menjadi tiga bagian yaitu proses

preprocessing, proses simpan file log dan proses simpan file kompresi. Ketiga

proses tersebut diimplementasikan ke dalam tiga method yang semuanya berada di

kelas EncoderStream.java.

4.1.5.1 Implementasi Preprocessing

Gambar 4.14 Implementasi preprocessing


59

Ketiga proses yang terdapat pada tahap ini, proses inilah yang paling

penting dan utama karena kode biner bertipe String tersebut akan dipecah menjadi

7 karakter. Dasar dari pemecahan ini, karena panjang maksimal setiap karakter

menurut standar ASCII yaitu 28 = 256 bit atau ditulis dalam biner 10000000.

Pemecahan menjadi 7 karakter ini berguna untuk mengantisipasi jika terdapat

kode biner yang lebih dari 256 bit. Sebagai contoh :

Kode biner = 10000001001

Pemecahan 8 karakter = 10000001 001

Pemecahan 7 karakter = 1000000 1001

Jika dilakukan pemecahan 8 karakter maka akan membentuk sebuah

karakter yang mempunyai nilai biner 257 atau lebih dari standar ASCII. Jika

terdapat sebuah karakter yang lebih dari 256 nilai binernya, maka standar harus

diubah menjadi Unicode di mana panjang maksimal setiap karakter adalah 216.

Standar pembentukan karakter pada penelitian ini menggunakan ASCII.

Pada implementasi program, pemecahan dilakukan dengan ekspresi

modulo. Setelah dilakukan pemecahan, program akan mengubah kode biner yang

bertipe String menjadi bertipe Integer dengan perintah Integer.parseInt(String

code,2). Perintah tersebut mempunyai arti mengubah data menjadi kode biner dan

hasilnya bertipe Integer. Angka 2 diambil dari bilangan yang di pangkat dalam

penghitungan biner.

Setelah didapat kode biner yang sudah siap diproses, maka selanjutnya

mencari karakter yang sesuai dengan kode biner (nilai biner). Pencarian tersebut

menggunakan perintah new Character((char)int data). Perintah tersebut akan


60

secara otomatis mendapatkan karakter yang sesuai dengan nilai biner. Langkah

terakhir adalah menyimpan karakter yang telah diperoleh ke dalam Arraylist

untuk diproses selanjutnya.

4.1.5.2 Implementasi Simpan File Log

Gambar 4.15 Implementasi proses simpan file log

Proses ini berfungsi untuk menyimpan data huruf dan kode biner yang

baru berupa Arraylist dengan tipe kelas KodeHuffman.java. Pada method ini

menggunakan stream bertipe objek untuk memudahkan dalam menyimpannya

supaya tidak terpisah antara data huruf dan kode biner.

File hasil disimpan dalam folder “logs” di dalam project dengan tipe data

.LDT yang merupakan singkatan dari Logs Data. Untuk nama menggunakan

waktu saat file dibuat dengan format tanggal, bulan, tahun, jam, menit dan detik

yang digabung menjadi satu. Penamaan hingga satuan detik berguna untuk

membuat file yang unik antara satu dengan yang lain.


61

4.1.5.3 Implementasi Simpan File Kompresi

Gambar 4.16 Implementasi proses simpan file kompresi

Proses selanjutnya berfungsi untuk menyimpan file hasil kompresi yang

telah diubah kodenya ke dalam sebuah file baru bertipe .NFC yang telah dibahas

pada bab sebelumnya. Di dalam method ini menggunakan kelas dari Java yaitu

PrintWriter yang merupakan salah satu cara dalam melakukan proses stream.

Salah satu keunggulan menggunakan kelas tersebuat adalah kita dapat

menentukan tipe dari hasil encoding teks.

Dalam method tersebut menggunakan tipe “windows-1252” yang berarti

encoding yang digunakan menggunakan standard ANSI (American National

Standards Institute). Alasan saya menggunakan ANSI, karena pada skripsi ini

hanya menggunakan 8 bit atau dengan total hanya 256 kombinasi. Jika saya

menggunakan tipe “utf-8” akan terlalu banyak bit yang tidak digunakan karena

dalam tipe tersebut menggunakan 32 bit.

Pada method tersebut terdapat kata “sb” yang digunakan sebagai pemisah

dan merupakan singkatan dari sub. Pemisah ini digunakan untuk mempermudah


62

dalam proses decoding. Pemisah tersebut memisahkan nama file log, jenis

algoritma yang digunakan dan isi dari kode biner yang baru.

4.2 Proses Decoding

Proses yang kedua adalah proses decoding yaitu proses mengembalikan data

biner hasil kompresi menjadi data awal. Terdapat beberapa proses yang ada,

antara lain sebagai berikut.

4.2.1 Implementasi Proses Baca Teks File Kompresi

Setelah proses encoding sudah dilakukan semua, maka akan menghasilkan

file hasil kompresi bertipe .NFC. Untuk mengubah kode seperti semula maka

harus dilakukan tiga tahap yaitu proses baca file kompresi, pengubahan kode dan

yang terakhir adalah membuat file bertipe .TXT seperti format teks awal. Pada

proses ini terdapat dua proses yaitu memilih file dan membaca file.

4.2.1.1 Memilih File

Gambar 4.17 Implementasi proses memilih file decoding


63

Sama seperti cara memilih file pada saat akan mengkompresi, saya

menggunakan kelas JFileChooser dan menggunakan WindowsLookAndFeel untuk

menampilkan kotak dialog seperti aplikasi yang berjalan pada sistem operasi

Windows. Perubahan hanya terjadi di FileFilter yang dirubah menjadi .NFC yang

berarti hanya menampilkan file berekstensi .NFC.

4.2.1.2 Membaca File

Gambar 4.18 Implementasi proses membaca file decoding

Proses berikutnya adalah membaca file kompresi, penulis menggunakan

method dari Java yaitu Files.readAllBytes yang mempunyai keunggulan membaca

semua karakter di dalam sebuah file tanpa terkecuali. Setelah semua karakter

terbaca maka akan dilakukan pembagian menjadi tiga data yang telah dipisahkan

oleh kata “sb” tadi.

Tiga data tersebut adalah nama file log, jenis algoritma yang digunakan

dan data inti yang berisi kode baru.


64

4.2.2 Implementasi Proses Pengubahan Kode (Decoding)

Pada proses pengubahan kode ini, tiga data hasil dari proses sebelumnya

akan diolah sesuai kebutuhan masing-masing. Dari tiga data tersebut akan

terbentuk dua sub proses yaitu proses decoding header dan proses decoding isi.

Selain itu akan dibahas juga proses decoding untuk ketiga algoritma Huffman.

4.2.2.1 Proses Decoding Header

Gambar 4.19 Implementasi proses decoding header

Pada proses ini, file log yang sudah dibuat akan dibaca kembali dengan

cara mencocokan nama file log pada data hasil yang pertama dengan nama file

yang ada di dalam folder. Setelah file log sesuai maka akan dilakukan proses

stream bertipe objek. Pemilihan stream bertipe objek didasarkan untuk

mempermudah dalam pengambilan data, sehingga data kode biner dan huruf tidak

terpisah atau tertukar.


65

4.2.2.2 Proses Decoding Isi

Gambar 4.20 Implementasi proses decoding isi

Pada method ini merupakan inti dari proses decoding yaitu dengan

mengembalikan kode yang telah diubah sebelumnya. Data yang digunakan adalah

data ketiga dari hasil pemecahan pada proses membaca file. Seperti yang telah

dijelaskan pada sub bab sebelumnya, bahwa proses encoding adalah mengubah

setiap tujuh bit menjadi sebuah karakter baru. Karena terkadang tidak semua

jumlah bit habis dibagi tujuh, maka sisa dari pembagian akan ditulis paling

belakang. Sebagai contoh sebuah teks setelah diubah menjadi data biner

berjumlah 52 bit maka jika dibagi tiap 7 bit akan menghasilkan 7 karakter dengan

sisa 3 bit, maka di akhir data akan dituliskan 3 sebagai penanda sisa bit. Penulisan

sisa ini akan berguna dalam proses pengubahan menjadi data biner kembali,

sebelum di decoding.


66

Di dalam method terdapat variabel akhir yang berisi sisa dari pembagian.

Jika nilai akhir adalah 0, maka data biner tersebut habis di bagi tujuh dan dapat

langsung diubah kembali karakter-karakter di dalam data menjadi biner. Jika nilai

akhir tidak 0 maka karakter terakhir akan di proses terpisah setelah karakter lain

telah diubah menjadi biner. Pemisahan ini dilakukan karena harus menggunakan

syntax yang berbeda. Di dalam method tersebut, perintah yang menjadi inti adalah

String.format(“%7s”, Integer.toBinaryString(c)).replace(‘ ‘,’0’).

Perintah tersebut berarti mengubah karakter c menjadi Integer biner

dengan jumlah bit sebanyak 7, ditulis dengan perintah “%7s”. Perintah “replace(‘

‘,’0’)” berarti mengganti tempat yang kosong dengan angka 0, karena secara

default setelah proses pengubahan tersebut angka 0 akan menjadi kosong.

4.2.2.3 Proses Decoding Huffman Dinamis dan Huffman Statis

Gambar 4.21 Implementasi proses decoding Huffman Dinamis dan Huffman

Statis


67

Proses decoding untuk Huffman Statis dan Huffman Dinamis memiliki

cara yang sama, karena tidak memakan separator seperti pada Huffman modifikasi

yang penulis buat. Dalam membentuk hasil, penulis menggunakan StringBuilder

untuk memudahkan dalam menggabungkan setiap String sehingga menjadi sebuah

kata.

Langkah pertama adalah membentuk sebuah objek StringBuilder dan

kemudian melakukan loop hingga semua data habis. Dalam melakukan loop, data

akan dicocokan dengan data header. Jika kode sesuai maka akan menambahkan

karakter yang sesuai ke objek StringBuilder hingga membentuk sebuah kata atau

kalimat.

4.2.2.4 Proses Decoding Huffman Modifikasi

Gambar 4.22 Implementasi proses decoding Huffman Modifikasi


68

Pada proses decoding Huffman Modifikasi ini berbeda dengan proses

decoding Huffman Dinamis dan Huffman Statis. Proses yang dilakukan harus

mengecek bit selanjutnya. Penulis membuat suatu kondisi jika bit selanjutnya

tidak sama maka akan mengecek dengan data yang tersimpan pada log. Kondisi

ini dibuat penulis karena pada dasarnya algoritma Huffman Modifikasi ini setiap

karakter memiliki bit yang sama, satu karakter bisa bernilai 1 atau 0 semua.

Dalam menggabungkan setiap karakter, method ini juga menggunakan

StringBuilder.

4.2.3 Implementasi Proses Pembentukan File Hasil Decoding

Gambar 4.23 Implementasi proses pembentukan file decoding


69

Proses ini merupakan proses terakhir dalam melakukan decoding yaitu

membuat file hasil. Setelah proses decoding selesai dan menghasilkan suatu kata

atau kalimat, langkah selanjutnya adalah proses Stream dengan menggunakan

kelas PrintWriter. File hasil yang dihasilkan berekstensi .TXT dan akan dibuat di

dalam folder bersamaan dengan file .NFC.


70

5 BAB V PENGUJIAN DAN ANALISIS

BAB V

PENGUJIAN DAN ANALISIS

Penulis akan melakukan pengujian terhadap ketiga algoritma dengan

didasarkan pada kecepatan proses encoding dan ukuran file hasil kompresi.

Pengujian tersebut dipilih oleh penulis karena dalam bidang kompresi selain

ketepatan hasil decoding, kedua faktor pengujian tersebut juga penting untuk

dilakukan.

5.1 Perbandingan Jumlah Bit

Pada percobaan perbandingan yang pertama, penulis akan

membandingkan jumlah bit yang dihasilkan oleh ketiga algoritma dari proses

encoding. Untuk melakukan pengujian, penulis membuat sebuah kelas yang berisi

sebagai berikut.


71

Gambar 5.1 Kelas pengujian perbandingan jumlah bit

Pada program diatas, penulis membuat sebuah kalimat sebagai data yaitu

“Universitas Sanata Dharma Yogyakarta”. Dari data tersebut penulis akan

menghitung jumlah bit data asli dan menghitung jumlah bit hasil dari encoding

tiap algoritma. Hasil dari program di atas sebagai berikut.

Gambar 5.2 Capture hasil pengujian jumlah bit


72

Gambar 5.3 Lanjutan capture hasil pengujian jumlah bit

Hasil penghitungan jumlah bit menghasilkan bahwa data asli yang diubah

menjadi biner mempunyai 285 bit, sedangkan hasil encoding Huffman Statis

adalah 233 bit, Huffman Dinamis menjadi paling banyak dengan jumlah 266 bit

dan Huffman Modifikasi sebanyak 164 bit. Hasil decoding ketiga algoritma

tersebut juga menunjukan bahwa proses berjalan dengan baik dan menghasilkan

kalimat yang sama dengan data asli. Hasil tersebut dapat ditampilkan dalam tabel

berikut.

Algoritma Jumlah Bit

Data asli 285

Huffman Statis 233

Huffman Dinamis 266

Huffman Modifikasi 164

Tabel 5.1 Tabel hasil perbandingan jumlah bit

Untuk lebih membuktikan, penulis melakukan pengujian terhadap enam

data. Semua data akan dilakukan pengujian untuk mengetahui jumlah bit setelah

kompresi dan menghitung ratio compression. Penulis membuat sebuah frame

untuk memudahkan proses pengujian.


73

Gambar 5.4 Frame pengujian jumlah bit dan ratio compression

File

penguji

Jumlah

karakter

Bit

awal

Huffman Statis Huffman

Dinamis

Huffman

Modifikasi

Bit Ratio Bit Ratio Bit Ratio

c1.txt 100 788 649 17.63 721 8.5 453 42.51

c2.txt 204 1592 1471 7.6 1568 1.5 994 37.56

c3.txt 304 2376 2101 11.57 2160 9.09 1435 39.6

c4.txt 408 3181 2902 8.77 2950 7.26 1966 38.19

c5.txt 510 3976 3737 6.01 3790 4.67 2514 36.77

c6.txt 612 4772 4504 5.61 4559 4.46 3028 36.54

Tabel 5.2 Tabel hasil pengujian jumlah bit dan ratio compression

5.2 Perbandingan Ukuran File Kompresi dan Waktu Proses

Percobaan selanjutnya adalah membandingkan ukuran hasil kompresi

dan waktu proses kompresi. Dalam melakukan proses ini, penulis menggunakan

user interface untuk memudahkan pengguna dalam pengoperasian.


74

Gambar 5.5 Tampilan awal aplikasi

Gambar 5.6 Tampilan klik Browse untuk memilih file


75

Gambar 5.7 Tampilan encoding untuk memilih salah satu algoritma

Gambar 5.8 Tampilan loading proses encoding


76

Gambar 5.9 Pemberitahuan jika proses encoding berhasil

Pada percobaan ini penulis melakukan enam percobaan dengan ukuran

berbeda yang semakin bertambah secara linear. Percobaan ini akan menguji

kecepatan dan hasil kompresi dari ketiga algoritma yang telah dibuat. Data ukuran

file pengujian ada pada tabel berikut.

Nama file Ukuran file

uji1.txt 100 KB

uji2.txt 200 KB

uji3.txt 300 KB

uji4.txt 400 KB


77

uji5.txt 500 KB

uji6.txt 600 KB

Tabel 5.3 Data ukuran file pengujian

Dari pengujian tersebut penulis mendapatkan file dan ukuran hasil

kompresi serta waktu yang diperlukan untuk melakukan encoding. Data yang

diperoleh sebagai berikut.

Data Waktu Proses Ukuran File Hasil

Statis Dinamis Modifikasi Statis Dinamis Modifikasi

uji1.txt 36 menit

34 detik

39 menit

41 detik

20 menit

42 detik

131 KB 131 KB 84 KB

uji2.txt 3 jam 48

menit 22

detik

3 jam 50

menit 17

detik

1 jam 53

menit 3

detik

261 KB 261 KB 167 KB

uji3.txt 7 jam 48

menit 19

detik

7 jam 49

menit 52

detik

4 jam 57

menit 19

detik

392 KB 392 KB 250 KB

uji4.txt 12 jam 5

menit 27

detik

11 jam 55

menit 31

detik

8 jam 42

menit 56

detik

522 KB 522 KB 333 KB

uji5.txt 16 jam

25 menit

16 detik

16 jam 30

menit 46

detik

12 jam 33

menit 57

detik

653 KB 653 KB 417 KB

uji6.txt 21 jam

29 menit

16 detik

21 jam 11

menit 40

detik

16 jam 57

menit 2

detik

785 KB 785 KB 501 KB

Tabel 5.4 Tabel hasil pengujian


78

Untuk mempermudah dalam pembacaan hasil pengujian, maka penulis

akan menampilkan dalam bentuk grafik untuk waktu proses dan file hasil

kompresi.

Gambar 5.10 Grafik waktu yang dibutuhkan untuk kompresi

Gambar 5.11 Grafik ukuran file hasil kompresi

0:00:00

2:24:00

4:48:00

7:12:00

9:36:00

12:00:00

14:24:00

16:48:00

19:12:00

21:36:00

0:00:00

uji 1 uji 2 uji 3 uji 4 uji 5 uji 6

statis

dinamis

modif

0

100

200

300

400

500

600

700

800

900

uji 1 uji 2 uji 3 uji 4 uji 5 uji 6

statis

dinamis

modif


79

Berdasarkan hasil pengujian dari ketiga algoritma tersebut, Huffman

Modifikasi jauh lebih baik untuk waktu yang diperlukan dalam sekali melakukan

kompresi. Selain itu ukuran file hasil kompresi lebih kecil dibandingkan algoritma

Huffman Statis dan Huffman Dinamis.

Menurut data hasil pengujian di atas, terdapat satu permasalahan yang

sangat menganggu yaitu masalah waktu yang dibutuhkan untuk melakukan

proses. Terlihat pada percobaan terhadap uji6.txt untuk Huffman Statis

memerlukan waktu 21 jam 29 menit 16 detik, hal ini akan sangat menganggu jika

ukuran file yang dikompres melebihi 1 Mb.

Hal tersebut dikarenakan algoritma yang digunakan melakukan proses

loop yang banyak, setiap algoritma paling tidak melakukan dua kali proses loop.

Jumlah proses ini akan mengikuti banyaknya dari karakter dalam suatu file, oleh

karena itu semakin banyak karakter akan semakin besar ukuran file dan semakin

lama dalam memprosesnya. Permasalahan waktu tersebut juga disebabkan karena

di Java, memakai banyak memori untuk menyimpan proses yang berjalan

sehingga dapat memperlambat proses dan memerlukan waktu yang cukup banyak.

5.3 Hubungan Peluang Kemuculan Setiap Karakter dengan Jumlah

Bit Hasil Kompresi

Pengujian selanjutnya, penulis akan menganalisis sejauh mana pengaruh

jumlah kemunculan setiap karakter dengan ukuran bit hasil kompresi. Pengujian

akan dilakukan terhadap 20 teks yang masing-masing 10 teks berbahasa Indonesia

dan 10 teks berbahasa Inggris. Penggunaan dua bahasa ini, sekaligus untuk


80

menganalisis sejauh mana algoritma kompresi ini dapat bekerja optimal di dalam

bahasa berbeda.

5.3.1 Data Bahasa Indonesia

Nama

file

Jumlah

karakter

Jumlah

bit

sebelum

Jumlah bit sesudah (rasio

kompresi)

Peluang

karakter (5

terbanyak) Statis Dinamis Modifikasi

ind1.txt 3644 28324 34620

(-22.2)

3489

(-23.1)

21918

(22.6)

(spasi)=0.14

a=0.13

e=0.08

n=0.07

i=0.06

ind2.txt 3772 29230 34977

(-19.6)

35303

(-20.7)

22269

(23.8)

a=0.16

(spasi)=0.13

n=0.07

e=0.06

i=0.06

ind3.txt 3614 28126 30094

(-6.9)

30257

(-7.5)

19624

(30.2)

a=0.15

(spasi)=0.13

n=0.08

e=0.06

i=0.06

ind4.txt 4069 31667 35701

(-12.7)

35841

(-13.1)

23000

(27.3)

a=0.13

(spasi)=0.13

n=0.09

e=0.07

i=0.06

ind5.txt 3745 29094 36390

(-25.0)

37054

(-27.3)

22924

(21.2)

(spasi)=0.13

a=0.13

n=0.08

e=0.07

i=0.07

ind6.txt 3668 28446 34770

(-22.2)

35499

(-24.7)

22023

(22.5)

a=0.15

(spasi)=0.13

e=0.06

n=0.06

i=0.05

ind7.txt 3889 30134 38180

(-26.7)

38465

(-27.6)

24001

(20.3)

(spasi)=0.13

a=0.13

i=0.07

n=0.07


81

e=0.07

ind8.txt 3677 28718 32071

(-11.6)

32291

(-12.4)

20695

(27.9)

a=0.16

(spasi)=0.13

n=0.08

e=0.07

i=0.06

ind9.txt 3903 30324 35234

(-16.1)

35880

(-18.3)

22547

(25.6)

a=0.13

(spasi)=0.13

n=0.1 i=0.08

e=0.07

ind10.txt 3831 29841 34116

(-14.2)

34404

(-15.1)

21905

(26.6)

a=0.14

(spasi)=0.12

n=0.07

e=0.07

i=0.06

Tabel 5.5 Hasil pengujian jumlah bit data bahasa Indonesia

Untuk mencari karakter dengan peluang kemunculan terbanyak di bahasa

Indonesia. maka dari data di atas dapat dihitung :

Karakter

terbanyak

Rata-rata peluang dalam 10 sample data

a (0.13 + 0.16 + 0.15 + 0.13 + 0.13

+ 0.15 + 0.13 + 0.16 + 0.13 +

0.14) / 10

0.14

(spasi) (0.14 + 0.13 + 0.13 + 0.13 + 0.13

+ 0.13 + 0.13 + 0.13 + 0.13 +

0.12) / 10

0.13

n (0.07 + 0.07 + 0.08 + 0.09 + 0.08

+ 0.06 + 0.07 + 0.08 + 0.1 +

0.07) / 10

0.08

i (0.06 + 0.06 + 0.06 + 0.06 + 0.07

+ 0.05 + 0.07 + 0.06 + 0.08 +

0.06) / 10

0.06

e (0.08 + 0.06 + 0.06 + 0.07 + 0.07

+ 0.06 + 0.07 + 0.07 + 0.07 +

0.07) / 10

0.07

Tabel 5.6 Peluang karakter terbanyak data bahasa Indonesia


82

Dari data tersebut dapat dilihat bahwa karakter ‘a’ menempati posisi

teratas dengan peluang kemunculan 0.14 dalam 10 data sample. Rata-rata rasio

kompresi Huffman Modifikasi untuk data bahasa Indonesia yaitu 24.8. Hasil

minus pada rasio Huffman Statis dan Dinamis dipengaruhi hasil bit setelah

kompresi lebih besar dari jumlah bit asli.

5.3.2 Data Bahasa Inggris

Nama

file

Jumlah

karakter

Jumlah

bit

sebelum

Jumlah bit sesudah (rasio

kompresi)

Peluang

karakter (5

terbanyak) Statis Dinamis Modifikasi

eng1.txt 3215 25443 29943

(-17.6)

30305

(-19.1)

19082

(25.0)

(spasi)=0.15

e=0.08

a=0.07

o=0.06

t=0.06

eng2.txt 2897 22858 25917

(-13.3)

26034

(-13.8)

16658

(27.1)

(spasi)=0.17

e=0.1 a=0.06

t=0.06

o=0.05

eng3.txt 3473 27161 31147

(-14.6)

31543

(-16.1)

19988

(26.4)

(spasi)=0.16

e=0.11

t=0.07

a=0.07

o=0.05

eng4.txt 3264 25576 28269

(-10.5)

28437

(-11.1)

18303

(28.4)

(spasi)=0.17

e=0.1 a=0.07

t=0.06

o=0.05

eng5.txt 3325 26112 28350

(-8.5)

28945

(-10.8)

18431

(29.4)

(spasi)=0.16

e=0.09

t=0.07

o=0.07

a=0.06

eng6.txt 3210 25258 27967

(-10.7)

28290

(-12.0)

18101

(28.3)

(spasi)=0.16

e=0.08

a=0.07

o=0.07

t=0.07

eng7.txt 3085 24165 26798

(-10.8)

27040

(-11.8)

17341

(28.2)

(spasi)=0.16

t=0.08


83

e=0.08

a=0.08

o=0.06

eng8.txt 3060 23834 26495

(-11.1)

26706

(-12.0)

17156

(28.0)

(spasi)=0.16

e=0.1 t=0.07

a=0.06

o=0.06

eng9.txt 3328 25860 30949

(-19.6)

31045

(-20.0)

19719

(23.7)

(spasi)=0.15

e=0.1 a=0.06

o=0.06

t=0.06

eng10.txt 3253 25275 28717

(-13.6)

28857

(-14.1)

18527

(26.6)

(spasi)=0.16

e=0.1 a=0.08

o=0.05

t=0.06

Tabel 5.7 Hasil pengujian jumlah bit data bahasa Inggris

Seperti pada data bahasa Indonesia, penulis juga menghitung peluang

kemunculan 5 karakter terbanyak pada data bahasa Inggris :

Karakter

5

terbanyak

Rata-rata peluang dalam 10 sample data

(spasi) (0.15 + 0.17 + 0.16 + 0.17 + 0.16

+ 0.16 + 0.16 + 0.16 + 0.15 +

0.16) / 10

0.16

e (0.08 + 0.1 + 0.11 + 0.1 + 0.09 +

0.08 + 0.08 + 0.1 + 0.1 + 0.1) /

10

0.10

a (0.07 + 0.06 + 0.07 + 0.07 + 0.06

+ 0.07 + 0.08 + 0.06 + 0.06 +

0.08) / 10

0.07

t (0.06 + 0.06 + 0.07 + 0.06 + 0.07

+ 0.07 + 0.08 + 0.07 + 0.06 +

0.06) / 10

0.07

o (0.06 + 0.05 + 0.05 + 0.05 + 0.07

+ 0.07 + 0.06 + 0.06 + 0.06 +

0.06) / 10

0.06

Tabel 5.8 Peluang karakter terbanyak data bahasa Inggris


84

Dari data bahasa Inggris tersebut, karakter terbanyak adalah ‘spasi’

dengan peluang 0.16 yang mempunyai selisih cukup jauh dengan karakter

terbanyak kedua. Rata-rata rasio kompresi Huffman Modifikasi untuk data bahasa

Inggris yaitu 27.11.

Beberapa hasil dari Huffman Statis dan Huffman Dinamis memiliki rasio

kompresi bernilai negatif. Semakin variatif karakter yang muncul, akan

memperkecil rasio kompresi yang dihasilkan, baik oleh algoritma Huffman Statik,

maupun pada algoritma Huffman Dinamis[10].

Di dalam data bahasa Indonesia dan Inggris, selain terdapat karakter

huruf, juga terdapat karakter seperti tanda baca, tanda ekspresi dan lain-lain yang

menyebabkan hasil rasio menjadi negatif.


85

6 BAB VI

PENUTUP

Bab akhir tulisan ini berisikan tentang kesimpulan dan saran. Kesimpulan

berisi tentang hal-hal yang berkaitan hasil pengujian ketiga algoritma. Saran akan

memuat hal-hal yang berkaitan tentang pengembangan sistem dalam tulisan ini.

6.1 Kesimpulan

Dari hasil pengujian dan analisa yang telah dilakukan, dapat disimpulkan

beberapa hal antara lain :

1. Hasil rata-rata ratio compression yang didapat dalam pengujian

perbandingan jumlah bit dari ketiga algoritma yaitu Huffman Statis =

9.53, Huffman Dinamis = 5.91 dan Huffman Modifikasi = 38.52.

berdasarkan hasil rata-rata tersebut, Huffman Modifikasi memiliki

tingkat ratio compression tinggi yang berarti lebih optimal.

2. Modifikasi algoritma Huffman yang telah dilakukan terbukti dapat

lebih baik dibandingkan dengan algoritma Huffman Statis dan

Huffmna Dinamis. Dapat dilihat dalam waktu yang diperlukan untuk

sekali proses dan ukuran file hasil kompresi.

3. Pada algoritma Huffman terbentuk struktur pohon biner dengan level

yang dalam untuk melakukan kompresi file. Dengan begitu sangat

memungkinkan untuk melakukan perubahan atau pengembangan

terhadap algoritma tersebut. Algoritma dimodifikasi untuk


86

memperpendek level pohon biner dengan cara membuat struktur

pohon menjadi lebih setimbang dibandingkan dengan algoritma

Huffman.

4. Berdasarkan pengujian hubungan peluang kemunculan karakter dan

jumlah bit hasil kompresi, dalam data bahasa Indonesia karakter ‘a’

lebih banyak muncul dalam setiap teks dengan peluang rata-rata 0.14,

selanjutnya (spasi) = 0.13, n = 0.08, e = 0.07 dan terakhir i = 0.06.

Dalam data bahasa Inggris, karakter ‘spasi’ lebih banyak muncul

dengan peluang rata-rata 0.16, selanjutnya e = 0.10, a = 0.07, t = 0.07

dan o = 0.06.

5. Berdasarkan pengujian terhadap teks dengan bahasa Indonesia dan

Inggris, terdapat rasio kompresi dengan nilai negatif. Nilai negatif

terjadi terjadi karena banyaknya variasi karakter yang terdapat dalam

teks.

6. Rasio kompresi Huffman modifikasi untuk data bahasa Indonesia

adalah 24.8 dan bahasa Inggris adalah 27.11. Sehingga dapat diambil

kesimpulan dalam penelitian ini bahwa untuk pengujian 10 data

bahasa Indonesia dan bahasa Inggris, algoritma huffman lebih

optimal digunakan dalam teks berbahasa Inggris.

6.2 Saran

Melihat dari lamanya waktu yang diperlukan dalam proses kompresi,

penulis memberikan saran untuk mencoba menggunakan bahasa pemrograman

selain Java. Hal ini juga dimaksudkan sebagai pembanding kinerja Java dan


87

bahasa pemrograman lainnya dalam melakukan proses kompresi. Pengujian untuk

data yang banyak juga perlu dilakukan untuk melihat lebih jauh kinerja dari

algoritma Huffman.

Selain itu dapat dikembangkan juga untuk kompresi citra menggunakan

algoritma Huffman. Karena sifat algoritma Huffman yang tidak memperbolehkan

hilangnya data dalam proses kompresi, dapat dilakukan pada data citra bidang

kesehatan seperti hasil rontgen.


88

DAFTAR PUSTAKA

[1]Mamta Sharma, “Compression Using Huffman Coding”, International Journal

of Computer Science and Network Security, VOL.10 No.5, May 2010

[2]V.V.Sunil Kumar dan M.Indra Sena Reddy ,”Image Compression Technique

by using Wavalet Transform”, Jurnal of Information Engineering and

Applications, Vol 2, No.5, 2012

[3] O’Hanen, B., and Wisan M., “JPEG Compression”. December 16, 2005.

[4] Munir, Rinaldi. 2008. Diktat kuliah IF2091 Struktur Diskrit. Program Studi Teknik

Informatika. Sekolah Teknik Elektro dan Informatika, Institut Teknologi

Bandung.

[5] Parlante, Nick , “Binary Trees”, http://cslibrary.stanford.edu/110/

[6] Leweler,A. Debra Ana Daniel S. Hirchsberg, “Data Compression”

[7] Wardoyo,Irwan dkk. “Kompresi Teks dengan menggunakan Algoritma

Huffman”

[8] Tim Dosen TI, “Binary Tree”, Universitas Sanata Dharma Yogyakarta.

[9] Tim Dosen TI, “Advanced Sort”, Universitas Sanata Dharma Yogyakarta.

[10] Silalahi, Bib Paruhum, Julio Adisantoso dan Danny Dimas Sulistio,

“Perbandingan Algoritma Huffman Statik Dengan Algoritma Huffman

Adaptif Pada Kompresi Data Teks”.


halaman judul perbandingan kompresi teks … · gambar 2.2 pohon biner sempurna dan beberapa contoh...

Documents