http://www.gunadarma.ac.id

Rijsa fitriani

  " Kompresi File "

File compression adalah sebuah proses dimana file-file Anda dijadikan satu paket atau dikecilkan ukurannya untuk mengurangi ukuran file. ... Yang paling simple adalah mengurangi ukuran sebuah file. Dengan mengompresi kita dapat menghemat banyak ruang  di memori . Dalam kompresi file memiliki 2 tokoh yang menjabarkan metodenya , yaitu Hufman dan Shanon-fano.

1. Metode  Algoritma menurut Hufman

 Algoritma Huffman Algoritma Huffman, yang dibuat oleh seorang mahasiswa MIT bernama David Huffman pada tahun 1952, merupakan salah satu metode lama yang sering banyak dipakai.

Algoritma Huffman menggunakan prinsip pengkodean yang mirip dengan kode Morse, yaitu tiap karakter (simbol) dikodekan hanya dengan rangkaian beberapa bit, dimana karakter yang sering muncul dikodekan dengan rangkaian bit yang pendek dan karakter yang jarang muncul dikodekan.dengan rangkaian bit yang lebih panjang.  

Berdasarkan tipe peta kode yang digunakan untuk mengubah pesan awal (isi data yang diinputkan) menjadi sekumpulan codeword, algoritma Huffman termasuk kedalam kelas algoritma yang menggunakan metode statik . Metoda statik adalah metoda yang selalu menggunakan peta kode yang sama, metoda ini membutuhkan dua fase (two-pass): fase pertama untuk menghitung probabilitas kemunculan tiap simbol dan menentukan peta kodenya, dan fase kedua untuk mengubah pesan menjadi kumpulan kode yang akan di taransmisikan. Sedangkan berdasarkan teknik pengkodean simbol yang digunakan, algoritma Huffman menggunakan metode symbolwise. 

Metoda symbolwise adalah metode yang menghitung peluang kemunculan dari setiap simbol dalam satu waktu, dimana simbol yang lebih sering muncul diberi kode lebih pendek dibandingkan simbol yang jarang muncul. 

 Kode Huffman pada dasarnya merupakan kode prefiks (prefix code). Kode prefiks adalah himpunan yang berisi sekumpulan kode biner, dimana pada kode prefik ini tidak ada kode biner yang menjadi awal bagi kode biner yang lain. Kode prefiks biasanya direpresentasikan sebagai pohon biner yang diberikan nilai atau label. Untuk cabang kiri pada pohon 

biner diberi label 0, sedangkan pada cabang kanan pada pohon biner diberi label 1. Rangkaian bit yang terbentuk pada setiap lintasan dari akar ke daun merupakan kode prefiks untuk karakter yang berpadanan. Pohon biner ini biasa disebut pohon Huffman. 

#Berikut contohnya

“ABACCDA” membutuhkan representasi 7 × 8 bit = 56 bit (7 byte)

A = 01000001

 B = 01000010 

A = 01000001

 C = 01000011

 C = 01000011

 D = 01000100

 A = 01000001

Pada string di atas, frekuensi kemunculan A = 3, B = 1, C = 2, dan D = 1,  

2.Metode  Algoritma menurut Shanon-fano

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 Sahnon-Fano termasuk algoritma statistik karena menggunakan data statistik dari kemunculan huruf dalam suatu file. 

a). 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 . ) 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.

• Metode Shannon memilih kode awalan di mana simbol sumber$$ {\ displaystyle i} diberi panjang codeword$$ {\ displaystyle l_ {i} = \ lceil - \ log _ {2} p_ {i} \ rceil} . Salah satu cara umum untuk memilih codeword menggunakan ekspansi biner dari probabilitas kumulatif. Metode ini diusulkan dalam " A Mathematical Theory of Communication " Shannon (1948), artikelnya memperkenalkan bidang teori informasi .
• Metode Fano membagi simbol sumber menjadi dua set ("0" dan "1") dengan probabilitas sedekat mungkin dengan 1/2. Kemudian set tersebut terbagi menjadi dua, dan seterusnya, hingga setiap set hanya berisi satu simbol. Kata sandi untuk simbol itu adalah string "0" dan "1" yang mencatat pada setengah bagian mana simbol itu jatuh. Metode ini diusulkan dalam laporan teknis selanjutnya oleh Fano (1949).

Kode Shannon-Fano adalah suboptimal dalam arti bahwa mereka tidak selalu mencapai panjang codeword yang diharapkan serendah mungkin, seperti yang dilakukan pengkodean Huffman . Namun, kode Shannon – Fano memiliki panjang codeword yang diharapkan dalam 1 bit dari optimal. Metode Fano biasanya menghasilkan pengkodean dengan panjang yang diharapkan lebih pendek daripada metode Shannon. Namun, metode Shannon lebih mudah dianalisis secara teoritis.