Kode Huffman

Posted on

Definisi Pohon

  • Pohon didefinisikan sebagai suatu graf tak berarah terhubungkan (connected undirected graph) yang tidak mengandung sirkuit
  • Dua sifat penting yang dapat digunakan untuk menentukan suatu pohon yaitu terhubung dan tidak mengandung sirkuit

Pohon dan Bukan Pohon

Terminologi dalam Pohon

  • Simpul E, F, dan G disebut anak (child) dari simpul D
  • Simpul D disebut orang tua (parent)
  • B dan C disebut sibling atau saudara kandung
  • Daun adalah simpul paling ujung dalam sebuah pohon. Simpul B, E, F, dan G adalah daun.
  • Aras maksimum dari suatu pohon disebut tinggi atau kedalaman pohon tersebut. Pada pohon disamping aras mak = 3

Pohon Biner

  • Pohon berakar yang setiap simpul cabangnya Mempunyai paling banyak n buah anak disebut pohon n-ary.
  • Jika n sama dengan 2 pohon tersebut disebut pohon biner (binary tree).
  • Untuk membuat pohon biner, terdapat aturan dalam penempatan simpulnya.
  • Berikut ini merupakan algoritma penempatan sebuah simpul dalam pohon biner : “Simpul yang berisi informasi yang nilainya lebih besar dari simpul diatasnya akan ditempatkan sebagai cabang kanan dan jika lebih kecil akan ditempatkan di cabang kiri.

 

Kode Huffman

  • Salah satu algoritma yang biasa digunakan dalam kompresi data adalah algoritma pengkodean Huffman
  • Pada Algoritma pengkodean Huffman simbol yang mempunyai probabilitas paling besar diberi kode paling pendek (jumlah bit kode sedikit) dan simbol dengan probabilitas paling kecil akan memperoleh kode paling panjang (jumlah bit kode banyak).
  • Kode tersebut diperoleh dengan cara memyusun sebuah pohon Huffman untuk masing-masing simbol berdasarkan nilai probabilitasnya

Algoritma Pohon Huffman

  • Berdasarkan daftar simbol dan probabilitas, buatlah dua buah node dengan frekuensi paling kecil.
  • Buatlah node parent dari node tersebut dengan bobot parent merupakan jumlah dari probabilitas kedua node anak tersebut.
  • Masukkan node parent tersebut beserta bobotnya ke dalam daftar, dan kemudian kedua node anak beserta probabilitasnya dihapus dari daftar.
  • Salah satu node anak dijadikan jalur (dilihat dari node parent) untuk pengkodean 0 sedangkan lainnya digunakan untuk jalur pengkodean 1.

Contoh

  • Buatlah kode Huffman untuk “SCIENCE”

Solusi

  • Buatllah daftar frekuensi kemunculan simbol-simbol dalam data tersebut.
  • Urutkan berdsarkan frekuensi dari terkecil ke terbesar, jika ada yang frekuensinya sama maka urutan berdasarkan urutan huruf pada kata yang dimaksud

  • Berdasarkan daftar frekuensi tersebut, kita buat daun-daun yang mewakili setiap simbol serta mengasosiasikan daun tersebut dengan frekuensi kemunculan simbol.

  • Dari daun S dan I kita buat simpul baru SI yang akan menjadi orangtua dari sImpul S dan I dan menyisipkannya ke dalam daftar sesuai dengan urutan frekuensinya.

  • Selanjutnya, kita lakukan hal yang sama secara berulang-ulang sehingga terbentuk satu pohon biner Huffman.
  • Dengan menelusuri pohon biner Huffman yang telah dibuat, kita dapat membuat tabel kode Huffman sebagai berikut:

  • Sehingga kode Huffman untuk string “SCIENCE” adalah 1100111110000110. ‘
  • Dengan menggunakan kode ASCII memori yang dipakai adalah sebesar 56 bit diperoleh dari 1 huruf kode ACSII terdiri dari 8 bit dan jumlah huruf SCIENCE terdiri dari 7 bit maka jika pakai kode ACSII sebesar 8 x 7 = 56 bit, sedangkan dengan menggunakan kode Huffman memori yang dipakai adalah sebesar 16 bit.

Latihan Soal:

Buatlah kode Huffman untuk “TELKOMSEL”

 

Untuk lebih jelasnya silahkan download link berikut ini:

 

 


 

Terimakasih atas perhatiannya.

 

Untuk materi sebelumnya tentang Short Path, silahkan Klik Disini.

Untuk materi selanjutnya tentang Soal Formatif UAS, silahkan Klik Disini.

 

 

Tinggalkan Balasan

Isikan data di bawah atau klik salah satu ikon untuk log in:

Logo WordPress.com

You are commenting using your WordPress.com account. Logout /  Ubah )

Foto Google+

You are commenting using your Google+ account. Logout /  Ubah )

Gambar Twitter

You are commenting using your Twitter account. Logout /  Ubah )

Foto Facebook

You are commenting using your Facebook account. Logout /  Ubah )

Connecting to %s