bab ii.pdf

Bab II Tinjauan Pustaka

Muhammad Abdul Jabbar Hussein (091344018) Laporan Tugas Akhir Tahun 2013 4

BAB II

TINJAUAN PUSTAKA DAN LANDASAN TEORI

2.1 Tinjauan Pustaka

Metode kompresi Huffman bukanlah merupakan metode baru. Sistem ini

telah banyak diimplementasikan dan terus berkembang seiring dengan

perkembangan teknologi. Diantaranya pernah dijelaskan pada beberapa literatur

yang pernah penulis baca dan menjadikannya sebagai acuan ,yaitu :

1. David Solomon, Data Compression The Complete Reference Fourth

Edition. Buku ini berisi tentang kumpulan metode kompresi data baik teks,

gambar, suara maupun video [1].

2. Irwan Wardoyo, Kompres Text dengan Menggunakan Metode Huffman.

Makalah ini berisi tentang metode kompresi teks dengan menggunakan

metode Static Huffman Code [2].

3. Yeuan-Kuen Lee, Huffman Coding. Power point yang diambil dari

internet berisi tentang penjelasan dari Huffman Code dan Adaptive

Huffman Code [3].

Dari beberapa literatur tersebut, rasio kompresi merupakan salah satu hal

yang harus dipertimbangkan. Metode Adaptive Huffman Code adalah metode

yang digunakan oleh penulis untuk proyek akhir kali ini. Pengkodean secara

adaptif menjadi pertimbangan penulis untuk menghasilkan rasio yang lebih baik

dibandingkan Metode Huffman Code.

2.2 Kompresi Data

Kompresi data atau pemampatan data adalah suatu proses pengubahan

sekumpulan data menjadi suatu bentuk kode untuk menghemat kebutuhan tempat

penyimpanan data dan waktu transmisi data. Saat ini kompresi data sangat

dibutuhkan untuk menghemat ruang penyimpanan, untuk menghemat biaya

pengiriman data dari komputer satu ke komputer lainnya serta untuk mempercepat

proses transfer data. Kompresi data mereduksi ukuran file dengan cara

menghilangkan redudansi atau kemunculan berulang-ulang dari bagian file.

Gambar 2.1 adalah blok dasar dari kompresi data.


Muhammad Abdul Jabbar Hussein (091344018)

Gambar 2.1 Blok dasar kompresi dan dekompresi data

Data asli : merupakan data input yang dikompresi, bisa berupa file text, file

image dsb, sekaligus sebagai output dari proses dekompresi data.

Box kompresi/Dekompresi data : merupakan pemampatan data dan

pengembalian file ke dalam bentuk semula.

Data hasil kompresi : merupakan keluaran dari proses kompresi data.

2.2.1 Faktor Penting Kompresi

Dalam kompresi data, terdapat 4 (empat) faktor penting yang perlu

diperhatikan, yaitu : Time Process (waktu yang dibutuhkan dalam menjalankan

proses), Completeness (kelengkapan data setelah file-file tersebut dikompres),

Ratio compress (ukuran data setelah dilakukan kompresi), Optimaly(perbandingan

apakah ukuran file sebelum dikompres sama atau tidak sama dengan file yang

telah dikompres). Tidak ada metode kompresi yang paling efektif untuk semua

jenis file.

2.2.2 Klasifikasi Teknik Kompresi

a. Entropy Encoding

1. Bersifat lossless

2. Tekniknya tidak berdasarkan media dengan spesifikasi dan karakteristik

tertentu namun berdasarkan urutan data.

3. Statistical encoding, tidak memperhatikan semantik data.

4. Misal: Run-length coding, Huffman coding, Arithmetic coding.

Data

Kompresi

Dekompresi

BitStream



b. Source Coding

1. Bersifat lossy

2. Berkaitan dengan data semantik (arti data) dan media.

3. Misal: Prediction (DPCM, DM), Transformation (FFT, DCT), Layered

Coding (Bit position, subsampling, sub-band coding), Vector quantization

c. Hybrid Coding

1. Gabungan antara lossy + lossless

2. Misal: JPEG, MPEG, H.261, DVI

2.2.3 Sifat Kompresi Berdasarkan Hasil

a. Lossy Compression

Teknik kompresi lossy ini tidak hanya menghilangkan redundansi saja

