JURNAL IT
VOLUME 15, DESEMBER 2014
STMIK HANDAYANI
PENGGUNAAN POHON BINER HUFFMAN UNTUK KOMPRESI DATA TEKS Sitti Zuhriyah Sistem Komputer, STMIK Handayani Makassar
[email protected]
Abstrak Di dalam dunia komputer, semua informasi, baik berupa tulisan, gambar ataupun suara semuanya disimbolkan dengan kode biner, yaitu deretan angka 0 dan 1 yang mewakili suatu simbol. David A. Huffman dalam tulisannya “A Method for the Construction of MinimumRedundancy Codes” memberikan suatu alternatif untuk memperkecil ukuran data yang sangat berguna dalam hal pengiriman ataupun penyimpanan data. Aplikasi penggambar pohon biner Huffman untuk data teks ini menerima input berupa teks dan kemudian berdasarkan input tersebut, menghitung frekuensi kemunculan tiap karakter di dalamnya, menggambarkan pohon biner huffman dan terakhir membuat tabel kode Huffman. Aplikasi ini juga dapat menggambarkan proses menggambar pohon biner Huffman secara bertahap sehingga dapat membantu untuk memahami proses menggambar pohon Huffman. Kata Kunci : Pohon Biner, Huffman, Kompresi
PENGGUNAAN POHON BINER HUFFMAN UNTUK KOMPRESI DATA TEKS
29
JURNAL IT
VOLUME 15, DESEMBER 2014
STMIK HANDAYANI
I. PENDAHULUAN Perkembangan teknologi yang semakin pesat mendorong kemajuan perkembangan teknologi informasi. Berbagai sarana dan fasilitas dijadikan media untuk memberikan ataupun mendapatkan informasi. Akses internet pun hampir menjadi suatu komponen yang tidak terpisahkan dari kehidupan perkantoran. Informasi berupa tulisan, gambar ataupun suara terus menerus dikirim dan diterima untuk berbagai macam keperluan. Namun, tidak semua pengguna media informasi mengetahui bahwa semua informasi baik berupa tulisan, gambar, ataupun suara semua disimbolkan dengan kode biner, yaitu deretan angka 0 dan 1 yang mewakili sebuah simbol. Misalnya huruf A di dalam teks disimbolkan dengan kode ASCII berukuran 8 bit yaitu 01000001. Dengan demikian jumlah bit untuk mewakili n huruf adalah 8 × n bit. Sedangkan dalam penyebaran ataupun penerimaan informasi huruf atau gambar yang biasa digunakan berjumlah puluhan bahkan ratusan. David A. Huffman dalam tulisannya "A Method for the Construction of MinimumRedundancy Codes" menawarkan suatu metode untuk membangun kode-kode yang optimum. Pada saat kode-kode yang optimum digunakan, jumlah digit yang diperlukan dalam pengkodean menjadi lebih sedikit. Hal ini berguna dalam penyimpanan data yang lebih kecil dan waktu pengiriman data informasi yang lebih singkat. Mengingat data atau pesan yang sering dikirim ataupun diterima seringkali berukuran sangat besar. Dalam tulisannya Huffman menjelaskan suatu metode untuk menentukan pengkodean simbol yang optimum berdasarkan probabilitas kemunculan kode tersebut di dalam sekumpulan kode. Hasil akhir dari algoritma Huffman adalah kamus kode yang optimum untuk suatu kumpulan kode. Jika karakter-karakter pada data teks yang biasanya dikodekan dengan kode ASCII digantikan dengan kode Huffman, maka panjang keseluruhan kumpulan kode menjadi lebih pendek. Sehingga memungkinkan ukuran penyimpanan data yang lebih kecil atau waktu pengiriman data yang lebih singkat. II. TINJAUAN PUSTAKA 2.1. Pohon Biner Di dalam ilmu matematika pohon ( tree) adalah graf yang tidak berarah terhubung tetapi tidak mengandung sirkuit [], sedangkan pohon biner adalah “ pohon berakar dimana setiap simpul cabangnya mempunyai paling banyak dua buah anak”. Di dalam ilmu komputer, pohon atau Tree adalah suatu struktur data yang terdiri dari simpul-simpul atau nodes yang terhubung satu sama lain. Jika hubungan antar simpul digambarkan, akan menyerupai sosok pohon nyata. Tiap simpul di dalam suatu pohon dapat memiliki atau tidak memiliki anak atau orangtua. Tiap simpul dapat memiliki maksimal satu orangtua, sedangkan jumlah anak yang dapat dimiliki suatu simpul adalah tidak terbatas.
Gambar 2.1. pohon biner
PENGGUNAAN POHON BINER HUFFMAN UNTUK KOMPRESI DATA TEKS
30
VOLUME 15, DESEMBER 2014
JURNAL IT STMIK HANDAYANI
2.2. Pohon Biner Huffman Data di dalam komputer disimpan dalam bytes. Pengkodean Huffman adalah suatu teknikkompresi lossless yang memanfaatkan kenyataan bahwa tidak semua byte muncul dengan frekuensi yang sama dalam suatu data[1]. Dengan begitu, penghematan ukuran data dapat dicapai memvariasikan panjang kode yang mewakili simbol-simbol di dalam data tersebut. Simbol yang lebih sering ditemukan dikodekan dengan jumlah bit yang lebih sedikit. Hal ini dapat dicapai dengan langkah-langkah berikut: Kompresi lossless yang memanfaatkan kenyataan bahwa tidak semua byte muncul dengan frekuensi yang sama dalam suatu data[1]. Dengan begitu, penghematan ukuran data dapat dicapai memvariasikan panjang kode yang mewakili simbol-simbol di dalam data tersebut. Simbol yang lebih sering ditemukan dikodekan dengan jumlah bit yang lebih sedikit. Hal ini dapat dicapai dengan langkah-langkah berikut: 1. Buat daftar frekuensi kemunculan setiap simbol. 2. Dengan informasi frekuensi kemunculan simbol-simbol tersebut, bangun suatu pohon biner Huffman. a. Buat daftar daun yang mewakili setiap simbol di dalam data. Asosiasikan setiap daun dengan frekunsi kemunculan simbol yang diwakilinya. b. Pilih dua daun (atau simpul) yang memiliki frekuensi terendah. Keluarkan simpul-simpul tersebut dari daftar. c. Buat sebuah simpul baru yang mewakili gabungan dari kedua daun (atau simpul) yang dikeluarkan sebelumnya. d. Jadikan kedua daun yang dikeluarkan sebagai anak dari simpul baru. Asosiasikan simpul baru dengan total frekuensi dari kedua anaknya. 3. Ulangi proses di atas sampai hanya tersisa satu buah simpul. Simpul ini akan menjadi simpul yang teratas dan oleh karena itu merupakan simpul akar. Sebagai contoh, misalkan kita memiliki data teks “ ada uang ada barang”, yang jika dikodekan dengan kode ASCII sebagai berikut: 011000010110010001100001001000000111010101100001011011100110011100100000 011000010110010001100001011000100110000101110010011000010110111001100111 Data tersebut terdiri dari 152 bit. Data tersebut akan dikompresi dengan menggunakan Huffman. III. PEMBAHASAN Pada contoh data teks “ ada uang ada barang” dengan kode ASCII sebagai berikut : 011000010110010001100001001000000111010101100001011011100110011100100000011 000010110010001100001011000100110000101110010011000010110111001100111. Yang mengandung 152 bit akan dikompresi dengan menggunakan Pohon Huffman. Pertama yang kita lakukan adalah membuat daftar frekuensi sebagai berikut: Tabel 3.1. Simbol Frekuensi b 1 u 1 r 1 n 2 g 2 d 2 <spasi> 3 a 7
PENGGUNAAN POHON BINER HUFFMAN UNTUK KOMPRESI DATA TEKS
31
JURNAL IT
VOLUME 15, DESEMBER 2014
STMIK HANDAYANI
Kemudian dari daftar frekuensi kita buat daun-daun yang mewakili setiap simbol dan mengasosiakan simbol tersebut dengan frekuensinya. Seperti gambar berikut: b,1
u,1
r,1
n,2
g,2
spa,
d,2
a,7
3 Gambar 3.1: Daftar Daun Simbol Pada Data "ada uang ada barang" Setelah itu daun b dan u akan dibuat daun yang baru yaitu bu, daun bu akan menjadi orantua dari simpul b dan u. lalu menyisipkannya ke dalam daftar sesuai dengan posisi frekuensinya. Ditunjujjan dengan gambar sebagai berikut: r,1
n,2
g,2
d,2
bu,2
b,1
spa, 3
a,7
r,1
Gambar 3.2 :Langkah Kedua Membuat Pohon Biner Huffman Pada Data "ada uang ada barang" Selanjutnya dilakukan dengan cara yang sama secara berulang sehingga terbentuk pohon Huffman yang baru seperti berikut g,2
d,2
bu,2
spa,3
b,1
a,7
rn,3
u,1
r,1
n,2
Gambar 3.3 :Langkah Ketiga Membuat Pohon Biner Huffman Pada Data "ada uang ada barang" bu,2
b,1
spa,3
u,1
rn,3
r,1
gd,4
n,2
g,2
a,7
d,2
Gambar 3.4 :Langkah Keempat Membuat Pohon Biner Huffman Pada Data "ada uang ada barang" rn,3
r,1
bu<sp>,5
gd,4
n,2
g,2
bu,2
d,2
b,1
PENGGUNAAN POHON BINER HUFFMAN UNTUK KOMPRESI DATA TEKS
a,7
sp,3
u,1
32
JURNAL IT
VOLUME 15, DESEMBER 2014
STMIK HANDAYANI
Gambar 3.5 :Langkah Kelima Membuat Pohon Biner Huffman Pada Data "ada uang ada barang" bu<sp>,5
bu,2
rngd,7
a,7
sp,3
b,1
rn,3
r,1
u,1
gd,4
g,2
n,2
d,2
Gambar 3.6 :Langkah Keenam Membuat Pohon Biner Huffman Pada Data "ada uang ada barang" rngd,7
bu<sp>a,12
rn,3
r,1
gd,4
n,2
d,2
g,2
a,7
bu<sp>,5
bu,2
b,1
sp,3
u,1
Gambar 3.7: Langkah Ketujuh Membuat Pohon Biner Huffman Pada Data "ada uang ada barang" rngdbu<sp>a,19
1
0
bu<sp>a,12
rngd,7 1
0
gd,4
rn,3 1
0 r,1
n,2
1
0 a,1
bu<sp>,5
0
1
0
g,2
d,2
bu,2
1 sp,3
0
1
b,1
u,1
Gambar 3.8: Langkah Kedelapan Membuat Pohon Biner Huffman Pada Data "ada uang ada barang"
PENGGUNAAN POHON BINER HUFFMAN UNTUK KOMPRESI DATA TEKS
33
VOLUME 15, DESEMBER 2014
JURNAL IT STMIK HANDAYANI
Dengan menelusuri pohon biner Huffman yang telah dibuat, kita dapat membuat tabel kode Huffman sebagai berikut: Tabel 3.2: tabel kode Huffman Simbol Frekuensi Kode Huffman r 1 000 n 2 001 g 2 010 d 2 011 b 1 1000 u 1 1001 <spasi> 3 101 a 7 11 Sehingga pesan teks “ ada uang ada barang” jika disimbolkan dengan kode Huffman maka menjadi, 1101111101100111001010101110111110110001100011001010 Data hasil kompresi data kode ASCII ke kode Huffman menjadi 52 bit. Jika dibandingkan dengan 152 bit sebelum kompresi, maka data ini jauh lebih pendek dari data sebelum dikompresi. Akan tetapi, agar dapat didekompresi menjadi data semula, tentunya tabel kode Huffman yang telah dibuat pada saat proses kompresi perlu disertakan pada data hasil kompresi. Hal ini akan mengakibatkanmeningkatnya ukuran data. Peningkatan ukuran data tersebut sangat bergantung dengan pengkodean tabel Huffman tersebut. Penggambaran atau pembangunan tabel kode Huffman tersebut akan dibahas pada penelitian selanjutnya. IV. KESIMPULAN Kesimpulan dari penelitian ini adalah bahwa kode Huffman bisa digunakan untuk mengkompresi data teks, sehingga dapat menghemat sistem penyimpana data informasi serta mempercepat waktu pengiriman informasi.
DAFTAR PUSTAKA [1] Huffman, David A., 1952. A Method for the Construction of Minimum-Redundancy Codes, Proceedings of I.R.E. (September 1952) [2] Zulen, Alvin Andhika. "Penerapan Pohon Biner Huffman Pada Kompresi Citra", http://www.informatika.org/~rinaldi/Matdis/2008-2009/Makalah2008/Makalah0809-077.pdf. Diakses 08/02/2011. [3] http://en.wikipedia.org/wiki/Selection_sort. Diakses pada 9 Februari 2011.
.
PENGGUNAAN POHON BINER HUFFMAN UNTUK KOMPRESI DATA TEKS
34
