MAKALAH
KODE HUFFMAN
“UNTUK
KOMPRESI PESAN”
Disusun oleh :
Nama
: Bayu Wira Saputra
NIM : 17103025
Kelas
: S1 Sistem Informasi 01-A
PROGRAM
STUDI SISTEM INFORMASI
FAKULTAS
TEKNOLOGI INFORMATIKA DAN INDUSTRI
INSTITUT
TEKNOLOGI TELKOM PURWOKERTO
2019
KATA PENGANTAR
Segala puji bagi Allah SWT yang telah memberikan
nikmat serta hidayah-Nya terutama nikmat kesempatan dan kesehatan sehingga kami
bis menyelesaikan makalah mata kuliah “Matematika diskrit”. Shalawat serta
salam kita sampaikan kepada Nabi besar kita Muhammad SAW yang telah memberikan
pedoman hidup yakni Al-Qur’an dan sunnah untuk keselamatan umat di dunia.
Makalah ini merupakan salah satu tugas mata
kuliah Matematika diskrit di program studi Sistem Informasi Fakultas Teknologi
Informatika dan Industri Pada IT Telkom Purwokerto. Selanjutnya penulis
mengucapkan terima kasih yang sebesar-besarnya kepada Bapak Yogo selaku dosen
mata kuliah Matematika Diskrit dan kepada segenap pihak yang telah memberikan
bimbingan serta arahan selama penulisan makalah ini.
Penulis menyadari bahwa terdapat banyak
kekurangan dalam penulisan makalah ini, maka dari itu penulis mengharapkan
kritik dan saran yang membangun dari para pembaca demi kesempurnaan makalah
ini.
Purwokerto, 16 Juni 2019
Penyusun
DAFTAR ISI
COVER………………………………………………………………………....….i
KATAPENGANTAR……………………………………………………………..ii
DAFTAR ISI…………………………………………………...……..........……..iii
BAB I. PENDAHULUAN
1.1 LatarBelakang………………………………………….……..…………….....1
1.2 RumusanMasalah…………………………………….…..………............……2
1.3 Tujuan……………………………………………….……………….………..2
BAB II. DASAR TEORI
2.1 Definisi kodehuffman………………….….…………………………………3
2.2 Contoh soal
KodeHuffman……..………….………….…………...………..4
2.3 Aplikasi
Kode Human “Untuk Kompresi Pesan”…........................…….…...8
BAB III. PENUTUP
3.1
Kesimpulan.....................................................................................................15
3.2
DaftarPustaka................................................................................................15
BAB I
PENDAHULUAN
1.1 Latar Belakang
Dalam berkomunikasi, seseorang terkadang tidak pernah berpikir
bagaimana terjadinya penyimpanan data, berapa besar tempat yang dibutuhkan
untuk menyimpan data tersebut dan berapa lama waktu yang dibutuhkan dari mereka
menulis sampai terkirimnya suatu pesan ketempat yang dituju. Orang awam tidak pernah mau mengerti apa,
mengapa dan bagaimana ilmu tentang pengiriman data dan penyimpanan data.
Bagi mereka yang penting
adalah apa yang mereka inginkan dapat terpenuhi dan dapat dicapai dalam waktu yang singkat dan hasilnya
akurat dan juga memuaskan Oleh karena itu kita sebagai ilmuwan kecil harus
tanggap atas semua keadaan tersebut di atas, karena sebenarnya semua
permasalahan di atas memang bukan permasalahan mereka. Tetapi permasalahan di
atas adalah permasalahan kita, yang harus kita pecahkan sedemikian rupa, sesuai
dengan ilmu pengetahuan yang kita miliki saat ini. Dalam ilmu Komunikasi data, pesan yang
dikirim kepada seseorang, seringkali ukurannya terlalu besar, sehingga
membutuhkan tempat penyimpanan yang terlalu besar pula.
Demikian juga pesan yang terlalu besar, akan membutuhkan waktu
pengiriman yang lebih lama bila dibandingkan dengan pesan yang berukuran
relative lebih kecil. Dua masalah tersebut di atas, sebenarnya bisa diatasi
dengan pengkodean pesan dengan tujuan agar isi pesan yang sebenarnya besar,
bisa dibuat sesingkat mungkin sehingga waktu pengiriman yang mestinya lama bisa
dibuat relatif lebih cepat dan tempat penyimpanan yang besar bisa dibuat
relatif lebih efisien dibandingkan dengan sebelum dilakukan pengkodean. Berdasarkan latarbelakang permasalahan di
atas, maka penulis tertarik untuk melakukan pembahasan dan penulisan serta tata
cara pemampatan data atau yang lebih terkenal dengan istilah kompresi data
dengan mengambil judul Kode Huffman untuk pemampatan/Kompresi Data.
1.2 Rumusan Masalah
1.
Definisi
dari kode huffman.
2.
Contoh
soal kode huffman
3.
Aplikasi
kode huffman yaitu dengan cara menggunakan kode Huffman untuk pemampatan atau
Compression data agar permasalahan seperti diatas bisa teratasi dengan baik
1.3 Tujuan
1.
Mengetahui
dan mempelajari definisi dari kode huffman.
2.
Contoh
soal kode dari kode huffman.
3.
Menerapkan
kode Huffman untuk memampatkan/mengkompresi data, agar dapat tercapai:
a. Ruang
penyimpanan yang relative lebih kecil dibandingkan sebelumnya b. Waktu
pengiriman pesan relative lebih cepat dibandingkan sebelumnya
BAB II
PEMBAHASAN
2.1 Definisi kode huffman
Algoritma Huffman merupakan algoritma yang dikembangkan oleh David A. Huffman yang
digunakan untuk menemukan prefix code yang optimal dan dipublikasikan dalam
sebuah paper “A Method for the Construction of
Minimum-Redundancy Codes” pada tahun 1952.
Algoritma Huffman menggunakan
prinsip pengkodean yang mirip dengan kode Morse, yaitu tiap karakter (simbol)
dikodekan hanya dengan rangkaian beberapa bit, dimana karakter yang sering
muncul dikodekan dengan rangkaian bit yang pendek dan karakter yang jarang
muncul dikodekan dengan rangkaian bit yang lebih panjang. Berdasarkan tipe peta
kode yang digunakan untuk mengubah pesan awal (isi data yang dimasukkan)
menjadi sekumpulan code-word, algoritma Huffman termasuk ke dalam kelas
algoritma yang menggunakan metode statik, yaitu metode yang selalu menggunakan
peta kode yang sama. Metode ini membutuhkan dua fase (two-phase), yaitu fase pertama untuk menghitung
probabilitas kemunculan tiap simbol dan menentukan peta kodenya, dan fase kedua
untuk mengubah pesan menjadi kumpulan kode yang akan ditransmisikan.
Sedangkan berdasarkan teknik
pengkodean simbol yang digunakan, algoritma Huffman menggunakan metode symbol-wise, yaitu
metode yang menghitung kemunculan dari setiap simbol dalam satu waktu, dimana
simbol yang sering muncul diberi kode lebih pendek dibandingkan dengan simbol
yang jarang muncul.
2.2 Contoh soal Kode Huffman
Metode dari Huffman code ini bisa kita lihat
dari Contoh soal kode Huffman
berikut:
Dimisalkan pada sebuah kalimat
terdapat huruf-huruf yang muncul dengan banyaknya kemunculan adalah
sebagai berikut:
Huruf
|
Frekuensi
|
a
|
5
|
b
|
7
|
c
|
10
|
d
|
14
|
e
|
20
|
Cara mencari kode huffman dijelaskan di bawah
ini:
Di bawah ini terdapat contoh metode huffman tree atau disebut juga metode pengakaran dimana kita akan membuat suatu pola pengakaran pada pohon. Langkah pembentukan pohon huffman adalah sebagai berikut:
Di bawah ini terdapat contoh metode huffman tree atau disebut juga metode pengakaran dimana kita akan membuat suatu pola pengakaran pada pohon. Langkah pembentukan pohon huffman adalah sebagai berikut:
Untuk membuat Huffman Code pertama kita harus
mengurutkan data frekuensi kemunculan dari yang trekecil seperti tabel diatas,
lalu kita jumlah kan setiap data secara berpasangan dari yang terkecil:
maka kita mulai dengan menjumlahkan a
dan b
Maka tabel berubah menjadi sebagai berikut:
Huruf
|
Frekuensi
|
c
|
10
|
ab
|
12
|
d
|
14
|
e
|
20
|
Dari tabel di atas kita kembali jumlahkan dua
nilai terkecil..
c dan ab
Maka tabel berubah menjadi sebagai berikut:
Huruf
|
Frekuensi
|
d
|
14
|
e
|
20
|
abc
|
22
|
Dari tabel di atas kita kembali jumlahkan dua
nilai terkecil..
d dan e
Maka tabel berubah menjadi sebagai berikut:
Huruf
|
Frekuensi
|
abc
|
22
|
de
|
34
|
Dari tabel di atas kita kembali jumlahkan dua
nilai terkecil..
abc dan de
Lalu, karena semua Huruf telah dijumlahkan,
kita tambahkan angka 0 dikiri setiap cabang, dan angka 1 dikanan setiap
cabang, seperti gambar di bawah ini:
Dari data metode pengakaran Hufman tree di
atas di dapatkan Codeword untuk setiap huruf adalah sebagai berikut:
Huruf
|
CodeWord
|
a
|
000
|
b
|
100
|
c
|
10
|
d
|
01
|
e
|
11
|
Dari tabel diatas kita mendapatkan kode yang
unik untuk setiap huruf dengan menggunakan Metoda Hufman Tree pada Hufman
Code.
2.3 Aplikasi Kode Human “Untuk
Kompresi Pesan”
1. Penerapan
Agar bisa menerapkan kode Huffmann, kita akan
menguji coba dasar teori yang sudah dijelaskan di atas untuk diterapkan dalam
suatu kalimat. Misalnya kalimatnya seperti di bawah ini: Gunakan kode Huffmann
untuk mengkompres suatu pesan yang dikirimkan kepada seseorang dengan susunan
kalimat sebagai berikut: “ HARI INI KITA
MAKAN SIANG DI MANA”
Untuk mendapatkan kode Huffmann kita harus
mengikuti langkah-langkah sesuai dengan petunjuk:
1. Menentukan Probabilitas atau peluang dari
kemunculan setiap karakter
2. Hasil penghitungannya diletakkan dalam
table
3. Membuat pohon biner
4. Menentukan kode setiap karakter
5. Menghitung berapa banyaknya bit yang
digunakan
6. Membandingkan hasil Kode Huffmann dengan
kode ASCII
Selanjutnya kita akan melakukan penghitungan
satu per satu untuk setiap karakter :
Langkah Pertama: Menentukan kerapatan masing-masing karakter
dalam susunan kalimat di atas Banyaknya huruf keseluruhan adalah = 27 karakter
terdiri dari:
Huruf “A” = 7, Huruf “I” = 6, Huruf “N”= 4,
Huruf “M” = 2 , Huruf “K” = 2 , Huruf “H” = 1, Huruf “ R” = 1, Huruf “T” = 1,
Huruf “ S” = 1, Huruf “G” = 1 dan Huruf “ D” = 1 Sehingga
Langkah kedua: Menentukan probabilitas Masingmasing
karakter adalah sebagai berikut
Huruf “A” = 7/27, Huruf “I”= 6/27, Huruf ”N”
= 4/27, Huruf “M” = 2/27, Huruf “K” = 2/27, Huruf “H” = 1/27, Huruf “R” = 1/27,
Huruf “T” = 1/27, Huruf “S” = 1/27, Huruf “G” = 1/27, Huruf “ D” = 1/27.
Apabila hasil tersebut ditabulasikan menjadi
seperti pada tabel 3.
Langkah ketiga: Membuat tabel seperti Berikut:
Tabel 3: Tabel Kerapatan dan Peluang untuk
setiap karakter [2]
Langkah ke empat: Membuat pohon biner seperti pada Gambar 2
[3].
Langkah kelima: Ringkasan hasil pembuatan pohon biner untuk
setiap karakter adalah sebagai berikut [3]:
A = 00
M =
110
I = 010
K =
1110
S =
0110
H =
11110
G =
01110
R =
111110
D =
01111
T =
111111
N = 10
Bila dibuat tabulasi bisa dinyatakan sebagai
berikut:
Tabel 4: Kode Huffman untuk Kerapatan dan
Peluang setiap karakter
Langkah keenam: Hasil rekapitulasi akhir
adalah sebagai berikut [4]:
a. Banyaknya bit untuk Huruf “ A “ =
2 * 7 = 14
b. Banyaknya bit untuk Huruf “ I
“ =
3 * 6 = 18
c. Banyaknya bit untuk Huruf “ N “
= 2 * 4 = 8
d. Banyaknya bit untuk Huruf “ M “ =
3 * 2 = 6
e. Banyaknya bit untuk Huruf “ K “ =
4 * 2 = 8
f. Banyaknya bit untuk Huruf “ H “ =
5 * 1 = 5
g. Banyaknya bit untuk Huruf “ R “ =
6 * 1 = 6
h. Banyaknya bit untuk Huruf “ T “ =
6 * 1 = 6
i.
Banyaknya bit untuk Huruf “ S “ = 4 * 1 =
4
j. Banyaknya bit untuk Huruf “ G “ =
5 * 1 = 5
k. Banyaknya bit untuk Huruf “ D “ =
5 * 1 = 5
Hasil akhir secara keseluruhan:
Kalimat yang di kodekan adalah: “HARI INI KITA
MAKAN SIANG DI MANA” [5] Dengan Kode ASCII: 27 * 8 Bit = 216 Bit. Dengan Kode
Huffmann 85 Bit adalah 85/216 * 100% = 39,35 %. Sehingga dengan kode Huffmann
bisa mengurangi beban lebih dari 60 %.
Kode Huffman Tidak Unik
Untuk membuktikan bahwa Kode Huffman tidak
unik, bisa dilakukan dengan mambuat pohon biner seperti pada Gambar 3.
Dari pohon biner pada gambar 3 di atas, bila
dibuat tabulasi bisa dinyatakan seperti pada tabel 5 berikut:
Tabel 5: Kode Huffman untuk Kerapatan dan
Peluang setiap karakter dari gambar 3
Hasil rekapitulasi akhir adalah sebagai
berikut:
a. Banyaknya bit untuk Huruf “ A “ =
2 * 7 = 14
b. Banyaknya bit untuk Huruf “ I
“ =
2 * 6 = 12
Gambar 4.
Contoh lain untuk membuktikan kode Huffman tidak uni
c. Banyaknya bit untuk Huruf “ N “
= 3 * 2 = 6
d. Banyaknya bit untuk Huruf “ M “ =
3 * 4 = 12
e. Banyaknya bit untuk Huruf “ K “ =
2 * 4 = 8
f. Banyaknya bit untuk Huruf “ H “ =
1 * 5 = 5
g. Banyaknya bit untuk Huruf “ R “ =
1 * 5 = 5
h. Banyaknya bit untuk Huruf “ T “ =
1 * 4 = 4
i. Banyaknya bit untuk Huruf “ S “ =
1 * 5 = 5
j. Banyaknya bit untuk Huruf “ G “ =
1 * 6 = 6
k. Banyaknya bit untuk Huruf “ D “ =
1 * 6 = 6
Maka, perbandingan hasil akhir secara
keseluruhan adalah dengan kode ASCII: 27 * 8 Bit = 216 Bit. Dengan Kode
Huffmann 83 Bit adalah 83/216 * 100% = 38,43 %. Dengan demikian, kode Huffman
terbukti mengurangi beban secara signifikan.
Contoh lain untuk membuktikan kode Huffman
tidak unik diperlihatkan pada gambar 4.
Ringkasan hasil pembuatan pohon Biner untuk
setiap karakter pada gambar 4 adalah sebagai berikut:
A = 00
I = 10
N = 010
M = 110
K = 0110
H =
1110
S = 01110
R = 11110
G = 011110
T = 11111
D = 011111
Tabel 6 berikut menunjukkan representasi
kerapatan dan peluang kode Huffman dari gambar 4.
Hasil Rekapitulasi akhir adalah sebagai
berikut:
a. Banyaknya bit untuk Huruf “ A “ =
2 * 7 = 14
b. Banyaknya bit untuk Huruf “ I
“ =
2 * 6 = 12
c. Banyaknya bit untuk Huruf “ N “
= 3 * 2 = 6
d. Banyaknya bit untuk Huruf “ M “ =
3 * 4 = 12
e. Banyaknya bit untuk Huruf “ K “ =
4 * 2 = 8
f. Banyaknya bit untuk Huruf “ H “ =
4 * 1 = 4
g. Banyaknya bit untuk Huruf “ R “ =
5 * 1 = 5
h. Banyaknya bit untuk Huruf “ T “ =
5 * 1 = 5
i. Banyaknya bit untuk Huruf “ S “ =
5 * 1 = 5
j. Banyaknya bit untuk Huruf “ G “ =
6 * 1 = 6
k.
Banyaknya bit untuk Huruf “ D “
= 6 * 1 = 6
Perhitungan hasilnya adalah sebagai berikut:
Dengan kode ASCII: 27 * 8 Bit = 216 Bit,
dengan Kode Huffmann 93 Bit adalah 93/216 * 100% = 43,056 %.
BAB III
PENUTUP
3.1
Kesimpulan
Dari Hasil uji
coba penerapan dan Penghitungan kode Huffman, maka dapat disimpulkan antara
lain bahwa:
1.
Kode Huffmann
benar-benar lebih sederhana bila di bandingkan dengan kode ASCII yang selama
ini dipakai masyarakat umum.
2.
Dengan
menggunakan kode Huffmann ternyata dapat mengurangi beban alias dapat
mengkompres data lebih dari 50%.
3.
Penghitungan
kode Huffmann tidak unik, tetapi bias bermacam –macam variasi dalam setiap
kalimat yang dikodekan, tetapi semua hasil yang dicapai tetap lebih rendah dari
pada kode ASCII.
3.2 Daftar Pustaka
3.
792-2135-1-SM.pdf
kurang jelas gaada tabelnya
ReplyDelete