PENGOLAHAN CITRA ( PERTEMUAN 10)

REFERENSI TENTANG (SHANNON FANO, HUFFMAN, RUN LENGHT ENCODING (RLE)

____________________________________________________________________________________

Nama         : Fransiskus Xaverius Budi Setiawan
Nim            : 17200185
Kelas          : 17.5A.07
Matkul       : Pengolahan Citra
__________________________________________________________________________________

1.1 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 inimenggantikan 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

    Menurut Salomon (2007), kompresi data adalah proses pengubahan serangkaian data input menjadi data output yang mempunyai ukuran lebih kecil. Algoritma Shannon Fano ditemukan dan dikembangkan oleh Claude Shannon dan Robert Fano. Algoritma Shannon Fano mengkodekan tiap karakter yang ada dalam serangkaian data input dengan menggunakan rangkaian beberapa bit, di mana karakter yang sering muncul dikodekan dengan rangkaian bit yang lebih pendek dibandingkan karakter yang jarang muncul

    Berikut ini adalah langkah-langkah kompresi dengan menggunakan algoritma Shannon Fano: 

1. Buat pohon Shannon dengan cara membaca semua karakter di dalam teks untuk menghitung
    probabilitas kemunculan tiap karakter. 

2. Karakter-karakter ini kemudian disusun dari yang mempunyai probabilitas kemunculan paling besar
    ke karakter yang mempunyai probabilitas kemunculan paling kecil.  

3. Bagi dua serangkaian karakter ini menjadi 2 subset yang mempunyai jumlah probabilitas yang sama
    atau hampir sama. 

4. Semua simbol dalam subset pertama diberi kode 0 sedangkan simbol pada subset lainnya diberi       
    kode 1.  

5. Ketika pada sebuah subset hanya terdapat 2 macam simbol, kode mereka dibedakan dengan cara          memberikan 1 bit lagi ke masing-masing simbol.

6. Lakukan langkah nomor 3, 4, dan 5 pada tiap-tiap subset secara rekursif sampai tidak ada lagi subset
    yang tersisa.   

1.1 Huffman

    Algoritma Huffman adalah salah satu algoritma kompresi tertua yang disusun oleh David Huffman pada tahun 1952. Algoritma tersebut digunakan untuk membuat kompresi jenis lossy compression, yaitu pemampatan data dimana tidak satu byte pun hilang sehingga data tersebut utuh dan disimpan sesuai dengan aslinya. Pada sejarahnya, Huffman sudah tidak dapat membuktikan apapun tentang kode apappun yang efisien, tapi ketika tugasnya hampir final, ia mendapatkan ide untuk menggunakan pohon binary untuk menyelesaikan masalahnya mencari kode yang efisien.  Pada dasarnya, algoritma Huffman ini bekerja seperti mesin sandi morse, dia membentuk suatu kode dari suatu karakter. Sehingga karakter tersebut memiliki rangkaian bit yang lebih pendek dibandingkan sebelumnya. 

  

1.1 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 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 1nti dari algortima huffman adalah menggunakan priority queue yang direkursif sehingga        membentuk pohon dengan kompleksitas waktu On(log n)

contoh pohon Huffman 1.1

contoh  pohon Huffman 1.2

1.1  Run Legth Encoding (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. 

2.1 Shannon Fano

    Algoritma Shannon-Fano dinamakan berdasarkan nama pengembangnya Claude Shannon dan Robert Fano. Algoritma Shannon-Fano merupakan kompresi yang bersifat lossless. Metode dimulai dengan deretan dari simbol n dengan kemunculan frekuensi yang diketahui. Mula-mula simbol disusun secara menaik (ascending order) berdasarkan frekuensi kemunculannya. Lalu set simbol tersebut dibagi menjadi dua bagian yang berbobot sama atau hampir sama. Seluruh simbol yang berada pada subset I diberi biner 0

    Sedangkan simbol yang berada pada subset II diberi biner 1. Setiap subset dibagi lagi menjadi dua subsubset dengan bobot kemunculan frekuensi yang kira-kira sama, dan biner kedua diberikan seperti subset I dan II. Ketika subset hanya berisi dua simbol, biner diberikan pada setiap simbol. Proses akan berlanjut sampai tidak ada subset yang tersisa (Salomon: 2010). 

    Algoritma Shannon-Fano merupakan algoritma kompresi data yang meng-kodekan setiap karakter dengan menggunakan beberapa rangkaian bit. Pembentukan bit yang mewakili masing-masing karakter dibuat berdasarkan frekuensi kemunculan tiap karakter. Tujuan dari penelitian ini adalah untuk menguji kompresi algoritma Shannon-Fano. Penelitian ini dilakukan terhadap dua kategori yaitu file dengan ukuran yang sama dan  memiliki karakter yang bervariasi dan file dengan ukuran yang berbeda dan karakter yang bervariasi. Hasil pengujian menunjukan bahwa file text dengan karakter yang bervariasi akan menghasilkan pemampatan file yang rendah sedangkan filetext dengan karakter yang tidak bervariasi memiliki tingkat pemampatan file yang tinggi dengan ukuran file yang sama.

2.1 Huffman

    sebuah tipe code yang optimal yang biasanya digunakan untuk lossless data compression. Algoritme Huffman Coding ditemukan oleh David A. Huffman pada saat ia masih seorang mahasiswa di MIT, ia menerbitkan karyanya pada tahun 1952 yang berjudul "A Method for the Construction of Minimum Redundancy Codes".

    Hasil dari algoritme Huffman bisa dipandang sebagai sebuah tabel kode variabel-panjang untuk pengkodean simbol sumber (seperti sebuah karakter dalam sebuah file). Algoritme ini memperoleh dari tabel tersebut berdasarkan dari estimasi probabilitas atau frekuensi munculnya untuk setiap nilai yang mungkin dari simbol sumber. Seperti dalam metode pengkodean entropi lainnya, simbol yang lebih umum diwakili dengan bit yang lebih sedikit daripada simbol kurang umum.

    Pada tahun 1951, David A. Huffman dan mahasiswa sekelasnya di teori informasi MIT diberikan pilihan untuk membuat makalah atau mengerjakan ujian akhir. Topik untuk makalah tersebut yang diberikan oleh profesor kelas itu, Robert M. Fano, adalah pencarian kode biner yang paling efisien. Huffman, yang tidak mampu untuk membuktikan kode mana yang paling efisien, hampir menyerah dan sudah mau memutuskan untuk mengambil ujian akhir-nya saja saat tiba-tiba ia terpikir sebuah ide untuk menggunakan algoritme pohon biner yang diurutkan berdasarkan frekuensi. Dengan cepat, ia langsung membuktikan kepada profesornya bahwa metode tersebut adalah metode yang paling efisien.

Hasil dari alogartima Huffman

Daftar Pustaka

http://ojs.uho.ac.id/index.php/dinamika/article/view/267
https://media.neliti.com/media/publications/67427-ID-implementasi-dan-analisis-perbandingan-a.pdf

Perangkat_Lunak_Kompresi_Teks_Menggunakan_Algoritma_Shannon_Fano

https://hendroprasetyo.com/memahami-algoritma-run-length-encoding-compressi/#.Y3X0wHZBzIV

https://id.wikipedia.org/wiki/Pengodean_Huffman

https://en.wikipedia.org/wiki/Run-length_encoding

https://media.neliti.com/media/publications/339018-analisa-kode-huffman-untuk-kompresi-data-1ab99bbd.pdf