akan tetapi juga menghilangkan atau membuang bit-bit yang kurang dominan atau

dianggap kurang perlu sehingga akan menghasilkan jumlah bit yang kecil. Tentu

saja ini tidak bisa dilakukan pada file teks atau program, karena setiap bagian file

ini penting .

Kompresi lossy umumnya dilakukan pada data multimedia, seperti

gambar, audio atau video. Sebagai contoh pada file audio, dengan membuang data

suara dengan frekuensi di luar selang 20 Hz-20 KHz, cukup banyak penciutan

ukuran yang dicapai. Telinga manusia tidak dapat mendengarkan suara di luar

selang tersebut, sehingga data yang dibuang memang tidak ada gunanya . Begitu

juga dengan file gambar, karena file gambar tidak mengutamakan ketelitian tetapi

visualisasi objek yang dilihat mata manusia , maka teknik kompresi lossy ini

cocok digunakan untuk file gambar. [4]

b. Lossless

Kompresi lossless digunakan untuk mengkompresi data yang tidak bisa

mengalami perbedaan/perubahan dari aslinya. Dengan kata lain, kompresi lossless

digunakan untuk representasi data yang mengharuskan bersifat lossless, tidak ada

satu pun dari bit data hilang/rusak, karena kerusakan 1 bit saja akan

mengakibatkan data menjadi tidak berguna. Teknik lossless umumnya akan

mencari pola-pola yang terdapat pada file yang ingin dikompresi. Teknik ini akan



menghasilkan rasio ukuran yang lebih kecil pada file yang memiliki tingkat

pengulangan pola yang sedikit, misalnya karena mengandung banyak informasi

yang unik, tidak akan diperoleh rasio yang baik. Oleh karena itu, teknik ini sangat

cocok digunakan untuk mengkompresi data alfanumerik baik berupa teks ataupun

numerik . Gambar 2.2 merupakan skema metode kompresi.

Gambar 2.2 Skema metode kompresi

Secara umum Kompresi data lossless diimplementasikan dengan

menggunakan salah satu jenis pemodelan berikut : Dictionary Based, Statistical

Method, atau Character Oriented.

2.3 Statistical Method

Metode statistik ini adalah suatu cara penyingkatan simbol atau kata dalam

teks dengan cara memperpendek simbol/kata yang memiliki frekuensi

kemunculan terbanyak, karakter yang sering muncul jumlah bitnya dibuat lebih

pendek dari yang jarang muncul, seperti pada algoritma Shannon Fano dan

Huffman code. Pada metode ini, aliran data yang dikompresi akan melewati dua

fase, yaitu : pemodelan dan pengkodean.

Metode

Lossy

Rung Length

Shannon Fano

Dictionary Based Statistical Method

Character Oriented

Losless

Arithmetic Huffman LZW LZ77



Pemodelan diawali dengan menghitung probabilitas kemunculan tiap

simbol pada suatu input, kemudian membentuk suatu tabel translasi dengan

mengikuti aturan sebagai berikut :

1. Tiap-tiap simbol dikodekan dengan kombinasi bit yang berbeda.

2. Simbol dengan probabilitas kemunculan tinggi dikodekan dengan jumlah bit

yang lebih sedikit.

3. Walaupun panjang kodenya berbeda, kode-kode tersebut dapat didekode

secara unik.

Ada dua macam metode pemodelan pada pada statistical method [5], yaitu

metode pemodelan statis dan pemodelan adaptif. Gambar 2.3 menunjukkan proses

dari metode pemodelan statis.

Pada proses kompresi dengan model statis ini terdiri dari dua kali

pembacaan. Yang pertama adalah membaca seluruh file data yang kemudian akan

didapat model berupa tabel frekuensi kemunculan simbol, kemudian membangun

kode-kode berdasarkan model yang ada.

Pembacaan Simbol

Pengkodean Penulisan Kode dan Tabel Frekuensi

Pemodelan

simbol

Penulisan Simbol

Pengkodean Balik

Pembacaan Kode dan Tabel Frekuensi

Pemodelan

Proses Dekompresi

Proses Kompresi

kode

Model Kompresi

Tabel Frekuensi

Kode Simbol

Tabel Frekuensi

Bit-bit kode

Gambar 2.3 Proses kompresi dan dekompresi dengan model statis



Pembacaan yang kedua adalah membaca satu per satu simbol file data

