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.

Example use case

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

Syllabus

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

Objectives

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

How It Works

·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

Prerequisites

·Pohon biner
·Priority queue

Real-World Uses

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

Complexity O(n log n) untuk n simbol