Alogoritma Shannon Fanon
Pengertian Algoritma Shannon-Fano
Algoritma Shannon-Fano coding ditemukan oleh
Claude Shannon (bapak teori informasi) dan Robert
Fano pada tahun 1949. Pada saat itu metode ini
merupakan metode yang paling baik tetapi hampir
tidak pernah digunakan dan dikembangkan lagi
setelah kemunculan algoritma Hufman. Pada
dasarnya
metode ini menggantikan setiap simbol dengan
sebuah alternatif kode biner yang panjangnya
ditentukan berdasarkan probabilitas dari simbol
tersebut Di bidang kompresi data, Shannon-Fano
coding adalah teknik untuk membangun sebuah kode
awalan didasarkan pada seperangkat simbol dan
probabilitas (diperkirakan atau diukur). Namun,
algoritmya ini dirasa kurang optimal dalam arti
bahwa ia tidak mampu mencapai kode seefisien
mungkin seperti kode diharapkan panjang seperti
algoritma Huffman .
Cara Kerja Algoritma Shannon-Fano Pada dasarnya cara kerja dari algoritma Shannon-Fano ini sama persis dengan Huffman. Algoritma ini membentuk sebuah pohon, kemudian meng-encodingnya, dan yang terahir adalah megnembalikannya dalam bentuk karakte teks atau decoding. Hanya saja perbedaan yang fundamental terdapat pada pembuatan pohon. Pembuatan pohon pada Shannon-Fano dibuat berdasarkan proses dari atas ke bawah – berbeda dengan huffman yang membuat pohon dari bawah ke atas. Sebuah pohon Shannon-Fano dibangun sesuai dengan spesifikasi yang dirancang untuk mendefinisikan tabel kode yang efektif. Algoritma yang sebenarnya sederhana: 1. Untuk daftar simbol-simbol tertentu, mengembangkan sebuah daftar yang sesuai probabilitas atau frekuensi dihitung sehingga setiap simbol frekuensi relatif kejadian diketahui. 2. Menyortir daftar simbol-simbol sesuai dengan frekuensi, dengan simbol-simbol yang paling sering terjadi di sebelah kiri dan yang paling umum di sebelah kanan. 3. Membagi daftar menjadi dua bagian, dengan total frekuensi dihitung dari kiri setengah menjadi seperti dekat dengan jumlah yang tepat mungkin. 4. Kiri setengah dari daftar ditetapkan angka biner 0, dan hak diberikan setengah digit 1. Ini berarti bahwa kode untuk simbol-simbol pada semester pertama semua akan dimulai dengan 0, dan aturan-aturan di paruh kedua akan semua mulai dengan 1. 5. Rekursif menerapkan langkah 3 dan 4 untuk masing-masing dari dua bagian, membagi kelompok dan menambahkan kode bit sampai setiap simbol telah menjadi kode yang sesuai daun di pohon. Untuk mempermudah, diilustrasikan dengan gambar berikut.
Algoritma Shannon-Fano termasuk
algoritma statistik yang menghitung kode
bebas prefiks. Algoritma ini dibagi menjadi
dua yaitu :
1. Algoritma Shannon-Fano Tak Adaptif
2. Agoritma Shannon-Fano Adaptif
Algoritma Shannon-Fano Statik (Tak
Adaptif)
Kompresi dengan algoritma ini dilakukan
dengan langkah–langkah sebagai berikut :
1. Membuat tabel statistik untuk
kemunculan huruf.
2. Mengurutkan data pada tabel dengan
a. Meletakkan huruf dengan
kemunculan tertingi pada posisi
paling atas, kemudian diikuti yang
lebih kecil sampai selesai.
b. Jika terdapat statistik kemunculan
yang sama maka dilakukan
pengurutan sesuai tabel ASCII.
3. Menghitung kode masing–masing huruf
dengan memecah tabel menjadi dua
bagian dengan pembagian masing–
masing subtabel mempunyai kemunculan
yang sama,atau mendekati.
4. Jika tidak dapat dibagi dalam jumlah
kemunculan yang sama maka subtabel
yang atas diberi kemunculan yang lebih
kecil daripada subtabel dibawahnya.
5. Memberikan kode 0 untuk subtabel
sebelah atas dan kode 1 untuk subtabel
sebelah bawah.
6. Melakukan langkah 3 dan langkah 4 dan
langkah 5 untuk masing-masing subtabel
sampai subtabel–subtabel tersebut tidak
dapat dibagi lagi dalam subtabel yang
lebih kecil.
b). Algoritma Shannon-Fano Dinamik
(Adaptif)
Mengkompresi input stream menggunakan
metode Shannon-Fano Dinamik (Adaptif)
dapat dilakukan dengan tahapan sebagai
berikut:
1) Menggunakan tabel untuk menyimpan
statistik dari huruf pertama sampai posisi
aktual
2) Metode ini menggabungkan perhitungan
statistik dan kode dalam pengkodean
pesan.
3) Pada saat pengisian tabel diurutkan
berdasarkan runtun input, kemudian
disusun berdasarkan kode ASCII.
4) Setiap ada pemunculan huruf yang baru
maka jumlah untukk escape bertambah
satu, sedangkan jika huruf tersebut
pernah muncul maka jumlah escape tidak
bertambah,yang bertambah hanya pada
huruf yang muncul kembali.
5) Pada saat awal tabel dianggap masih
kosong , karena itu digunakan satu huruf
khusus yang disebut sebagai escape.
Algoritma Huffman
Pengertian Algoritma Huffman
Algoritma pengkodean Huffman sebetulnya hampir sama dengan algoritma pengkodean Shannon-Fano. Yaitu simbul yang mempunyai probabilitas paling besar diberi kode paling pendek (jumlah bit kode sedikit) dan simbul dengan probabilitas paling kecil akan memperoleh kode paling panjang (jumlah bit kode banyak). Kode tersebut diperoleh dengan cara memyusun sebuah pohon Huffman untuk masing-masing simbul berdasarkan nilai probabilitasnya. Simbul yang memiliki probabilitas terbesar akan dekat dengan root (sehingga memiliki kode terpendek) dan simbul yang memiliki probabilitas terkecil akan terletak jauh dari root (sehingga memiliki kode terpanjang). Pohon Huffman merupakan pohon-biner (binary tree). Sedangkan Algoritma penyusunan pohon beserta pengkodeannya adalah sebagai berikut : • Berdasarkan daftar simbul dan probabilitas, buat dua buah node dengan frekuensi paling kecil. • Buat node parent dari node tersebut dengan bobot parent merupakan jumlah dari probabilitas kedua node anak tersebut. • Masukkan node parent tersebut beserta bobotnya ke dalam daftar, dan kemudian kedua node anak beserta probabilitasnya dihapus dari daftar. • Salah satu node anak dijadikan jalur (dilihat dari node parent) untuk pengkodean 0 sedangkan lainnya digunakan untuk jalur pengkodean 1.
Metode Huffman
Algoritma Huffman merupakan suatu algoritma yang terbilang klasik dan sangat populer digunakan. hal ini dikarenakan file yang dikompresi tidak mengalami perubahan ketika dilakukan proses dekompresi sehingga cocok digunakan untuk kompresi data citra digital, data teks, audio dan suara . pada metode huffman karakter-karakter yang digunakan bentuk ASCII akan diubah kedalam bentuk bit-bit yakni 0 dan 1. dan pengkodeannya mirip dengan sandi morse. Prinsip pada algoritma kompresi huffman adalah data atau file yang terdapat perulangan karakter vokal ataupun konsonan akan dihitung banyaknya frekwensi kemunculan karakter tersebut [13]. sebagai contoh pada sebuah dokument terdapat karakter A, B, C, D dan E. kemudian mengurutkan data-data karakter dimulai dari tingkat frekwensi karakter yang paling sering muncul sampai dengan karakter yang jarang muncul. kemudian membentuk struktur pohon huffman untuk penggunaan karakter A sampai dengan karakter E.
dari gambar diatas pada pohon huffman dapat dibaca yaitu :
1. untuk karakter A dikodekan menjadi kode biner yakni 01
2. Karakter B dikodekan menjadi kode biner 10.
3. Karakter C dikodekan menjadi kode biner 11.
4. Karakter D dikodekan menjadi kode biner 000.
5. Karakter E dikodekan menjadi kode biner 001.
Pembuatan Pohon Huffman
Pembuatan Pohon Huffman
Pohon Huffman ini dibentuk berdasarkan kode
prefiks. Kode biner dibentuk secara prefiks dan kode
biner ini tidak mungkin terbentuk sama satu sama
lainnya. Karakter-karakter yang akan
direpresentasikan dalam biner, dipisahkan ke dalam
cabang pohon biner dan beri frekuensinya. Cabang
sebelah kiri diberi bit 0 sebagai identitas, dan bit
kanan diberi angka 1. pada akhirnya bit ini akan
dibaca dari akar hingga simpul dari suatu karakter itu
sehingga terbentuk angka biner identitas untuk
meringkas memori sehingga menjadi efisien.
Langkah dalam membentuk pohon Huffman ini dapat
diringkas menjadi sebagai berikut :
1. hitung semua frekuensi kemunculan tiap
karkternya. Hal ini dapat dilakukan hanya
dengan menghitung (memroses) semua karakter
dari awal hingga akhir dengan saru kali lewat
(one way pass).
2. kemudian terapkan strategi algoritma greedy.
Apa itu algoritma greedy? Yaitu algoritma
greedy merupakan metode yang paling populer
untuk memecahkan persoalan optimasi [4]. Ada
dua persoalan optimasi, yaitu optimasi minimum
dan maksimum, yang digunakan pada hal ini
adalah optimasi minimum. Algoritma greedy
pada pembentukan pohon di sini yaitu membagi
dua pohon menjadi frekuensi yang lebih kecil,
kemudian hubungkan pada sebuah akar. Akar
tersebut kemudian dipisah kembali dan digabung
dengan akar yang berada di atasnya (akar baru).
3. proses ketiga yaitu proses rekursif dari proses
kedua sehingga akar utama pohon memiliki
frenuensi bernilai 1.
Inti dari algortima huffman adalah menggunakan
priority queue yang direkursif sehingga membentuk
pohon dengan kompleksitas waktu On(log n)[3].
Proses-proses ini akan lebih jelas dengan contoh
gambar.
Misal karakternya adalah ABACCDA. Jika kita
mengikuti kode ascii tanpa menggunakan algoritma
huffman, maka kita akan memakan banyak memori
yaitu 7bit x 8 karakter = 56 bit. Tapi dengan pohon
huffman, kita akan lihat bedanya. Yang pertama
dilakukan dalam menbentuk pohon huffman yaitu
hitung frekuensi dari tiap-tiap karakter
A : 3/7
B : 1/7
C : 2/7
D : 1/7
Kemudian lakukan proses kedua dari proses-proses di
atas yaitu buatlah simpul dan akar dari frekuensi
yang terkecil
Kemudian proses ini diulang (rekursif) hingga semua
karakter terbentuk menjadi pohon.
Dapat dilihat pada contoh pembentukan phon di
bawah ini:
Pembuatan Pohon Huffman
Pohon Huffman ini dibentuk berdasarkan kode
prefiks. Kode biner dibentuk secara prefiks dan kode
biner ini tidak mungkin terbentuk sama satu sama
lainnya. Karakter-karakter yang akan
direpresentasikan dalam biner, dipisahkan ke dalam
cabang pohon biner dan beri frekuensinya. Cabang
sebelah kiri diberi bit 0 sebagai identitas, dan bit
kanan diberi angka 1. pada akhirnya bit ini akan
dibaca dari akar hingga simpul dari suatu karakter itu
sehingga terbentuk angka biner identitas untuk
meringkas memori sehingga menjadi efisien.
Langkah dalam membentuk pohon Huffman ini dapat
diringkas menjadi sebagai berikut :
1. hitung semua frekuensi kemunculan tiap
karkternya. Hal ini dapat dilakukan hanya
dengan menghitung (memroses) semua karakter
dari awal hingga akhir dengan saru kali lewat
(one way pass).
2. kemudian terapkan strategi algoritma greedy.
Apa itu algoritma greedy? Yaitu algoritma
greedy merupakan metode yang paling populer
untuk memecahkan persoalan optimasi [4]. Ada
dua persoalan optimasi, yaitu optimasi minimum
dan maksimum, yang digunakan pada hal ini
adalah optimasi minimum. Algoritma greedy
pada pembentukan pohon di sini yaitu membagi
dua pohon menjadi frekuensi yang lebih kecil,
kemudian hubungkan pada sebuah akar. Akar
tersebut kemudian dipisah kembali dan digabung
dengan akar yang berada di atasnya (akar baru).
3. proses ketiga yaitu proses rekursif dari proses
kedua sehingga akar utama pohon memiliki
frenuensi bernilai 1.
Inti dari algortima huffman adalah menggunakan
priority queue yang direkursif sehingga membentuk
pohon dengan kompleksitas waktu On(log n)[3].
Contoh Langkah-langkah Pembentukan Pohon Huffman
Pohon Huffman yang terbentuk beserta kode simbul
Kelebihan dan Kekurangan Shannon-Fanon dan Huffman
Dilihat dari cara dalam pembentukan pohon, sudah
tampak jelas perbedaan antara kedua algoritma
tersebut. Algoritma huffman memebentuk pohon dari
bawah sampai atas atau dengan kata lain dari simpul
hingga akar, sedang algortima shannon-fano
membentuk pohon dari akar ke simpul. Dalam
pembentukan prioritas dari pohon yang dibenuk juga
berbeda. Pada kasus sebelumnya, pohon huffman
terbantuk dengan mengelompokkan karakter string
yang memiliki frekuensi rendah satu per satu
kemudian membentuknya menjadi simpul dan
merekursifnya. Namun, pada pohon shannon-fano,
semua karakter dikelompokkan berurutan dari kiri ke
kanan dari frekuensi yang sering muncul ke frekuensi
yang umum. Untuk mempermudah dalam
melihatperbedaan efisiensi dalam kedua algoritma,
Run Length Encoding (RLE)
Pengertian Run Length Enconding (RLE)
Run Length Encoding (RLE) merupakan salah satu jenis lossless yang paling sederhana dari skema
kompresi data dan didasarkan pada prinsip sederhana data encoding. RLE sangat cocok
digunakan untuk mengompresi data yang berisi karakter-karakter berulang atau data berjalan
(yaitu: urutan dimana nilai data yang sama terjadi pada banyak elemen data yang berturut-turut).
Penggunaan metode RLE sangat berguna untuk data yang berisi banyak data yang berjalan misalnya: citra
grafis sederhana seperti ikon, citra garis, dan animasi. Metode ini tidak berguna untuk file yang tidak
memiliki data berjalan karena sangat dapat meningkatkan ukuran file.
Kompresi data pada file yang berisi karakter-karakter berulang dengan cara, karakter yang sama
berturut-turut diubah menjadi 2 nilai, yaitu jumlah karakter yang sama dan karakter itu sendiri .
Mengompresi citra menggunakan RLE didasarkan pada pengamatan bahwa jika terdapat piksel pada citra
secara acak, ada kemungkinan bahwa warna disebelahnya memiliki warna yang sama . Semakin
detail piksel pada citra, semakin buruk kompresinya.
Sistem kerja dengan metode RLE (Run Length Encoding) adalah sebagi berikut: (1) RLE bekerja
dengan mengurangi ukuran fisik dengan adanya pengulangan string dari deretan karakter/bit data; (2)
String perulangan ini dinamakan RUN dan biasanya dikodekan dalam 2 bit. Bit pertama merupakan
jumlah perulangan dan bit kedua adalah karakter yang diulang [8]. Misalnya kompresi data yang memiliki
string “MMMMM” yang direpresentasikan dalam 5 karakter atau bit data. Jika menggunakan RLE
dikompresi menjadi 2 karakter atau bit yaitu 5M (1 buah paket RLE 2 bit, bit pertama “5” disebut run
count dan bit kedua “A” disebut run value). Data yang memiliki string “ABBBCCCCD” yang
direpresentasikan dalam 8 bit, dikompresi menjadi 6 bit yaitu A3B4CD. Data yang memiliki string
“HGYTRK” yang direpresentasikan dalam 6 bit, dikompresi menjadi 12 bit yaitu 1H1G1Y1T1R1K.
Dalam kasus tersebut terlihat bahwa kompresi data menjadi tidak efisien karena menghasilkan bit yang
lebih besar dari bit sebelum kompresi, sehingga kompresi dengan RLE lebih cocok digunakan unutuk
karakter yang berulang.
Metode Run Length Encoding
Algoritma RLE ini merupakan teknik
kompresi yang lossless, sehingga kita dengan
mudah dapat melakukan dekompresi citra
kembali. Bagaimana algoritma RLE bekerja?
Kita coba implementasikan dengan citra
grayscale ukuran 6x6 bit (8 derajat keabuan)
sebagai berikut:
1 1 1 7 1 3
4 4 6 1 2 2
7 7 7 5 5 5
6 4 4 2 2 2
5 5 2 2 2 1
2 3 3 3 0 0
Kode RLE merupakan pasangan intensitas
warna dan banyaknya intensitas warna yang
muncul berurutan. Sehingga di dapat kode RLE
nya adalah sebagai berikut:
1 3 7 1 1 1 3 1 4 2 6 1 1 1 2 2 7 3 5 3 6 1 4 2 2 3
5 2 2 3 1 1 2 1 3 3 0 2
Cara membaca kode diatas adalah : intensitas
warna 1 muncul 3 kali, intensitas warna 7
muncul 1 kali, intensitas warna 1 muncul 1 kali,
intensitas warna 3 muncul 1 kali,...... dan
seterusnya. Cocokkan dengan citra aslinya.
RLE merupakan metode kompresi yang
banyak didukung oleh format file gambar
seperti: TIFF, BMP, PCX.
RLE bekerja dengan mengurangi ukuran
fisik dengan adanya pengulangan string dari
deretan karakter / byte data.
String perulangan ini dinamakan RUN, dan
biasanya di kodekan dalam 2 byte. Byte
pertama merupakan jumlah perulangan dan
byte kedua adalah karakter yang diulang.
Implementasi dan Hasil RLE
Dengan menggunakan algoritma Run Length Encoding akan dikompresi beberapa citra dalam format
jpg, png, bmp, dan tiff menggunakan aplikasi matlab dengan algoritma RLE sehingga diperoleh
bagaimana keefektifan metode RLE dalam kompresi data citra. Berikut adalah potongan algoritma RLE
pada aplikasi matlab yang digunakan untuk melakukan encode citra:
%Show UI Image chooser
[FileName,PathName] = uigetfile({'*.bmp';'*.tiff';'*.jpg';'*.png';'*.*'},'Select Image
to Compress');
file = strcat(PathName, FileName);
%Read the image to matlab variable and identify the dimension
image = imread(file);
height = size(image,1);
width = size(image,2);
n_channel = size(image,3);
%variable container for compressed image
compressed = zeros(1,1,1);
%start count time
tic
%RLE Algorithm
for channel = 1:n_channel
for y = 1:height
compressed_y = y;
compressed_x = 1;
last_pixel = image(y,1,channel);
match = 1;
for x = 2:width
current_pixel = image(y,x,channel);
if(last_pixel == current_pixel)
match = match + 1;
if(match == 256)
compressed(compressed_y, compressed_x, channel) = match;
compressed(compressed_y, compressed_x + 1, channel) = last_pixel;
compressed_x = compressed_x + 2;
match = 1;
last_pixel = current_pixel;
end
else
compressed(compressed_y, compressed_x, channel) = match;
compressed(compressed_y, compressed_x + 1, channel) = last_pixel;
compressed_x = compressed_x + 2;
match = 1;
last_pixel = current_pixel;
end
end
compressed(compressed_y, compressed_x, channel) = match;
compressed(compressed_y, compressed_x + 1, channel) = current_pixel;
end
end
%Convert compressed data to 8 bit integer
compressed = uint8(compressed);
%Save compressed result
imwrite(compressed,'encode_result.bmp');
%end count time
time = toc;
Kompresi citra dengan metode Run Length Encoding (RLE)
Untuk mengompresi citra di atas dengan menggunakan metode RLE, ditentukan terlebih dahulu
matriks dari intensitas warna yang terdapat pada citra. Matriks diperoleh melalui aplikasi matlab dengan
algoritma sebagai berikut (file citra yang ingin ditentukan matriksnya dan script matlab harus berada di
folder yang sama, agar program dapat dijalankan).
img=imread('nama file citra.format');
asci=uint8(img)
1. Citra grayscale format png
Pada citra grayscale format png diperoleh matriks seperti berikut:
Selanjutnya ditentukan Kode RLE dari pasangan nilai dari matriks di atas. Kode RLE diperoleh dari
pasangan intensitas warna dan banyaknya intensitas warna yang muncul secara berurutan arah x axis.
Berdasarkan matriks diperoleh pasangan nilai:
Kode RLE yang diperoleh: 254 8 254 8 254 8 254 8 235 7 237 1 163 6 159 1 188 1 121 6 113 1 165 1
128 6 121 1 169 1
Kode RLE di atas bermakna bahwa intensitas warna kode 254 muncul sebanyak 32 kali secara
berurutan arah x axis, intensitas warna kode 235 muncul 7 kali, intensitas warna kode 237 muncul 1 kali,
dan seterusnya. Pasangan yang dihasilkan sebanyak 15, sehingga citra memiliki 30 piksel.
Ukuran citra awal = 64 × 3 bit = 192 bit
Ukuran citra setelah dikompresi = 30 × 3 bit = 90 bit
Rasio kompresi =
= 0,46875
Hal ini berarti bahwa citra terkompresi sebesar 46,9% lebih kecil dari ukuran citra semula.
2. Citra grayscale format jpg
Pada citra format jpg diperoleh matriks seperti berikut:
Berdasarkan matriks diperoleh pasangan nilai:
253 1 254 2 252 1 255 2 254 2 255 5 252 1 253 1 255 1 253 1 254 1 253 1
255 1 254 1 252 1 253 1 255 1 253 1 255 1 254 3 255 2 252 1 234 1 237 1 235 1 234 1 233 1 237 1 232 1
239 1 163 3 165 1 162 2 158 1 189 1 121 1 119 1 122 1 123 1 121 2 116 1 164 1 128 1 127 1 130 1 126 1
127 1 130 1 120 1 170 1
Pasangan yang dihasilkan sebanyak 50, sehingga citra memiliki 100 piksel.
Ukuran citra awal = 64 × 3 bit = 192 bit
Ukuran citra setelah dikompresi = 100 × 3 bit = 300 bit
Rasio kompresi =
= 1,5625
Hal ini berarti bahwa citra mengalami kompresi negatif sebesar 156,25%, hasil kompresi citra berukuran
lebih besar dari ukuran citra semula.
Daftar Pustaka
https://adoc.pub/queue/implementasi-metode-run-length-encoding-rle-untuk-kompresi-c.html
https://informatika.stei.itb.ac.id/~rinaldi.munir/Matdis/2009-2010/Makalah0910/MakalahStrukdis0910-006.pdf
http://staff.uny.ac.id/sites/default/files/KOMPRESI%20DATA_Eko.pdf
http://seminar.uny.ac.id/semnasmatematika/sites/seminar.uny.ac.id.semnasmatematika/files/full/T-38.pdf
https://jurnal.uisu.ac.id/index.php/infotekjar/article/download/2892/pdf
Komentar
Posting Komentar