sambil dikodekan berdasarkan kode yang telah terbentuk. Setelah itu model yang

telah terbentuk dikirimkan untuk proses dekompresi.

Pada proses dekompresi dilakukan pembacaan bit-bit hasil kompresi

sambil mencocokkan dengan tabel kode yang pada akhirnya akan dihasilkan

simbol-simbol file data aslinya.

Sedangkan pada metode pemodelan adaptif, data tidak perlu dibaca

terlebih dulu untuk menghitung statistiknya, tetapi statistik itu secara

berkelanjutan diubah setiap pembacaan dan pengkodean sebuah karakter baru.

Gambar 2.4 menunjukkan proses dari metode pemodelan adaptif.

2.4 Dekompresi Data

Dekompresi atau pemulihan data adalah pengambilan aliran (stream)

kode-kode dan perubahan ke dalam bentuk simbol-simbol. Dekompresi ini dapat

dikatakan pula sebagai teknik pengembalian data ke keadaan awal dengan cara

menginverskan proses awal yang dilakukan dengan menggunakan kode kunci

(model) yang diikutkan ke dalam file kompresi .

Pembacaan Simbol

Pengkodean Penulisan Kode

PembaharuanModel

simbol kode

Tabel Bit-bit kode

Model

Kompresi

Pemodelan

simbol

Penulisan Simbol

Pengkodean Balik

Pembacaan Kode

Pemodelan

Proses Dekompresi

Proses Kompresi

Kode Simbol

Tabel Frekuensi

Gambar 2.4 Proses kompresi dan dekompresi dengan model adaptif

PembaharuanModel

Simbol

Model



2.5 Huffman Code

Algoritma Huffman, yang dibuat oleh seorang mahasiswa MIT bernama

David Huffman pada tahun 1952, merupakan salah satu metode paling lama dan

paling terkenal dalam kompresi teks . 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 diinputkan) menjadi sekumpulan codeword, algoritma Huffman

termasuk kedalam kelas algoritma yang menggunakan metode statik . Metoda

statik adalah metoda yang selalu menggunakan peta kode yang sama, metoda ini

membutuhkan dua fase (two-pass): fase pertama untuk menghitung probabilitas

kemunculan tiap simbol dan menentukan peta kodenya, dan fase kedua untuk

mengubah pesan menjadi kumpulan kode yang akan di taransmisikan.

Sedangkan berdasarkan teknik pengkodean simbol yang digunakan,

algoritma Huffman menggunakan metode symbolwise. Metoda symbolwise adalah

metode yang menghitung peluang kemunculan dari setiap simbol dalam satu

waktu, dimana simbol yang lebih sering muncul diberi kode lebih pendek

dibandingkan simbol yang jarang muncul.[2]

2.5.1 Pembentukan Huffman Tree

Kode Huffman pada dasarnya merupakan kode prefiks (prefix code). Kode

prefiks adalah himpunan yang berisi sekumpulan kode biner, dimana pada kode

prefik ini tidak ada kode biner yang menjadi awal bagi kode biner yang lain. Kode

prefix biasanya direpresentasikan sebagai pohon biner yang diberikan nilai atau

label. Untuk cabang kiri pada pohon biner diberi label 0, sedangkan pada cabang

kanan pada pohon biner diberi label 1. Rangkaian bit yang terbentuk pada setiap

lintasan dari akar ke daun merupakan kode prefiks untuk karakter yang

berpadanan. Pohon biner ini biasa disebut pohon Huffman.



Langkah-langkah pembentukan pohon Huffman adalah sebagai berikut[2]:

1. Baca semua karakter di dalam teks untuk menghitung frekuensi

kemunculan setiap karakter. Setiap karakter penyusun teks dinyatakan

sebagai pohon bernode tunggal. Setiap node di-assign dengan

frekuensi kemunculan karakter tersebut, lalu sorting.

2. Gabungkan dua buah pohon yang mempunyai frekuensi terkecil pada

sebuah akar. Setelah digabungkan akar tersebut akan mempunyai

frekuensi yang merupakan jumlah dari frekuensi dua buah pohon-

pohon penyusunnya.

3. Ulangi langkah 2 sampai hanya tersisa satu buah pohon Huffman.

Agar pemilihan dua pohon yang akan digabungkan berlangsung

cepat, maka semua yang ada selalu terurut menaik berdasarkan

