KOMPRESI DENGAN ALGORITMA SHANNON-FANO

Claude Shannon dan Robert Fano adalah orang yang mengembangkan algoritma ini sehingga gabungan dari nama mereka yang menjadi nama algoritma yang mereka kembangkan.

Algoritma Shannon-Fano ini merupakan metode kompresi lossless, yaitu kompresi data yang tidak merusak hasil kompresi dan dapat dikembalikan pada keadaan semula.

Untuk mendapatkan kode dari setiap karakter, dengan menggunakan frekuensi kemunculan setiap karakter pada teks. Panjang kode ditentukan oleh frekuensi kemunculan karakter. Kode bit untuk karakter yang sering muncul akan lebih pendek daripada karakter yang tidak sering muncul.

Baca Juga Haar Wavelet Transform

KOMPRESI SHANNON-FANO

Contoh :

Teks yang akan dikompres : XPXWWXZZYWWYXXYXZWYWZZW

1.       Hitung semua jumlah karakter yang ada pada teks dan perhatikan        banyaknya karakter pada teks

          Dari contoh diatas ada 23 jumlah karakter dan  ada 5 karakter yaitu

          X P W Z Y

2.       Lakukan pengurutan descending berdasarkan frekuensi kemunculan karakter. Berikut pengurutan untuk Shannon-Fano

Karakter	W	X	Z	Y	P
Frekuensi	7	6	5	4	1

Sedangkan pengurutan frekuensi kemunculan karakter untuk Huffman dilakukan secara ascending.

Karakter	P	Y	Z	X	W
Frekuensi	1	4	5	6	7

                                                                                                                      

3.       3. Pisahkan karakter yang sudah disusun dengan descending menjadi 2 bagian yaitu kiri dan kanan dengan perbedaan yang tidak terlalu besar antara bagian yang    satu dengan yang lain.

Sedangkan pada algoritma Huffman, gabungkan 2 karakter yang sudah disusun ascending dengan frekuensi kemunculan terkecil.

4.  Buat pohon Shannon-Fano dari hasil yang didapat pada langkah 3 dengan memberi tanda kode 0 untuk bagian kiri dan kode 1 untuk bagian kanan.

Untuk Huffman buat pohon bitnya sesuai hasil penggabungan karakter diatas dengan pemberian kodenya sama yaitu kode 0 untuk bagian kiri dan kode 1 untuk bagian kanan.

5. Gantikan  kode karakter dari pohon Shannon-Fano yang sudah dibentuk

Kode bit Shannon-Fano berbeda dengan Huffman maka sudah pasti hasil kompresinya pun akan berbeda. Untuk lebih jelasnya perhatikan table berikut.

Teks yang akan dikompresi : XPXWWXZZYWWYXXYXZWYWZZW
Hasil kompresi teks Shannon-Fano :
01 111 01 00 00 01 10 10 110 00 00 110 01 01 110 01 10 00 110 00 10 10 00

Teks sebelum dikompres : 23*8 bit = 184 bit
Setelah dikompres : (7*2)+(6*2)+(5*2)+(4*3)+(1*3) = 51 bit

DEKOMPRESI SHANNON-FANO

Kode bit yang akan di dekompresi:

 01 111 01 00 00 01 10 10 110 00 00 110 01 01 110 01 10 00 110 00 10 10 00

Caranya : Baca serangkaian kode bit nya dari yang paling kiri dan cocokkan dengan kode yang terbentuk dari pohon Shannon-Fano

Maka, berdasarkan pembacaan kode tersebut dekompresi dari
01 111 01 00 00 01 10 10 110 00 00 110 01 01 110 01 10 00 110 00 10 10 00
X    P   X    W W  X   Z  Z   Y    W  W   Y   X   X    Y   X   Z  W    Y   W   Z   Z   W

Ø Perbedaan pertama yang tampak dari algoritma Shannon-Fano dan Huffman

Adalah dari pengurutan frekuensi kemunculan karakternya.

Ø Perbedaan kedua dari algoritma ini adalah dari cara pembuatan pohon biner nya.

Ø Hasil kompresi dari Shannon-Fano dan Huffman berbeda.

Ø Dari beberapa modul atau jurnal yang kami baca Shannon-Fano lebih cepat mengompres dan dekompres data karena proses pembuatan pohon biner nya yang lebih singkat. Namun kelemahannya dalam pembuatan pohonnya kurang efektif.

Autor:

  KHAIRUL HAWANI   

LAMTIUR PASARIBU

M. NAUFAL SIREGAR 

RONI NASUTION