Monthly Archives: January 2016

Tugas Multimedia Algoritma Huffman

Algoritma Huffman

 Kompresi Teks Menggunakan Algoritma Huffman

1.Pengertian

Algoritma Huffman adalah salah satu algoritma kompresi. Algoritma huffman merupakan algoritma yang paling terkenal untuk mengompres teks. Terdapat tiga fase dalam menggunakan algoritma Huffman untuk mengompres sebuah teks, pertama adalah fase pembentukan pohon Huffman, kedua fase encoding dan ketiga fase decoding. Prinsip yang digunakan oleh algoritma Huffman adalah karakter yang sering muncul di -encoding dengan rangkaian bit yang pendek dan karakter yang jarang muncul di-encoding dengan rangkaian bit yang lebih panjang. Teknik kompresi algoritma Huffman mampu memberikan penghematan pemakaian memori sampai 30%. Algoritma Huffman mempunyai kompleksitas O(log n) untuk himpunan dengan karakter.

Algoritma Huffman, yang dibuat oleh seorang mahasiswa MIT bernama David Huffman pada tahun 1952, merupakan salah satu metode paling lama dan paling terkenal dalam kompresi teks. 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 sekumpulancodeword, 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.

2.Pembentukan Pohon Huffman

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.

Langkah-langkah pembentukan pohon Huffman adalah sebagai berikut [3] :

1. Baca semua karakter di dalam teks untuk menghitung frekuensi kemunculan setiap karakter. Setiap karakter penyusun teks dinyatakan sebagai pohon bersimpul tunggal. Setiap simpul di-assign dengan frekuensi kemunculan karakter tersebut.

2. Terapkan strategi algoritma greedy sebagai berikut : gabungkan dua buah pohon yang mempunyai frekuensi terkecil pada sebuah akar. Setelah digabungkan akar tersebut akan mempunyai frekuensi yang merupakan jumlah dari frekuensi dua buah pohon-pohon penyusunnya.

3. Ulangi langkah 2 sampai hanya tersisa satu buah pohon Huffman. Agar pemilihan dua pohon yang akan digabungkan berlangsung cepat, maka semua yang ada selalu terurut menaik berdasarkan frekuensi.

3.Proses Encoding

Encoding adalah cara menyusun string biner dari teks yang ada. Proses encoding untuk satu karakter dimulai dengan membuat pohon Huffman terlebih dahulu. Setelah itu, kode untuk satu karakter dibuat dengan menyusun nama string biner yang dibaca dari akar sampai ke daun pohon Huffman.

Langkah-langkah untuk men-encoding suatu string biner adalah sebagai berikut

1. Tentukan karakter yang akan di-encoding

2. Mulai dari akar, baca setiap bit yang ada pada cabang yang bersesuaian sampai ketemu daun dimana karakter itu berada

3. Ulangi langkah 2 sampai seluruh karakter diencoding

4.Proses Decoding

Decoding merupakan kebalikan dari encodingDecoding berarti menyusun kembali data daristring biner menjadi sebuah karakter kembali.

Langkah-langkah men -decoding suatu string biner dengan menggunakan pohon Huffman adalah sebagai berikut :

1. Baca sebuah bit dari string biner.

2. Mulai dari akar

3. Untuk setiap bit pada langkah 1, lakukan traversal pada cabang yang bersesuaian.

4. Ulangi langkah 1, 2 dan 3 sampai bertemu daun. Kodekan rangkaian bit yang telah dibaca dengan karakter di daun.

5. Ulangi dari langkah 1 sampai semua bit di dalam string habis. Sebagai contoh kita akan men-decoding string biner yang bernilai ”111”

5.Contoh penerapan kompresi teks algoritma huffman pada nama masing-masing.

page huffman

6. Kesimpulan

1. Algoritma Huffman adalah salah satu algoritma kompresi, yang banyak digunakan dalam kompresi teks.

2. Terdapat 3 tahapan dalam menggunakan algoritma Huffman, yaitu:

  • membentuk pohon Huffman
  • melakukan encoding dengan menggunakan pohon Huffman, dan
  • melakukan decoding

3. Algoritma Huffman mempunyai kompleksitas waktu O(n log n).

4. Algoritma Huffman adalah salah satu algoritma yang menggunakan prinsip algoritma greedy dalam penyusunan pohon Huffman

5. Dari hasil pengujian yang dilakukan, algoritma Huffman dapat mengompres teks sebesar 70% jika dibandingkan dengan menggunakan kode ASCII dan sebesar 25,3% jika dibandingkan dengan kita menggunakan 3-bit kode. Untuk dapat lebih melihat dan membuktikan keefektifan, kelebihan dan kelemahan dari algoritma Huffman, perlu diadakannya sebuah penelitian yang bertujuan membandingkan seluruh algoritma kompresi dalam mengompres berbagai data atau file.