frekuensi. Gambar 2.5 merupakan diagram alir proses pembentukan pohon Huffman.

Gambar 2.5 Diagram alir pembentukan Huffman tree

Sebagai contoh, dalam kode ASCII string 7 huruf “ABCDACA”

membutuhkan representasi 7 × 8 bit = 56 bit , dengan rincian yang ditunjukan

pada Tabel 2.1 dan Gambar 2.6.



Tabel. 2.1 Kode ASCII untuk karakter ‘ABCD’

Simbol Kode ASCII A 01000001 B 01000010 C 01000011 D 01000100

Gambar 2.6 Huffman tree untuk karakter ‘ABCDACA’

2.5.2 Proses Encoding Huffman Code

Encoding adalah cara menyusun string biner dari teks yang ada. Proses

encoding untuk satu karakter dimulai dengan membuat pohon Huffman terlebih

dahulu. Setelah itu, kode untuk satu karakter dibuat dengan menyusun nama

string biner yang dibaca dari akar sampai ke daun pohon Huffman.

Langkah-langkah untuk men-encoding suatu string biner pada Static

Huffman adalah sebagai berikut :

1. Tentukan karakter yang akan di-encoding

2. Mulai dari akar, baca setiap bit yang ada pada cabang yang bersesuaian

sampai ketemu daun dimana karakter itu berada

3. Ulangi langkah 2 sampai seluruh karakter di-encoding Sebagai contoh kita

dapat melihat Tabel 2.2, yang merupakan hasil encoding untuk pohon

Huffman pada Gambar 2.6



Tabel 2.2 Codebook Huffman code untuk karakter ‘ABCD’

Simbol Frekuensi Probability Kode Huffman A 3 3/7 1 B 1 1/7 010 C 2 2/7 01 D 1 1/7 011

Dengan menggunakan kode Huffman, pesan ‘ABACCDA’

direpresentasikan menjadi :1010010111011

Sehingga, dengan menggunakan kode Huffman jumlah bit yang

dibutuhkan untuk string ‘ABACCDA’ hanya 13 bit. Kode untuk setiap simbol

tidak boleh merupakan awalan dari kode yang lain sebab akan menimbulkan

keraguan (ambigou) dalam proses decoding. Untuk menentukan bahwa kode

harus unik dan karakter yang sering muncul jumlah bitnya kecil, dapat digunakan

konsep pohon biner.

2.5.3 Proses Decoding Huffman Code

Decoding merupakan kebalikan dari encoding. Decoding berarti menyusun

kembali data dari string biner menjadi sebuah karakter kembali. Decoding dapat

dilakukan dengan dua cara, yang pertama dengan menggunakan pohon Huffman

dan yang kedua dengan menggunakan tabel kode Huffman.

Langkah-langkah men -decoding suatu string biner dengan menggunakan

pohon Huffman adalah sebagai berikut :

1. Baca sebuah bit dari string biner.

2. Mulai dari akar

3. Untuk setiap bit pada langkah 1, lakukan traversal pada cabang yang

bersesuaian.

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

telah dibaca dengan karakter di daun.

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



Gambar 2.7 adalah proses dekode biner ”011” sesuai gambar 2.6 :

Gambar 2.7 Proses decoding bit ‘011’ menggunakan Huffman tree

Setelah ditelusuri dari akar, maka kita akan menemukan bahwa string yang

mempunyai kode Huffman 011” adalah karakter D.

Cara yang kedua adalah dengan menggunakan tabel kode Huffman.

Sebagai contoh kita akan menggunakan kode Huffman pada Tabel 2.2 untuk

merepresentasikan string “ABCDACA”. Dengan menggunakan Tabel 2.2 string

tersebut akan direpresentasikan menjadi rangkaian bit : 1 010 01 011 1 011 . Jadi,

jumlah bit yang dibutuhkan hanya 13 bit. Dari Tabel 2.2 tampak bahwa kode

untuk sebuah simbol/karakter tidak boleh menjadi awalan dari kode simbol yang

lain guna menghindari keraguan (ambiguitas) dalam proses dekompresi atau

decoding. Karena tiap kode Huffman yang dihasilkan unik, maka proses decoding

dapat dilakukan dengan mudah.

Contoh: saat membaca kode bit pertama dalam rangkaian bit

“1010010111011 ”, yaitu bit “1”, dapat langsung dinodekan bahwa kode bit “1”

