Latihan:
Lakukan kompresi teks 'ABACCDA' dengan metode Huffman dan Shannon-Fano.
Apa itu kompresi?
Kompresi adalah sebuah cara dalam ilmu komputer untuk memadatkan data sehingga hanya memerlukan ruangan penyimpanan lebih kecil sehingga lebih efisien dalam menyimpannya atau mempersingkat waktu pertukaran data tersebut.
A. Metode Huffman
Metode Huffman disebut Pohon Huffman yang 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.
Pada latihan ini karakter atau stringnya 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.
Kemudian lakukan proses kedua dari proses-proses diatas adalah membuat simpul dan akar dari frekuensi yang terkecil.
Pada akhirnya pohon jadi dan tiap-tiap karakter telah memiliki identitas yang akan digunakan untuk proses encoding.
B. Metode Shannon-Fano
Pada dasarnya cara kerja dari algoritma ShannonFano ini sama persis dengan Huffman. Algoritma ini membentuk sebuah pohon, kemudian mengencodingnya, 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.
Karakteristik Pohon Shannon-Fano
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 aturanaturan 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.
Untuk latihan ini kita menggunakan string 'ABACCDA' maka hasil tabelnya adalah:
Maka akan membentuk pohon faktor seperti berikut ini:
25 Oktober, 2020 - 18:30WIB
0 comments