ปัญหา
Huffman Construction ทั่วไป ไม่จำกัด Height/Depth ถ้าจำกัด → ไม่ "Optimal" แล้ว (แต่ Depth สูงสุดถูก Bound โดย Fibonacci Series)
ทำไมต้องจำกัด Depth?
Fast Huffman Decoders ใช้ Lookup Tables
Table Size = 1 << TreeDepth (2Depth)
เพื่อ Speed + Memory Management: Limit = 8 KB (Fit L1 Cache) → 4K Cells (2 bytes/cell) → Max Depth = 12 bits
12 bits สำหรับ Literals สั้นเกินไปสำหรับ Optimal Huffman → ต้องมี Depth-Limited Construction
Literature Review
Depth-Limited Huffman Trees เรียนรู้มาตั้งแต่ 1960s → Literature เยอะมาก
Algorithm หลัก:
- Package-Merge Algorithm (Larmore & Hirschberg, 1990): O(n L) Time, O(n) Space - Optimal & Practical
- Dynamic Programming Approaches
- Heuristics (สำหรับ Real-time)
สรุป
Height-Limited Huffman = Practical Constraint สำหรับ Fast Decoding (Lookup Tables)
Trade-off: Compression Ratio ↔ Decoding Speed/Memory
Package-Merge = Standard Solution ที่ Optimal และมีประสิทธิภาพ