merupakan pemetaan dari simbol “A”. Kemudian baca kode bit selanjutnya, yaitu

bit “0”. Tidak ada kode Huffman “0”, lalu baca kode bit selanjutnya, sehingga

menjadi “01”. Tidak ada juga kode Huffman “01”, lalu baca lagi kode bit

berikutnya, sehingga menjadi “010”. Rangkaian kode bit “010” adalah pemetaan

dari simbol “B”, dan Seterusnya hingga bitstream sudah terbaca semua.



2.6 Adaptive Huffman Code

Pengembangan dari Huffman Code adalah Adaptive Huffman Code.

Adaptive Huffman Code pertama kali ditemukan oleh Faller dan Gallager,

selanjutnya dikembangkan oleh Knuth. Versi terakhir dari Adaptive Huffman

Code diuraikan oleh Jeffrey Scott Vitter. Berbeda dengan Huffman Code yang

membutuhkan dua fase, Adaptive Huffman Code hanya membutuhkan satu fase

dalam kompresi data, dimana proses penghitungan frekuensi karakter dan

pembuatan pohon Huffman identik di encoder dan decoder dilakukan secara

adaptif pada saat membaca data.

Pada Huffman code, statistik-statistik pada kompresi data biasanya dibawa

bersama data yang sudah dikodekan untuk dipakai oleh pendekompres data. Cara

ini mempunyai masalah jika statistik-statistik untuk model tersebut

mengkonsumsi lebih banyak ruang dari data terkompresi sendiri.

Kompresi data adaptif adalah solusi untuk masalah ini. Dalam metode

Kompresi data adaptif, pengkompresi dan pendekompresi memulai proses dengan

fixcode yang sama. Dalam pembuatan model fixcode, variabel yang digunakan

adalah e dan r. Kedua variabel tersebut diperoleh dari m = 2e + r. dimana m

adalah jumlah karakter dalam fixcode yang digunakan. Dengan aturan sebagai

berikut:

Untuk urutan karakter ke 1 sampai 2r, karakter direpresentasikan

sebanyak e +1 bit dari nilai urutan karakter - 1.

Untuk urutan karakter ke 2r + 1 sampai akhir, karakter

direpresentasikan sebanyak e bit dari nilai urutan karakter - r - 1.

Pengkompresi mengkodekan sebuah simbol dengan menggunakan model

yang ada, lalu meng-update model tersebut untuk memproses simbol berikutnya.

Pendekompresi melakukan cara yang sama. Sepanjang algoritma, pohon Huffman

terbentuk identik untuk kompresi dan dekompresi, proses dapat berjalan tanpa

perlu mengirimkan statistik-statistik dari kompresi ke dekompresi. Setiap kali

simbol dibaca, maka simbol tersebut langsung dikodekan. Untuk satu simbol yang

sama, kemungkinan hasil pengkodeannya berbeda, hal ini disebabkan karena

setiap kali membaca simbol dilakukan penyesuaian pohon.[3]



2.6.1 Pembentukan Huffman Tree

Prinsip dari pohon Huffman Adaptive Huffman Code, yaitu :

1. Setiap node, kecuali akar memiliki saudara kandung

2. Untuk setiap node di dalam pohon, bobot node akar ≥ bobot node

kanan ≥ bobot node kiri

3. Node kanan diberi suksesor bit ‘1’ dan node kiri diberi suksesor bit ‘0’

4. Urutan setiap simbol berbanding lurus terhadap bobot simbol tersebut,

semakin besar urutan maka akan semakin besar frekuensi simbol di

dalam data yang sudah dibaca, demikian juga sebaliknya

5. Node-node yang semakin dekat dengan akar memiliki bobot yang

semakin besar

6. Node dalam adalah orang tua dari node luar (node kanan dan node kiri)

7. Bobot node dalam adalah jumlah bobot node luarnya

8. Node-node yang memiliki bobot sama disimpan dalam sebuah blok

Blok adalah list terurut dari node-node yang memiliki bobot sama. Blok

diurutkan mengecil berdasar angka urut yang dimiliki node-node tersebut, node

yang pertama adalah node dengan angka urut terbesar.

Setiap node yang terdapat di dalam pohon Huffman ini juga menyimpan

sebuah informasi tambahan, yaitu angka urut. Angka urut adalah angka unik yang

