Huffman Encoding: Pengertian, Cara Kerja, dan Contohnya

Dalam dunia digital, ukuran data sering kali menjadi masalah dalam hal penyimpanan dan transfer data. Karena itu, para ahli terus mengembangkan teknik kompresi data untuk mengurangi ukuran data dan memungkinkan transfer data yang lebih cepat.

Salah satu teknik kompresi yang populer adalah Huffman Encoding.

Di artikel ini kita akan membahas mengenai huffman encoding. Yuk, simak!

Daftar Isi

Pengertian Huffman Encoding

Huffman Encoding adalah teknik kompresi data yang dikembangkan oleh David Huffman pada tahun 1952.

Huffman Encoding: Pengertian, Cara Kerja, dan Contohnya

Teknik ini bekerja dengan cara memetakan karakter dalam data menjadi kode biner dengan panjang yang berbeda-beda, sehingga karakter yang muncul lebih sering diwakili oleh kode biner yang lebih pendek.

Teknik ini didasarkan pada analisis frekuensi karakter dalam data, di mana karakter yang muncul lebih sering akan diwakili oleh kode biner yang lebih pendek dan sebaliknya.

Misalnya, dalam sebuah data terdapat karakter "a" yang muncul 5 kali, karakter "b" yang muncul 3 kali, dan karakter "c" yang muncul 2 kali.

Dalam Huffman Encoding, karakter "a" akan diwakili dengan kode biner yang lebih pendek, seperti 0, sedangkan karakter "b" dan "c" akan diwakili dengan kode biner yang lebih panjang, seperti 10 dan 11. Kode biner ini kemudian digunakan untuk merepresentasikan karakter dalam data.

Kelebihan Huffman Encoding

Huffman Encoding memiliki beberapa kelebihan, di antaranya:

Efisien: Huffman Encoding dapat menghasilkan kompresi data yang efisien, di mana ukuran data yang dikompresi menjadi lebih kecil dibandingkan dengan ukuran data aslinya.
Lossless Compression: Huffman Encoding termasuk dalam kategori lossless compression, di mana data yang telah dikompresi dapat dikembalikan ke bentuk aslinya tanpa kehilangan informasi apapun.
Digunakan pada berbagai jenis data: Huffman Encoding dapat digunakan pada berbagai jenis data, seperti teks, gambar, dan audio.
Mudah diimplementasikan: Huffman Encoding dapat dengan mudah diimplementasikan pada berbagai sistem, karena teknik ini tidak memerlukan sumber daya yang besar.

Kekurangan Huffman Encoding

Huffman Encoding juga memiliki beberapa kekurangan, antara lain:

Huffman Encoding dapat memakan waktu yang lama untuk menghasilkan pohon Huffman yang optimal.
Huffman Encoding kurang efektif pada data yang berukuran kecil atau tidak memiliki pola frekuensi yang jelas.
Huffman Encoding tidak dapat melakukan kompresi data yang mengandung informasi acak atau kompleks.
Huffman Encoding tidak cocok untuk data yang selalu berubah, seperti data sensor atau data streaming.

Implementasi Huffman Encoding

Huffman Encoding memiliki berbagai implementasi, seperti:

Kompresi file teks: Huffman Encoding dapat digunakan untuk mengompresi file teks, di mana karakter yang sering muncul dapat diwakili dengan kode biner yang lebih pendek.
Kompresi gambar: Huffman Encoding digunakan dalam format gambar seperti JPEG dan GIF untuk mengurangi ukuran file gambar.
Kompresi audio: Huffman Encoding digunakan dalam format audio seperti MP3 dan AAC untuk mengurangi ukuran file audio.

Cara Kerja Huffman Encoding

Proses Huffman Encoding dimulai dengan analisis frekuensi karakter dalam data. Kemudian, karakter-karakter ini dikelompokkan berdasarkan frekuensi munculnya, sehingga karakter-karakter yang paling sering muncul ditempatkan pada pohon Huffman dengan jarak kode biner yang lebih pendek, dan karakter-karakter yang lebih jarang muncul ditempatkan pada pohon Huffman dengan jarak kode biner yang lebih panjang.

Pohon Huffman terdiri dari simpul (node) yang terhubung oleh garis, yang mewakili jarak kode biner. Pada akhirnya, setiap karakter akan diwakili oleh kode biner yang unik, sehingga karakter dapat direpresentasikan dalam bentuk kode biner.

Sumber: bournetocode.com

Contoh Implementasi Huffman Encoding

Sebagai contoh kita akan membuat Huffman Encoding untuk string:

String di atas terdapat 15 karakter yang setiap karakternya memiliki 8 bit. Maka total nilai bit untuk string yang belum terkompresi adalah 15 x 8 bits = 120 bits.

Dengan menggunakan teknik Huffman Encoding, kita dapat mengkompresi string tersebut menjadi ukuran yang lebih kecil.

Langkah pertama yakni membuat daftar frekuensi kemunculan karakter-karakter dalam string tersebut. Kemudian urutkan berdasarkan frekuensi dari terkecil ke terbesar, jika ada yang memiliki frekuensi yang sama maka urutan tersebut berdasarkan urutan huruf pada kata yang dimaksud.

Buat setiap karakter yang unik sebagai simpul daun.
Dari daun B dan D kita buat simpul baru BD yang akan menjadi orangtua dari simpul B dan D, kemudian menyisipkannya ke dalam daftar sesuai dengan urutan frekuensinya.

Selanjutnya, kita lakukan hal yang sama secara berulang-ulang sehingga terbentuk satu pohon biner Huffman.

Untuk setiap simpun non-daun, berikan angka 0 di sisi kiri dan angka 1 di sisi kanan.

Dengan menelusuri pohon biner Huffman yang telah dibuat, kita dapat membuat tabel kode Huffman sebagai berikut:

Tanpa menggunakan teknik Huffman Encoding, total ukuran string adalah 120 bits. Setelah dilakukan teknik Huffman ukuran berkurang menjadi 32 + 15 + 28 = 75 bits.

Penutup

Huffman Encoding adalah teknik kompresi data yang efektif dan dapat diterapkan pada berbagai jenis data. Dalam Huffman Encoding, data diolah terlebih dahulu untuk membentuk pohon Huffman, kemudian setiap karakter pada data diberikan kode biner yang unik.

Kode biner untuk setiap karakter didasarkan pada jalur dari pohon Huffman, sehingga karakter-karakter yang sering muncul akan memiliki kode biner yang lebih pendek.

Meskipun Huffman Encoding memiliki kelebihan dalam efektivitas kompresi dan tidak merusak data, namun teknik ini juga memiliki kelemahan seperti memerlukan waktu dan sumber daya komputasi yang cukup besar, tidak efektif untuk data yang hanya terdiri dari beberapa karakter, dan rentan terhadap kesalahan.

Oleh karena itu, sebelum menggunakan Huffman Encoding perlu dipertimbangkan terlebih dahulu karakteristik data dan kebutuhan aplikasi.

Demikianlah penjelasan mengenai pengertian, kelebihan dan kekurangan, serta contoh implementasi dari Huffman Encoding.

Semoga informasi yang disajikan dapat bermanfaat dan menambah khazanah pengetahuan kita.

Salam!

Referensi:

Trivusi