Huffman Code (ฮัฟฟ์มันโค้ด)
Huffman Code = Optimal Prefix Code ประเภทหนึ่ง ใช้ทั่วไปสำหรับ Lossless Data Compression
พัฒนาโดย David A. Huffman (MIT Sc.D. Student) ตีพิมพ์ 1952 "A Method for the Construction of Minimum-Redundancy Codes"
Output = Variable-Length Code Table สำหรับ Encode Source Symbols (เช่น Character ในไฟล์)
สร้างจาก Estimated Probability/Frequency (Weight) ของแต่ละ Symbol
Symbol ที่ Common → ใช้ Bits น้อยกว่า → Entropy Encoding Principle
Implement ได้ Efficient: O(n) Time ถ้า Weights Sorted แล้ว
Entropy (เอนโทรปี / ความไม่แน่นอน)
ใน Information Theory: Shannon's Source Coding Theorem (Noiseless Coding Theorem)
- กำหนดขีดจำกัด Data Compression
- ให้ความหมาย Operational ของ Shannon Entropy
Theorem: ไม่สามารถ Compress ได้ให้ Code Rate (Avg Bits/Symbol) < Shannon Entropy ของ Source โดยไม่สูญเสียข้อมูล
แต่เข้าใกล้ Entropy ได้ Arbitrarily Close ด้วย Probability of Loss → 0
Information Entropy Definition
Average Rate ที่ Information ถูกผลิตโดย Stochastic Data Source
คำนวณ Entropy ของ Random Variable
Random Variable X มี k ∈ K Discrete States, Probability Distribution p(k)
H(X) = - Σ_{k∈K} p(k) · log₂(p(k))
Negative Sum ของ Probability × Log Probability
Base-2 Log → Units = Bits (Natural Log → Nats)
Properties
- Minimum Entropy (0): Single Event p=1.0 (Certainty)
- Maximum Entropy: All Events Equally Likely (Uniform Distribution)
- Entropy = Lower Bound ของ Average Bits ต่อ Symbol สำหรับ Encoding จาก Distribution P
ความสัมพันธ์ Huffman ↔ Entropy
- Huffman Code ให้ Average Code Length L ใกล้เคียง Entropy H
- H ≤ L < H + 1 (สำหรับ Binary Huffman)
- Gap = Redundancy ของ Code