dimiliki oleh setiap node di dalam pohon, dalam arti tidak lebih dari satu node

yang memiliki angka urut tersebut. Node-node dengan ketinggian yang sama akan

memiliki angka urut terurut membesar dari kiri ke kanan. Angka urut diberikan

kepada node ketika node tersebut pertama kali dibuat. Angka urut yang diberikan

adalah angka urut terbesar yang belum digunakan oleh node-node yang lain.

Angka urut terbesar ini didapatkan dari nilai maksimum kemungkinan jumlah

node terbanyak. Perhitungannya adalah 2 kali jumlah fixcode dikurang 1.

Pohon Huffman ini juga memiliki sebuah node khusus,yang disebut node

NYT (Not Yet Transmitted). Ketika sebuah simbol yang belum terdapat di dalam

pohon Huffman dikirimkan/dibaca, node NYT akan membentuk dua buah anak,

anak kanan menyimpan informasi simbol baru tersebut, dan anak kiri menjadi

node NYT yang baru. Anak kanan mempunyai angka urut lebih besar daripada

anak kiri. Misal, jika angka urut terbesar yang belum digunakan adalah x, maka



anak kanan mempunyai angka urut x, sedangkan anak kiri mempunyai angka urut

(x-1). Pohon Huffman yang pertama kali terbentuk hanya memiliki sebuah node,

yaitu node NYT.

Seperti dijelaskan diatas, bahwa bobot akar ≥ bobot node kanan ≥ bobot

node kiri, oleh karena itu, setiap node akan mengalami pertukaran posisi sesuai

dengan nilai bobotnya. Ada beberapa hal yang perlu diperhatikan dalam menukar

posisi node, antara lain :

1. Node akar dari pohon tidak boleh ditukar posisinya dengan apapun

2. Tidak diperbolehkan untuk menukar posisi suatu node dengan node

orang tuanya atau leluhurnya

3. Angka urut dari dua buah simpul yang ditukar posisinya haruslah

ditukar juga

4. Jika Node dalam melakukan pertukaran, node luarnnya mengikuti.

5. Node dalam dan node luar untuk simbol baru yang memiliki saudara

kandung node NYT tidak melakukan pertukaran, pertukaran dimulai

dari orangtua node NYT sebelumnya.

Gambar 2.8 merupakan diagram alir proses pembentukan pohon Huffman

pada Adaptive Huffman Code.

Gambar 2.8 Diagram alir pembentukan Huffman tree pada Adaptive Huffman Code



Misal, dalam pengkodean deretan huruf hal pertama yang dilakukan

adalah mendapatkan nilai maksimum kemungkinan jumlah node terbanyak dan

pembentukan fixcode . Jika jumlah simbol yang dibuat dalam fixcode adalah

deretan alfabet kapital (26 huruf), maka kemungkinan jumlah node maksimum

adalah sebanyak 51 node (26 x 2 -1).

Untuk model awal itu sendiri m = 26, sehingga e = 4 dan r 10. Oleh karena

itu untuk simbol ke 1 sampai 20 (2r), maka modelnya adalah biner 0 sampai 19 (k

-1) sebanyak 5 bit (e + 1). Dan simbol ke 21(2r+1) sampai 26, maka modelnya

adalah biner 9 sampai 14(k-r-1) sebanyak 4 bit (e). Tabel 2.3 merupakan fixcode

alfabet kapital :

Tabel 2.3 Fixcode adaptive Huffman code alfabet kapital

Simbol Urutan Kode A 1 00000 B 2 00001 C 3 00010 D 4 00011 E 5 00100 F 6 00101 G 7 00110 H 8 00111 I 9 01000 J 10 01001 K 11 01010 L 12 01011 M 13 01100 N 14 01101 O 15 01110 P 16 01111 Q 17 10000 R 18 10001 S 19 10010 T 20 10011 U 21 1001 V 22 1010 W 23 1011 X 24 1100 Y 25 1101 Z 26 1110


Muhammad Abdul Jabbar Hussein (091344018)

Gambar 2.9(1-8) Proses pembentukan adaptive Huffman tree karakter ‘ABCDACA’

(1) (2) (3) (4)

(5) (6)

(7)

(8)

= Tukar



Gambar 2.9(1-8) adalah contoh urutan pembentukan pohon Huffman yang

