Nim : 17200083
Nama : Ahmad Guntur Dwi Herjanto
Kelas : 17.5a.97
Mata Pelajaran : Pengolahan Citra
1. Algoritma Shannon Fano
Refrensi : Analisis Algoritma Shannon-Fano Dalam Kompresi Data
Pengajuan Proposal Skripsi Mahasiswa STMIK CIC Cirebon
Chairun Nas1
, Wanda Ilham2
, Ilwan Syafrinal3
,
Algoritma Shannon-Fano pada dasarnya adalah metode yang mengganti setiap simbol yang ada pada data menjadi kode biner yang panjangnya ditentukan berdasarkan pada probabilitas simbol. Algoritma ini disebut sebagai teknik kompresi data paling awal yang ditemukan oleh Claude Shannon dan Robert Fano pada tahun 1949 di MIT. Algoritma Shannon-Fano menggunakan pendekatan top down dalam penyusunan binary tree, sehingga sangat efisien untuk mengkompresi data teks yang berukuran besar.
Secara garis besar, algoritma Shannon-Fano memiliki ketentuan sebagai berikut:
a. Setiap simbol yang berbeda memiliki kode yang berbeda.
b. Simbol dengan probabilitas yang kecil memiliki kode panjang bit yang lebih panjang dan simbol dengan probabilitas yang lebih besar memiliki panjang bit yang lebih pendek.
c. Meskipun kode yang dihasilkan memiliki panjang bit yang berbeda dengan kode pada karakter asli, tetapi dapat dikodekan secara unik.
b. Simbol dengan probabilitas yang kecil memiliki kode panjang bit yang lebih panjang dan simbol dengan probabilitas yang lebih besar memiliki panjang bit yang lebih pendek.
c. Meskipun kode yang dihasilkan memiliki panjang bit yang berbeda dengan kode pada karakter asli, tetapi dapat dikodekan secara unik.
Maka adapun langkah-langkah dalam kompresi data pada algoritma ShannonFano dapat dilihat sebagai berikut:
a. Urutkan simbol sesuai dengan karakter tabel ASCII serta bangun tabel
daftar kemunculan simbol dari data (Probabilitas simbol)
b. Urutkan tabel kemunculan simbol sesuai dengan frekuensi kemunculan dari frekuensi kemunculan paling tinggi ke paling terendah.
c. Bagilah tabel kemunculan simbol menjadi dua bagian dengan pembagian berdasarkan pada total frekuensi bagian (bagian atas) sedekat mungkin dengan jumlah frekuensi dengan bagian yang lain (bagian bawah). Hal ini dapat dilakukan dengan membentuk pohon biner.
d. Tetapkan bagian atas dengan digit biner 0 dan bagian bawah dengan digit biner 1
e. Terapkan langkah 3 dan 4 secara berulang-ulang untuk masing-masing dua bagian. Bagilah kelompok dan tambahkan bit ke kode sehingga setiap simbol memperoleh daun yang sesuai dengan pohon biner.
b. Urutkan tabel kemunculan simbol sesuai dengan frekuensi kemunculan dari frekuensi kemunculan paling tinggi ke paling terendah.
c. Bagilah tabel kemunculan simbol menjadi dua bagian dengan pembagian berdasarkan pada total frekuensi bagian (bagian atas) sedekat mungkin dengan jumlah frekuensi dengan bagian yang lain (bagian bawah). Hal ini dapat dilakukan dengan membentuk pohon biner.
d. Tetapkan bagian atas dengan digit biner 0 dan bagian bawah dengan digit biner 1
e. Terapkan langkah 3 dan 4 secara berulang-ulang untuk masing-masing dua bagian. Bagilah kelompok dan tambahkan bit ke kode sehingga setiap simbol memperoleh daun yang sesuai dengan pohon biner.
1.1 Analisa Dan Pembahasan
Sebelum dilakukan implementasi kedalam Sistem, algoritma Shannon-Fano perlu dilakukan analisa untuk mengetahui bagaimana proses kompresi data yang dilakukan oleh algoritma. Pada pembahasan berikut data yang akan dilakukan analisa adalah berupa teks. Adapun contoh data kasus yang akan dilakukan analisa sebagai berikut:
“ PENELITIAN INI DILAKUKAN UNTUK MEMPEROLEH GELAR
SARJANA ILMU KOMPUTER ”
Dari data teks berikut, selanjutnya dilakukan proses kompresi algoritma Shannon-Fano. Berdasarkan langkah-langkah pada algoritma Shannon-Fano, maka dapat dijabarkan proses analisis sebagai berikut:
a. Mengurutkan karakter sesuai dengan tabel ASCII dan menghitung frekuensi kemunculan. Adapun pengurutan berdasarkan karakter sesuai dengan tabel ASCII dan frekuensi kemunculan karakter dapat dilihat pada Tabel 1 berikut:
Dari pengkodean ke dalam ASCII, maka dapat diketahui besar ukuran
memori yang dibutuhkan untuk menyimpan data kasus tersebut. Untuk
mengetahui ukuran memori yang dibutuhkan dari data kasus tersebut
adalah sebagai berikut:
Ukuran Memori Karakter = Banyak Karakter X Ukuran Bit (1)
Maka dari rumus diatas peroleh ukuran memori dari data kasus seperti
pada Tabel 2 Berikut:
Proses selanjutnya adalah membagi kemunculan karakter menjadi dua
bagian, dimana jumlah frekuensi bagian atas (bagian pertama) sedekat
mungkin dengan jumlah frekuensi dengan bagian bawah (bagian
kedua). Untuk membagi bagian tersebut, dapat digunakan dengan cara
membentuk pohon biner. Pada pohon biner, bagian atas dimulai dengan digit biner 0 dan bagian bawah dimulai dengan digit 1. Lakukan hal ini
secara berulang sampai semua karakter memiliki digit biner. Adapun
pohon biner yang terbentuk adalah seperti Gambar 2 berikut
Untuk menghitung ukuran memori karakter yang telah dikodekan
dengan algoritma Shannon-Fano dapat mengikuti rumus menghitung
ukuran memori karakter di atas. Adapun ukuran memori dari karakter
yang telah dikodekan dapat dilihat pada Tabel 5 berikut:
Setelah dilakukan kompresi dengan algoritma Shannon-Fano, maka
ukuran memori data kasus dari 69 Byte menjadi 35,25 byte. Selanjutnya
dapat dihitung rasio pemampatan dengan menggunakan rumus:
Maka dengan menggunakan rumus diatas, diperoleh rasio kompresi
sebagai berikut:
Dari proses kompresi, maka diperoleh bahwa 48,92 % ukuran memori
dari ukuran awal berhasil di kompresi.
2. Metode Huffman
Refrensi: Teknik Kompresi Citra Menggunakan Metode Huffman
Tri Rahmah Silviani, Ayu Arfiana
Program Pascasarjana Universitas Negeri Yogyakarta
Metode Huffman
Metode Huffman merupakan salah satu metode dalam teori persandian yang dimanfaatkan dalam
proses kompresi data. Kode Huffman diusulkan oleh Dr. David A. Huffman pada tahun 1952 sebagai
metode yang ditujukan untuk mengkonstruksi kode redundansi minimum [3]. Metode Huffman termasuk dalam kelompok metode kompresi lossless yaitu metode kompresi yang tidak menghilangkan informasi
setelah dilakukan kompresi [1]. Hasil yang diperloleh dari proses kompresi dengan file asli tidak berubah,
hanya saja bit dalam file tersebut berkurang. Cara kerja dalam metode ini adalah dengan melakukan
pengkodean dalam bentuk bit untuk mewakili data karakter.
Citra yang telah dikompresi tentu harus didekompresi agar citra tersebut sesuai dengan citra aslinya.
Terdapat dua cara yang dapat dilakukan dalam kompresi citra menggunakan metode Huffman, yaitu [2]:
1. Menggunakan pohon Huffman
Langkah-langkah penguraian kode Huffman menggunakan pohon Huffman sebagai berikut:
a. Membaca bit pertama dari string biner
b. Melakukan traversal pada pohon Huffman mulai dari akar sesuai dengan bit yang dibaca.
c. Jika bit yang dibaca nol maka akar yang dibaca adalah akar kiri, sementara itu jika yang dibaca 1
maka yang dibaca adalah akar kanan
d. Jika anak dari pohon bukan daun maka baca bit berikutnya dari string biner
e. Pada daun tersebut ditemukan simbol dan proses penguraian kode Huffman selesai
2. Menggunakan tabel kode Huffman
Tabel kode Huffman disusun menggunakan prefix code, sehingga kode untuk sebuah karakter
tidak bisa menjadi awalan dari kode yang lain. String biner yang dienkripsi dapat dipisahkan
berdasarkan rangkaian bitnya untuk kemudian diuraikan menjadi data awal. Pada penguraian kode
menggunakan tabel kode Huffman yang dapat dilakukan adalah melihat setiap rangkaian bit yang
ditemukan dalam string biner dan hasil enkripsi data di dalam tabel kode Huffman. Berikut
merupakan algoritma Huffman dalam mengkompresi data [6].
Contoh 1.
Terdapat citra dengan representasi matriks, tiap piksel dikodekan dengan 8 bit warna, sebagai berikut:
Dari data tersebut akan dilakukan kompresi.
Langkah-langkah pengkodean pada data citra sebagai berikut:
1. Bentuk vektor dari dari data citra yang berupa matriks tersebut yaitu:
Jumlah piksel 16
3. Simpul pohon biner
4. Pembentukan pohon biner
5. Konversi data
6. Penyimpan data
Ukuran: kode Huffman, data warna
Rasio kompresi citra pada contoh 1
Ukuran citra sebelum kompresi: 16 piksel 8 bit warna bit
Ukuran citra setelah kompresi:
Jika dilakukan dekompresi maka file yang dihasilkan akan sama persis dengan file aslinya akan tetapi
ukuran bit dalam citra tersebut menjadi 32 bit dengan rasio kompresi sebanyak 75 %.
3. Metode RLE (Running Length Enconding)
Algoritma RLE (Run Length Encoding) adalah salah satu algoritma yang dapat digunakan untuk melakukan kompresi data sehingga ukuran data yang dihasilkan menjadi lebih rendah dari ukuran sebenarnya. Contoh yang dibahas kali ini adalah mengenai kompresi dan pengembalian data dari sebuah kalimat.
RLE (Run Length Encoding) adalah bentuk paling mudah dari teknik kompresi data lossless dimana sederetan data dengan nilai yang sama secara berurutan akan disimpan menjadi sebuah nilai data dan jumlahnya. Algoritma ini sangat berguna pada data yang memiliki banyak data dengan nilai yang sama secara berurutan seperti file ikon, gambar garis, dan animasi. Algoritma ini tidak cocok diterapkan pada data normal karena akan hal tersebut akan mengakibatkan semakin bertambahnya ukuran data kompresi dibandingkan data awalnya
Langkah-langkah penggunaan algoritma ini adalah
* Tentukan kalimat yang digunakan sebagai data input
Diasumsikan data input adalah sebagai berikut:LLLLLLoooooooooorrrrrrrrrrreeeeeeeeeeemmmmmmm IIIIIIIppppppppppsssssssuuuuuuuuuummmmmmmmm
1. Hitung ukuran data yang digunakan dalam perhitungan sebagai penanda ukuran data sebelum dilakukan kompresi
Dim inputData As Byte() = System.Text.Encoding.[Default].GetBytes(input)
Dim ukuranInputData As UInteger = CUInt(input.Length)
Console.WriteLine("Ukuran input data = " & ukuranInputData)
2. Lakukan proses kompresi data menggunakan algoritma ini
Penjelasan lebih detail tentang fungsi ini dapat dilihat pada penjelasan skrip dibawah ini
Dim KompresiData As Byte() = New Byte(ukuranInputData * (257 / 256)) {}
Dim ukuranKompresiData As Integer = Compress(inputData, KompresiData, ukuranInputData)
* Gunakan fungsi ini untuk melakukan kompresi data
Public Function Compress(input As Byte(), ByRef output As Byte(), ukuranInput As UInteger) As Integer
Dim byte1 As Byte, byte2 As Byte, penanda As Byte
Dim i As UInteger, posisiInput As UInteger, posisiOutput As UInteger, count As UInteger
Dim histogram As UInteger() = New UInteger(255) {}
If ukuranInput < 1 Then
Return 0
End If
For i = 0 To 255
histogram(i) = 0
Next
For i = 0 To ukuranInput - 1
histogram(input(i)) += 1
Next
penanda = 0
For i = 1 To 255
If histogram(i) < histogram(penanda) Then
penanda = CByte(i)
End If
Next
output(0) = penanda
posisiOutput = 1
byte1 = input(0)
posisiInput = 1
count = 1
If ukuranInput >= 2 Then
byte2 = input(posisiInput)
posisiInput += 1
count = 2
Do
If byte1 = byte2 Then
While (posisiInput < ukuranInput) AndAlso (byte1 = byte2) AndAlso (count < 32768)
byte2 = input(posisiInput)
posisiInput += 1
count += 1
End While
If byte1 = byte2 Then
encodeDenganPerulangan(output, posisiOutput, penanda, byte1, count)
If posisiInput < ukuranInput Then
byte1 = input(posisiInput)
posisiInput += 1
count = 1
Else
count = 0
End If
Else
encodeDenganPerulangan(output, posisiOutput, penanda, byte1, count - 1)
byte1 = byte2
count = 1
End If
Else
encodeTanpaPerulangan(output, posisiOutput, penanda, byte1)
byte1 = byte2
count = 1
End If
If posisiInput < ukuranInput Then
byte2 = input(posisiInput)
posisiInput += 1
count = 2
End If
Loop While (posisiInput < ukuranInput) OrElse (count >= 2)
End If
If count = 1 Then
encodeTanpaPerulangan(output, posisiOutput, penanda, byte1)
End If
Return CInt(posisiOutput)
End Function
3. Dapatkan hasil kompresi data dan ukuran data hasil kompresi yang baru
Dim teksKompresiData As String = System.Text.Encoding.[Default].GetString(KompresiData)
4. Lakukan proses pengembalian data kompresi menggunakan algoritma ini
Penjelasan lebih detail tentang fungsi ini dapat dilihat pada penjelasan skrip dibawah ini
Dim PengembalianData As Byte() = New Byte(ukuranInputData - 1) {}
Decompress(KompresiData, PengembalianData, CUInt(ukuranKompresiData))
* Gunakan fungsi ini untuk melakukan pengembalian data kompresi
Public Sub Decompress(input As Byte(), output As Byte(), ukuranInput As UInteger) Dim penanda As Byte, simbol As Byte Dim i As UInteger, posisiInput As UInteger, posisiOutput As UInteger, count As UInteger If ukuranInput < 1 Then Return End If posisiInput = 0 penanda = input(posisiInput) posisiInput += 1 posisiOutput = 0 Do simbol = input(posisiInput) posisiInput += 1 If simbol = penanda Then count = input(posisiInput) posisiInput += 1 If count <= 2 Then For i = 0 To count output(posisiOutput) = penanda posisiOutput += 1 Next Else If Convert.ToBoolean(count And &H80) Then count = ((count And &H7F) << 8) + input(posisiInput) posisiInput += 1 End If simbol = input(posisiInput) posisiInput += 1 For i = 0 To count output(posisiOutput) = simbol posisiOutput += 1 Next End If Else output(posisiOutput) = simbol posisiOutput += 1 End If Loop While posisiInput < ukuranInput End Sub
5. Dapatkan hasil pengembalian data dan ukuran data hasil hasil pengembalian data kompresi yang baru
Dim teksPengembalianData As String = System.Text.Encoding.[Default].GetString(PengembalianData) Dim ukuranPengembalianData As UInteger = CUInt(teksPengembalianData.Length)
6. Hasil Akhir
No comments:
Post a Comment