GreedyMenengahFase D–FE1E5

Huffman Coding

Huffman Coding membangun kode biner hemat dengan berulang menggabung dua frekuensi terkecil menjadi satu pohon. Simbol yang sering muncul dapat kode pendek, yang jarang dapat kode panjang. Dasar kompresi seperti ZIP dan JPEG.

Contoh kasus

Kompresi teks atau berkas: huruf yang sering muncul (mis. spasi, e) diberi kode terpendek agar ukuran total mengecil.

Silabus

Huffman Coding memberi kode pendek untuk simbol yang sering muncul dan kode panjang untuk yang jarang, agar total ukuran data mengecil.

Tujuan Belajar

·Memahami hubungan frekuensi simbol dengan panjang kodenya
·Menjelaskan cara menggabung dua frekuensi terkecil jadi pohon
·Menerapkan Huffman untuk mengompresi data teks

Cara Kerja

·Hitung frekuensi kemunculan tiap simbol
·Masukkan tiap simbol sebagai simpul ke priority queue
·Gabung dua simpul berfrekuensi terkecil jadi satu simpul induk
·Ulangi penggabungan sampai tersisa satu pohon
·Baca jalur kiri/kanan sebagai bit 0/1 untuk membentuk kode tiap simbol

Prasyarat

·Pohon biner
·Priority queue

Contoh Nyata

·Kompresi file ZIP agar ukuran unduhan lebih kecil
·Format gambar JPEG memampatkan data foto
·Streaming musik menghemat kuota dengan memampatkan audio

Kompleksitas O(n log n) untuk n simbol