BAB 2
LANDASAN TEORI
2.1 Pengertian File Teks
File teks merupakan file yang berisi informasi-informasi dalam bentuk teks. Data yang berasal dari dokumen pengolah kata, angka yang digunakan dalam perhitungan, nama dan alamat dalam basis data merupakan contoh masukan data teks yang terdiri dari karakter, angka dan tanda baca.
Masukan dan keluaran data teks direpresentasikan sebagai set karakter atau sistem kode yang dikenal oleh sistem komputer. Ada tiga macam set karakter yang umum digunakan untuk masukan dan keluaran pada komputer, yaitu ASCII, EBCDIC, dan Unicode. ASCII (American Code for Information Interchange) merupakan suatu standar internasional dalam kode huruf dan simbol seperti Hex dan Unicode tetapi ASCII lebih bersifat universal. ASCII digunakan oleh komputer dan alat komunikasi lain untuk menunjukkan teks. Kode ASCII memiliki komposisi bilangan biner sebanyak 8 bit, dimulai dari 00000000 hingga 11111111. Total kombinasi yang dihasilkan sebanyak 256, dimulai dari kode 0 hingga 255 dalam sistem bilangan desimal. EBCDIC (Extended Binary Codec Decimal Interchange Code) merupakan set karakter yang diciptakan oleh komputer merk IBM. EBCDIC terdiri dari 256 karakter yang masing-masing berukuran 8 bit. Adanya keterbatasan pada kode ASCII dan EBCDIC, dibuat standar kode internasional baru yang merupakan kode 16 bit yang disebut Unicode. Unicode adalah suatu standar industri yang dirancang untuk
mengizinkan teks dan simbol dari semua sistem tulisan di dunia untuk ditampilkan dan dimanipulasi secara konsisten oleh komputer (Sudewa, Ida Bagus Adi, 2003).
Gambar 2.1 Karakter ASCII
2.1.1 Format Teks
Secara umum, format data teks dibagi menjadi dua bagian, yaitu (Purnomo, Herry et al, 2005, hal: 410):
1. Teks sederhana (plain text) Format data teks (*.txt) merupakan contoh format teks jenis ini yang paling populer.
2. Teks terformat (formatted text) Merupakan teks yang terformat dan mengandung styles. Format data dokumen Microsoft Word (*.doc) merupakan contoh format teks jenis ini yang paling populer.
Contoh format data teks di atas beserta perangkat lunak yang biasa digunakan di antaranya adalah (Purnomo, Herry et al, 2005, hal: 410):
1. Format data teks (*.txt) Format data teks merupakan format teks yang digunakan untuk menyimpan huruf, angka, karakter kontrol (tabulasi, pindah baris, dan sebagainya) atau simbol-simbol lain yang biasa digunakan dalam tulisan seperti titik, koma, tanda petik, dan sebagainya. Satu huruf, angka, karakter kontrol atau simbol pada arsip teks memakan tempat satu byte. Berbeda dengan jenis teks terformat yang satu huruf saja dapat memakan tempat beberapa byte untuk menyimpan format dari huruf tersebut seperti font, ukuran, tebal atau tidak dan sebagainya. Kelebihan dari format data teks ini adalah ukuran datanya yang kecil karena tiadanya fitur untuk memformat tampilan teks. Saat ini perangkat lunak yang paling banyak digunakan untuk memanipulasi format data ini adalah Notepad.
2. Format data dokumen (*.doc) Doc merupakan ekstensi arsip dokumen perangkat lunak Microsoft Word yang paling banyak digunakan dalam menulis laporan, makalah dan sebagainya. Doc merupakan jenis teks terformat yang tidak hanya dapat mengatur tampilan teks seperti styles (font, ukuran huruf, dan sebagainya), namun juga dapat menyisipkan gambar. Kekurangan format teks dokumen ini terletak pada ukuran datanya yang besar.
3. Hyper Text Markup Language (*.htm atau *.html) Merupakan format teks standard untuk tampilan dokumen web.
4. Rich Text Format (*.rtf) Format teks ini dikembangkan oleh Microsoft yang dapat dibaca oleh berbagai macam platform, seperti Windows, Linux, Mac OS dan sebagainya.
2.1.2 Tipe Teks
Tipe teks merupakan tipe dasar yang sudah sangat dikenal dalam kehidupan seharihari. Tipe teks terdiri dari tipe karakter (char) dan tipe string. Tipe karakter (char) terdiri atas satu huruf, angka, tanda baca, atau karakter khusus seperti ”a”, ”1”, ”*” dan sebagainya. Tipe string terdiri atas nol atau lebih karakter seperti ”algoritma”, ”teks” dan sebagainya (Purnomo, Herry et al, 2005, hal: 99).
2.2 Pohon (Tree)
Pohon (tree) membentuk salah satu subklas dari graf yang paling banyak digunakan. Dalam ilmu komputer, pohon berguna dalam mengatur dan mengaitkan data dalam suatu basis data.
Definisi 2.1 Sebuah pohon T (tree T) adalah sebuah graf sederhana yang memenuhi: jika v dan w adalah verteks atau node di T, maka terdapat sebuah lintasan sederhana tunggal dari v ke w (Johnsonbaugh, Richard, 1998, hal: 75).
Definisi 2.2 Sebuah pohon berakar adalah pohon di mana sebuah node tertentu dirancang seperti akar (Johnsonbaugh, Richard, 1998, hal: 75).
v1
v3
v2
v4
v5
v6
v7
Gambar 2.2 Pohon Berakar dengan v1 Sebagai Akar. Pohon secara luas digunakan dalam struktur data ilmu komputer seperti pohon pencarian biner, pohon perentang, tumpukan dan lain lain.
2.3 Pohon Biner (Binary Tree)
Definisi 2.3 Pohon biner (binary tree) adalah pohon berakar yang setiap nodenya mempunyai paling banyak dua anak dan masing-masing anak dari sebuah node disebut sebagai anak kiri (left child) dan anak kanan (right child) (Jong, Jek Siang, 2002, hal: 283 ).
Definisi 2.4 Pohon biner penuh (full binary tree) adalah pohon biner yang setiap nodenya (kecuali daun) mempunyai tepat dua anak (Jong, Jek Siang, 2002, hal: 283 ).
Pohon biner dapat digunakan untuk menyatakan ekspresi aljabar maupun pencarian dan pengurutan data.
Definisi 2.5 Misalkan T adalah pohon biner dan v ∈ V(T) adalah suatu titik cabang dalam T. Subpohon kiri (left subtree) v adalah pohon biner yang:
1. Titik-titiknya adalah anak kiri v dan semua turunannya. 2. Garis-garisnya adalah garis-garis dalam E(T) yang menghubungkan titik-titik subpohon kiri v. 3. Anaknya adalah anak kiri v. (Jong, Jek Siang, 2002, hal: 284). v w
x
Gambar 2.3. Pohon Biner
Gambar di atas merupakan pohon biner dengan dua subpohon, yaitu subpohon kiri v dengan w sebagai akar dan subpohon kanan v dengan x sebagai akar.
2.4 Pemampatan Data
Salah satu ide yang populer dalam pemampatan data adalah apabila frekuensi kemunculan karakter atau simbol pada suatu pesan diketahui, maka terdapat cara untuk mengkodekan karakter, sehingga membutuhkan ruang yang lebih kecil. Ide ini tidaklah baru, suatu contoh awal pemampatan data adalah kode Morse yang dikembangkan oleh Samuel Morse pada pertengahan abad ke 19. Huruf-huruf yang
dikirim oleh telegraf disandikan dengan titik dan garis. Morse mencatat bahwa huruf tertentu terjadi lebih sering dibanding yang lain. Untuk mengurangi rata-rata waktu yang diperlukan dalam mengirimkan pesan, Morse membuat urutan yang lebih pendek untuk huruf-huruf yang terjadi lebih sering seperti e (.), a (.-) dan urutan yang lebih panjang untuk huruf-huruf yang terjadi agak jarang seperti q (--.-) dan j(.---).
Ide penggunaan kode yang lebih pendek untuk karakter yang lebih sering terjadi dan kode yang lebih panjang untuk karakter yang jarang terjadi diambil ke dalam bidang komputasi oleh Claude Elwood Shannon dan Robert M. Fano tahun 1950an, ketika ke duanya mengembangkan algoritma pemampatan Shannon-Fano. Beberapa tahun kemudian, David A. Huffman menerbitkan suatu paper tahun 1952 yang meningkatkan kinerja algoritma dengan menamainya Huffman coding.
Saat ini terdapat berbagai tipe algoritma pemampatan antara lain Huffman, LIFO, LZ77, Dynamic Markov Compression, Block Sorting Lossless, Run Length, Shannon-Fano, Arithmetic dan lain-lain.
2.4.1 Pengertian Pemampatan Data
Pemampatan data adalah proses pengubahan sekumpulan data menjadi suatu bentuk kode untuk menghemat kebutuhan ruang penyimpanan dan waktu untuk transmisi data (Linawati et al, 2004, hal:7). Pemampatan merupakan salah satu teori informasi yang diperkenalkan oleh Shannon yang bertujuan untuk menghilangkan redundasi dari sumber. Pemampatan bermanfaat dalam membantu mengurangi konsumsi sumber daya yang mahal, seperti ruang hard disk atau perpindahan data melalui internet.
Pemampatan data memiliki beberapa aplikasi, diantaranya (Munir, Rinaldi, 2004, hal: 166):
1. Pengiriman data (data transmission) pada saluran komunikasi data Data yang telah dimampatkan membutuhkan waktu yang lebih singkat dibandingkan dengan data yang tidak dimampatkan. 2. Penyimpanan data (data storing) di dalam media sekunder (storage) Data yang telah dimampatkan membutuhkan ruang pada media penyimpanan yang lebih sedikit dibandingkan dengan data yang tidak dimampatkan.
2.4.2 Metode Pemampatan
Metode pemampatan diklasifikasikan ke dalam dua metode, yaitu (Munir, Rinaldi, 2004, hal: 169):
1. Metode Lossless Merupakan teknik pemampatan yang menghasilkan hasil penirmampatan tepat sama seperti data semula. Tidak ada informasi yang hilang akibat pemampatan. Tetapi rasio pemampatannya sangat rendah. Misalnya pada data teks, gambar seperti GIF dan PNG. Contoh metode ini adalah Shannon-Fano coding, Huffman coding, Arithmetic coding dan lain sebagainya.
2. Metode Lossy Merupakan teknik pemampatan yang menghasilkan hasil penirmampatan hampir sama dengan data semula. Ada informasi yang hilang akibat pemampatan, tetapi dapat ditolerir oleh persepsi mata. Misalnya pada gambar
dan MP3. Kelebihan teknik ini adalah rasio pemampatan yang tinggi dibanding metode lossless.
Efek pemampatan pada metode pemampatan lossless dapat diukur melalui sejumlah penyusutan suatu file asal dalam membandingkan ukuran dari jenis-jenis pemampatan, yaitu:
1. Rasio pemampatan, merupakan perbandingan ukuran file setelah pemampatan dengan file semula yang ditunjukkan dalam persentase (ditulis dalam %): ukuran file hasil pemampa tan * 100% Rasio Pemampatan = ukuran file semula
(2.1)
2. Kecepatan proses pemampatan (ditulis dalam satuan KByte/s): Kecepatan Proses Pemampatan =
ukuran file semula waktu komputasi yang dibutuhkan
(2.2)
Ada beberapa kriteria yang sering menjadi pertimbangan dalam memilih suatu metode pemampatan yang tepat diantaranya kecepatan pemampatan, sumber daya yang dibutuhkan, kualitas, ukuran file, kompleksitas algoritma dan lain-lain (Munir, Rinaldi, 2004, hal: 166). Kualitas pemampatan dengan kebutuhan memori biasanya berbanding terbalik. Kualitas pemampatan yang bagus umumnya dicapai pada proses pemampatan yang menghasilkan pengurangan memori yang tidak begitu besar dan begitu juga sebaliknya.
2.5 Algoritma Huffman
Algoritma Huffman diperkenalkan oleh David A. Huffman seorang mahasiswa MIT dalam papernya yang berjudul "A Method for the Construction of MinimumRedundancy Codes" dan diterbitkan pada tahun 1952. Prinsip kode Huffman adalah karakter yang paling sering muncul di dalam data dikodekan dengan kode yang jumlah bitnya lebih sedikit, sedangkan karakter yang jarang muncul dikodekan dengan kode yang jumlah bitnya lebih panjang. Algoritma Huffman menggunakan tabel frekuensi kemunculan karakter untuk menggambarkan setiap karakter menjadi kode atau string biner. Kode atau string biner yang digunakan untuk mengkodekan setiap karakter dinamakan kode Huffman.
Algoritma Huffman yang akan dibahas dalam tulisan ini adalah algoritma Huffman yang menggunakan metode statik, yaitu metode yang menggunakan peta kode yang sama, metode ini membutuhkan dua fase, yaitu fase pertama untuk menghitung frekuensi kemunculan tiap karakter dan menentukan peta kodenya dan fase ke dua untuk mengubah pesan atau data menjadi kumpulan kode yang akan ditransmisikan.
Kode optimal untuk sebuah file digambarkan dengan pohon biner penuh, di mana setiap node bukan daun mempunyai dua anak. Pada awalnya Huffman hanya mengkodekan karakter menggunakan pohon biner biasa, namun setelah itu Huffman menemukan bahwa penggunaan algoritma Greedy dapat membentuk kode prefiks yang optimal. Penggunaan algoritma Greedy pada algoritma Huffman adalah pada saat pemilihan dua pohon dengan frekuensi terkecil dalam membuat pohon Huffman. Algoritma
Greedy
digunakan
meminimumkan total cost
pada
pembentukan
yang dibutuhkan. Cost
pohon
Huffman
agar
yang digunakan untuk
menggabungkan dua buah pohon pada akar setara dengan jumlah frekuensi dua buah pohon yang digabungkan. Oleh karena itu, total cost pembentukan pohon Huffman adalah jumlah seluruh penggabungan daun-daun.
Algoritma Huffman menggunakan struktur data string sebagai masukan, struktur data binary tree pada pembentukan pohon biner dan array untuk mendeklarasikan kumpulan variabel yang bertipe sama.
2.5.1 Kode Prefix (Prefix Code)
Kode prefix (prefix code) membentuk kode Huffman yang optimal, maksudnya adalah tidak ada kode suatu karakter yang merupakan awalan bagi kode karakter yang lain karena semua karakter berada di daun pohon. Dengan begitu tidak ada ambiguitas pada proses penirmampatan data. Kode prefix direpresentasikan sebagai pohon biner berlabel yang dalam hal ini setiap sisi pada pohon biner diberi label 0 untuk subpohon kiri dan diberi label 1 untuk subpohon kanan.
2.5.2 Algoritma Huffman
Huffman memberikan sebuah algoritma untuk membangun sebuah kode Huffman dengan masukan string teks S={s1,s2,…,sn} dan frekuensi kemunculan karakter F={f1, f2 ,…, fn}, dihasilkan keluaran berupa kode string biner C={c1,c2,…,cn} atau disebut kode Huffman. Algoritma Pemampatan Huffman:
Masukan: daftar karakter-karakter yang telah diurutkan {s1,s2,…,sn} dan frekuensinya {f1, f2 ,…, fn} Keluaran: kode Huffman dengan n kode
1. Urutkan karakter berdasarkan frekuensi kemunculan karakter. 2. Setiap karakter dinyatakan sebagai daun atau pohon bersimpul tunggal. 3. Gabungkan dua daun pohon yang mempunyai frekuensi kemunculan karakter paling kecil pada sebuah akar. 4. Ulangi langkah tiga hingga tersisa satu buah pohon biner 5. Beri label pada setiap sisi pohon biner. Sisi kiri dilabeli dengan 0 dan sisi kanan dilabeli dengan 1. 6. Telusuri pohon biner dari akar ke daun. Barisan label-label pada sisi pohon dari akar ke daun menyatakan kode Huffman untuk karakter yang bersesuaian
Tabel karakter-karakter yang diurutkan berdasarkan frekuensi kemunculan karakter tersebut berhubungan dengan distribusi probabilitas atau distribusi peluang. Distribusi probabilitas ini berhubungan pada kemungkinan penempatan akar atau subpohon baru yang telah terbentuk. Probabilitas untuk masing-masing karakter adalah frekuensi karakter tersebut dibagi jumlah frekuensi keseluruhan.
Untuk proses penirmampatan (decompression) atau menyusun kembali data dari kode biner menjadi sebuah string asli dapat digunakan tabel kode Huffman yang telah terbentuk. Selain menggunakan tabel, cara lainnya adalah menggunakan algoritma penirmampatan.
Algoritma Penirmampatan:
1. Baca sebuah bit dari rangkaian kode biner. 2. Mulai dari akar pohon biner. 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 hingga tidak ada lagi bit dalam rangkaian kode biner.
Contoh 2.1 Diberikan string ”fungsi rekursif” sebagai masukan pada pemampatan file teks. Masukan ini terdiri dari karakter-karakter abjad S={f,u,n,g,s,i,r,e,k,spasi} dengan frekuensi kemunculan karakter F={2,2,1,1,2,2,2,1,1,1}. Apabila string tersebut menggunakan kode ASCII untuk mengkodekan setiap karakter, maka representasi 15 karakter membutuhkan 15 × 8 = 120 bit atau 15 bytes. Untuk meminimumkan jumlah bit yang dibutuhkan, panjang kode untuk setiap karakter sedapat mungkin diperpendek, terutama untuk setiap karakter yang frekuensi kemunculannya besar. Jadi, bagaimana memperoleh jumlah minimum bit apabila digunakan algoritma Huffman untuk menghasilkan kode yang merepresentasikan setiap karakter.
Dengan menggunakan algoritma Huffman untuk mengkodekan setiap karakter dapat diperoleh kode Huffman sebagai berikut:
Masukan: 15 karakter yang telah diurutkan dan tabel frekuensi Keluaran: Kode Huffman
1. Pengurutan karakter berdasarkan frekuensi kemunculannya. Karakter pada data diurutkan di dalam tabel secara menaik (asscending order). Tabel 2.1 Frekuensi Kemunculan Karakter yang telah Diurutkan Karakter spasi e g k n f i r s u Jumlah
Frekuensi 1 1 1 1 1 2 2 2 2 2 15
2. Pembentukan pohon Huffman Setiap karakter digambarkan sebagai daun. Gabungkan dua daun yang mempunyai frekuensi kemunculan karakter paling kecil untuk membentuk sebuah akar kemudian akar diurutkan kembali. Akar merupakan jumlah frekuensi dua daun atau subpohon penyusunnya. Iterasi ini dilakukan hingga terbentuk satu buah pohon biner. Beri label 0 dan 1 pada setiap sisi pohon biner. Sisi kiri dilabeli dengan 0 dan sisi kanan dilabeli dengan 1.
Pengurutan kembali akar yang baru terbentuk berhubungan dengan distribusi probabilitas. Pada contoh ini, ada lebih dari satu kemungkinan tempat yang tersedia pada penggabungan karakter ”spasi” dan ”e” dengan frekuensi 2. Untuk mencegah penggabungan akar baru terlalu cepat maka akar ditempatkan pada posisi terendah. Jadi, akar baru ”spasi” dan ”e” ditempatkan sesudah karakter ”u”. Pembentukan pohon biner dari string ”fungsi rekursif” adalah:
1.
k:1
g:1
f:2
n:1
i:2
r:2
s:2
2
u:2
spasi:1 2. f:2
n:1
i:2
r:2
s:2
2
2
u:2
g:1
3.
g:1
5.
k:1
6.
e:1
n:1
4
3
n:1
f:2
n:1
g:1
r:2
4
2
r:2
2
k:1
spasi:1
3
2
k:1
i:2
u:2
e:1
7
2
r:2
r:2
i:2
4
4
4
i:2
f:2
s:2
g:1 7.
f:2
4
f:2
i:2
n:1 4
4
u:2
s:2
e:1
3
spasi:1
e:1
3
spasi:1
2
3
spasi:1
2
k:1
2
g:1
k:1
2
u:2
s:2
e:1
spasi:1
2
g:1 4.
k:1
2
u:2
s:2
r:2
i:2
e:1
spasi:1
n:1
e:1
4
f:2
s:2
u:2
8. 8
7 3
n:1
4
f:2
s:2
4
4
u:2
i:2
2
r:2
g:1 15
9.
7
8
2
k:1
spasi:1
e:1
15
9.
8
7 3
4
f:2
n:1
s:2
4
4
u:2
i:2
2
2
r:2
e:1
spasi:1
k:1
g:1 15 0
8
7
0
1
n:1
0
1 f:2
0 s:2
1 4
4
4
3 0
1
1 u:2
0 i:2
0
1
1
2
r:2 0 g:1
2 1 k:1
0
1
spasi:1
e:1
Gambar 2.4 Pembentukan Pohon Huffman Keterangan gambar: : akar yang dibentuk dari dua daun atau subpohon penyusunnya : daun yang terdiri dari karakter dan frekuensinya
3. Kode Huffman yang diperoleh dari pohon Huffman yang telah terbentuk adalah: Tabel 2.2 Tabel Kode Huffman untuk Masing-masing Karakter Karakter Spasi E G K n f i r s u
Frekuensi (f) 1 1 1 1 1 2 2 2 2 2
Kode Huffman 1110 1111 1100 1101 000 001 100 101 010 011
Panjang kode (shf) 4 4 4 4 3 3 3 3 3 3
Total panjang (fxshf) 4 4 4 4 3 6 6 6 6 6
Total 15 34 49 Dengan demikian, jumlah bilangan bit yang dibutuhkan oleh algoritma Huffman untuk merepresentasikan string ”fungsi rekursif” adalah 49 bit. String tersebut dimampatkan dengan rasio sebesar:
u k u r afni l eh a s ipl e m a m tpaan * 1 0 0% Rasio Pemampatanan= u k u r a f n i l e s e m u l a 4 9 m=n p a * 1 0%0 1 2 0
= 40,8% Dengan demikian string ”fungsi rekursif” dimampatkan menjadi rangkaian bit: 0010110001100010100111010111111101011101010100001 Untuk proses penirmampatan (decompression) atau menyusun kembali data dari kode biner menjadi sebuah string asli dapat digunakan tabel kode Huffman yang telah terbentuk
atau
menggunakan algoritma penirmampatan.
Pada
proses
penirmampatan, rangkaian bit biner 0010110001100010100111010111111101011101010100001 dimulai dengan membaca bit pertama yaitu ”0”, tidak terdapat bit ”0” pada tabel kode Huffman. Lalu baca bit berikutnya, sehingga menjadi ”00”, tidak terdapat juga bit ”00”, kemudian baca lagi bit berikutnya, sehingga menjadi ”001”. Rangkaian bit ”001” ini ditemukan pada tabel kode Huffman yaitu bit yang merepresentasikan karakater ”f”. Proses ini terus dilakukan hingga tidak terdapat lagi bit biner.
2.6 Algoritma Shannon-Fano
Shannon-Fano coding merupakan algoritma pertama yang diperkenalkan
untuk
pemampatan sinyal digital pada papernya yang berjudul “A Mathematical Theory of Communication” pada tahun 1948. Shannon dan Fano terus menerus mengembangkan algoritma ini yang menghasilkan kode biner (binary codeword) untuk setiap karakter yang terdapat pada data dengan redundansi minimum.
Algoritma Shannon-Fano didasarkan pada variable–length code yang berarti beberapa karakter pada data yang akan dikodekan direpresentasikan dengan kode (codeword) yang lebih pendek dari karakter yang ada pada data. Jika frekuensi kemunculan karakter semakin tinggi, maka kode semakin pendek. Dengan demikian kode yang dihasilkan tidak sama panjang, sehingga kode tersebut bersifat unik.
Algoritma Shannon-Fano menggunakan struktur data yang sama dengan algoritma Huffman, yaitu struktur data string sebagai data masukan, struktur data binary tree sebagai pembentukan pohon biner dan array sebagai pendeklarasian variabel yang sama.
2.6.1 Algoritma Shannon-Fano
Untuk memperoleh kode Shannon-Fano dengan masukan string teks S={s1,s2,…,sn} dan frekuensi kemunculan karakter F={f1, f2 ,…, fn}, dihasilkan keluaran berupa string biner C={c1,c2,…,cn} atau kode Shannon-Fano. Algoritma pemampatan Shannon-Fano: Masukan: daftar karakter-karakter yang telah diurutkan {s1,s2,…,sn} dan frekuensinya {f1, f2 ,…, fn}
Keluaran: kode Shannon-Fano dengan n kode
1. Urutkan karakter berdasarkan frekuensi dengan kemunculan karakter secara menurun (descending order). 2. Bagi urutan karakter di dalam tabel frekuensi ke dalam dua subbagian dengan jumlah frekuensi keduanya mendekati atau hampir sama. 3. Berikan label 0 pada subpohon kiri dan label 1 pada subpohon kanan. 4. Ulangi pembagian pada langkah tiga dan empat pada ke dua bagian secara rekursif hingga masing-masing karakter menjadi daun kode yang bersesuaian.
Rekursif dan iterasi merupakan prosedur perulangan dalam menyelesaikan permasalahan pemrograman. Prosedur rekursif merupakan suatu proses yang berulang yang dilaksanakan dengan cara memanggil prosedur atau fungsi yang sama yaitu dirinya sendiri. Sedangkan iterasi merupakan suatu proses perulangan yang dilaksanakan oleh suatu prosedur atau fungsi atau sub program dengan cara memasukkan secara langsung nilai-nilai argumennya. Dalam proses iterasi, proses perulangan dikendalikan oleh suatu pencacah (counter) yang akan selalu berubah setiap kali dilakukan proses perulangan (Purnomo, Herry et al, 2005, hal: 99).
Contoh 2.2 Untuk membandingkan hasil yang diperoleh dengan algoritma Huffman, digunakan string masukan yang sama untuk memperoleh jumlah minimum bit apabila digunakan
algoritma
Shannon-Fano
untuk
menghasilkan
kode
yang
merepresentasikan setiap karakter.
1. Pengurutan karakter berdasarkan frekuensi kemunculannya secara menurun (descending order).
Tabel 2.3 Frekuensi Kemunculan Karakter yang telah Diurutkan Karakter f i r s u spasi e g k n Jumlah
Frekuensi 2 2 2 2 2 1 1 1 1 1 15
2. Pembentukan pohon Shannon-Fano Pohon biner dibentuk dengan pembagian tabel karakter yang telah diurutkan ke dalam dua bagian dengan jumlah frekuensi masing-masing subbagian mendekati atau sama. Berikan label 0 pada subpohon kiri dan label 1 pada subpohon kanan. Ulangi pembagian ini secara rekursif hingga masing-masing karakter menjadi daun kode yang bersesuaian. Pembentukan pohon biner dari string ”fungsi rekursif” adalah: 1.
15
0
1
8
7
2.
15
0
1
8 0 4
7 0
1 4
3
1 4
3.
15 0
7
8
0
1
4
f:2
0
4 1
0
1
i:2
4
3 1
0
1
0
s:2
r:2
u:2
4.
0
1
1 2
2
spasi:1
15 0
7
8
0
1
1
4
0
4
0
1
f:2
i:2
0 r:2
1 4
3 1 s:2
0
0
1
u:2
spasi:1
1
2 0
e:1
2 1 g:1
0 k:1
1 n:1
Gambar 2.5 Pembentukan Pohon Shannon-Fano
3. Kode Shannon-Fano yang diperoleh dari pohon biner yang telah terbentuk adalah: Tabel 2.4 Tabel Kode Shannon-Fano untuk Masing-masing Karakter Karakter
Frekuensi (f)
f i r s u spasi e g k n Jumlah
2 2 2 2 2 1 1 1 1 1 15
Kode ShannonFano 000 001 010 011 100 101 1100 1101 1110 1111
Panjang kode (ssf)
Total panjang (fxssf)
3 3 3 3 3 3 4 4 4 4 34
6 6 6 6 6 3 4 4 4 4 49
Dengan demikian, jumlah bilangan bit yang dibutuhkan oleh algoritma Shannon-Fano untuk merepresentasikan string ”fungsi rekursif” adalah 49 bit. String tersebut dimampatkan dengan rasio sebesar:
u k u r afni l eh a s ipl e m a m tpaan * 1 0 0% Rasio Pemampatanan= u k u r afni l es e m u l a 4 9 m=n p a * 1 0%0 1 2 0
= 40,8% Dengan demikian string ”fungsi rekursif” dimampatkan menjadi rangkaian bit: 0001001111110101100110101011001110100010011001000
Untuk proses penirmampatan (decompression) atau menyusun kembali data dari kode biner menjadi sebuah string asli dapat digunakan tabel kode Shannon-Fano yang telah terbentuk atau menggunakan algoritma penirmampatan. Pada proses penirmampatan, rangkaian bit biner 0001001111110101100110101011001110100010011001000 dimulai dengan membaca bit pertama yaitu ”0”, tidak terdapat bit ”0” pada tabel kode Shannon-Fano. Lalu baca bit berikutnya, sehingga menjadi ”00”, tidak terdapat juga bit ”00” pada kode Shannon-Fano, lalu baca lagi bit berikutnya, sehingga menjadi ”000”. Rangkaian bit ”000” ini ditemukan pada tabel kode Shannon-Fano yaitu bit yang merepresentasikan karakater ”f”. Proses ini terus dilakukan hingga tidak terdapat lagi bit biner.
Berdasarkan hasil pemampatan string ”fungsi rekursif” menggunakan algoritma Huffman pada Contoh 2.1, diperoleh string hasil pemampatan yang berukuran 49 bit, sedangkan pemampatan dengan algoritma Shannon-Fano pada Contoh 2.2 juga diperoleh string hasil pemampatan yang berukuran sama yaitu 49 bit.
Dengan demikian, ke dua algoritma dapat menghemat pemakaian ruang media penyimpanan dari pada menyimpan file dengan kode ASCII yang berukuran 120 bit.