selalu beradaptasi setiap suatu simbol muncul untuk karakter ‘ABCDACA’.

2.6.2 Proses Encoding Adaptive Huffman Code

Pada proses pengkodean, setiap simbol yang muncul pertama kali, dan

belum ada dalam pohon Huffman, selalu dikodekan bedasarkan model yang ada

dalam fixcode diikuti dengan kode NYT. Selanjutnya memanggil update

procedure yang berfungsi untuk pembaharuan pohon Huffman. Bila simbol yang

muncul sudah ada dalam pohon Huffman, maka simbol tersebut dikodekan sesuai

urutan bit suksesor yang ada dalam cabang dari node akar hingga node simbol

yang bersangkutan kemudian panggil update procedure. Gambar 2.10 merupakan

diagram alir proses pengkodean Adaptive Huffman Code.

Gambar 2.10 Diagram alir encoder pada Adaptive Huffman Code



Seperti dijelaskan sebelumnya, bahwa untuk setiap simbol baru yang

pertama kali muncul akan dikodekan sesuai model yang ada pada fixcode diikuti

dengan kode NYT. NYT dan simbol yang sudah pernah muncul dikodekan sesuai

urutan bit suksesor dari cabang node akar hingga node yang bersangkutan.

Gambar 2.11 adalah hasil pengkodean untuk karakter ‘ABCDACA’.

00000 0 00001 00 00010 100 00011 10 01 11

Gambar 2.11 Bitstream hasil pengkodean ‘ABCDACA’

Dari proses pengkodean diatas, jumlah bit yang didapat hanya 32 bit.

Dalam kode ASCII yang 1 simbolnya dikodekan 8 bit berarti karakter

‘ABCDACA’ dikodekan sebanyak 56 bit (7 x 8 bit). Maka hasil dari pengkodean

adaptive Huffman code mengalami pemampatan data.

2.6.3 Proses Decoding Adaptive Huffman Code

Deretan bit hasil pengkodean bagian encoder akan dikembalikan pada

data semula oleh bagian decoder. Caranya adalah dengan pengecekan keberadaan

simbol untuk deretan bit pada pohon Huffman di bagian ini. Jika belum ada ,

pembacaan bit dimulai dari node NYT. Jika node yang ditemui adalah node NYT,

maka lakukan pengecekan lagi untuk nilai desimal bit sebanyak e. Misal nilai

desimal bit sebanyak e adalah p, periksa apakah nilai p kurang dari r, jika iya

baca 1 bit selanjutnya dan ubah bit-bit tersebut menjadi simbol sesuai fixcode

yang ada kemudian update pohon Huffman. Jika tidak itu maka tambahkan nilai r

dan p dan ubah bit-bit tersebut menjadi simbol sesuai fixcode yang ada. Bila node

yang ditemui merupakan node yang memiliki simbol yang sudah muncul

sebelumnya, maka ubah bit tersebut sesuai simbol yang terdapat pada node

tersebut kemudian update pohon Huffman.

C A B D

NYT

A C A

NYT NYT



Cara menentukan apakah bit yang ditemui itu node NYT atau node yang

memiliki simbol, yaitu dengan pembacaan bit suksesor dari node akar hingga

node yang bersangkutan. Gambar 2.12 merupakan diagram alir proses

pendekodean Adaptive Huffman Code.

Pada deretan bit 00000000001000001010000011100111 hasil pengkodean

‘ABCDACA’, Node pertama pada pohon Huffman tidak memiliki bit suksesor,

maka bit tersebut langsung melakukan pengecekan nilai p, ternyata p kurang dari r

(0 < 10), ubah bit 00000 sesuai fixcode yaitu ‘A’. selanjutnya update pohon

Huffman. Bit selanjutnya merupakan suksesor node NYT kiri, maka baca e bit

setelah bit tersebut dan ubah sesuai fixcode. Begitu seterusnya untuk simbol B,C

dan D. jika pembacaan bit suksesor mengarah pada node yang sudah ada

simbolnya maka ubah bit-bit suksesor tersebut sesuai simbol yang ada pada node

tersebut, contoh bit ‘10’ langsung diubah menjadi ‘A’. Begitu juga bit ‘01’ untuk

simbol C dan bit ‘11’ untuk ‘A’.

Gambar 2.12 Diagram alir decoder pada Adaptive Huffman Code

bab ii.pdf

Documents