Ordinary Huffman coding minimizes expected code length. Real file formats and hardware often add another rule: no codeword may be longer than a fixed limit.
The Package-Merge algorithm solves that constrained problem optimally. It is a beautiful lesson in algorithm design because the compression problem becomes easier after an unexpected reduction to a coin-selection problem.
Quick Read
- Problem: assign prefix-code lengths to n symbols so expected length is minimal and every code length is at most L.
- Foundation: Huffman coding, prefix codes, Kraft’s inequality and canonical Huffman codes.
- Core idea: reduce length-limited coding to a binary coin-collector problem, then repeatedly package equal-denomination items.
- Complexity: the classic algorithm runs in O(nL) time, with linear-space refinements.
- Professional lesson: the output is a set of optimal code lengths; the final bit patterns are usually generated canonically afterward.
1. First learn ordinary Huffman coding
Huffman coding repeatedly combines the two least frequent symbols or subtrees. More frequent symbols tend to receive shorter codes, and the resulting binary prefix code has minimum expected length among unrestricted binary prefix codes for the given frequencies.
But unrestricted Huffman trees can become deep. A format, decoder table, SIMD path or hardware pipeline may impose a maximum code length L. Once that limit appears, ordinary greedy merging no longer directly solves the constrained optimum.
2. Separate code lengths from codewords
A crucial learning move is to stop thinking about actual 0/1 strings at first. Package-Merge determines how long each symbol’s codeword should be. Once a valid multiset of lengths is known, canonical Huffman construction can assign the concrete bit patterns.
This separation makes the optimization cleaner: cost depends on symbol weights and code lengths, not on the arbitrary visual shape of one particular binary tree.
3. Kraft’s inequality is the feasibility rule
For binary prefix-code lengths ℓ1,…,ℓn, Kraft’s inequality requires:
sum(2^(-ℓ_i)) <= 1For a full optimal prefix code, equality can be achieved. Package-Merge uses this binary structure to transform “choose code lengths” into “choose coins whose denominations sum to a target”.
4. The binary coin-collector reduction
For each symbol with weight pi, imagine one item at each allowed depth 1…L. The item’s denomination is a power of two associated with that depth, while its cost is pi. Selecting an item represents paying for one unit of code length for that symbol.
The constrained coding problem can then be reduced to choosing a minimum-cost set of these power-of-two-denomination items that reaches the required total denomination. The number of selected items associated with a symbol becomes its final code length.
The exact reduction is worth studying from a source, but the mental model is already useful: tree-depth optimization becomes structured coin selection.
5. Why “package” and “merge”?
At one denomination level, take the cheapest available items in pairs. Pairing two items of denomination 2−k creates one package of denomination 2−(k−1) whose cost is the sum of the two item costs. That package can compete with native items at the next larger denomination.
Repeated packaging resembles carrying in binary arithmetic. Cheap combinations propagate upward until the target denomination can be met optimally.
6. A small conceptual trace
Suppose four symbols have weights 1, 2, 4 and 8, and the maximum length is three. Instead of immediately drawing a tree, create three depth-level copies of each weight. At the deepest level, sort by cost and pair the cheapest two items into packages. Merge those packages with the next-level items, sort again, and continue.
For learning, do not rush to a full implementation. Use labelled cards showing symbol, depth, denomination, cost. Physically pair cards and carry packages to the next level. The binary accounting becomes visible.
7. From selected packages back to lengths
Packages remember which lower-level items they contain. After the optimal top-level selection is determined, unpack recursively. Count how many selected level-items belong to each original symbol. That count determines its optimal length.
This is an important algorithm pattern: compress many local choices into packages for optimization, then backtrack through package provenance to reconstruct the solution.
8. Why ordinary Huffman can violate the limit
If symbol frequencies are highly skewed, ordinary Huffman coding may create a long chain for very rare symbols. Simply truncating those lengths destroys the prefix-code constraint. Simply clipping and renormalizing usually destroys optimality.
Package-Merge solves the constrained optimization problem directly rather than repairing an unrestricted solution after the fact.
9. Canonical Huffman codes come afterward
Many practical formats store code lengths rather than explicit tree shapes. Given valid code lengths, a canonical assignment sorts symbols by length and symbol order, then assigns consecutive bit patterns in a deterministic way.
This separation is professionally useful: one algorithm optimizes lengths, while another deterministic procedure assigns actual codes.
10. Practical connection: DEFLATE-style constraints
The DEFLATE specification defines Huffman-coded blocks with bounded code lengths; for the literal/length and distance alphabets, dynamic code lengths are represented within the format’s stated limits. Package-Merge is one principled way an encoder can solve a length-limited Huffman problem, although a format specification does not require every implementation to use the same construction algorithm.
That distinction matters: a file format defines what outputs are valid; an encoder algorithm chooses how to produce a good valid output.
11. Complexity
The Larmore–Hirschberg result gives an O(nL)-time method for n symbols and maximum code length L, with an O(n)-space refinement. In practice, constants, sorting strategy, repeated weights and memory layout also matter.
Professional analysis should state whether the input weights are already sorted. Sorting can add its own O(n log n) cost if it is not absorbed elsewhere in the pipeline.
12. Common mistakes
- Using ordinary Huffman and simply clipping lengths that exceed L.
- Confusing symbol weights with binary denominations in the coin reduction.
- Losing package provenance and therefore being unable to reconstruct code lengths.
- Treating code lengths and concrete bit patterns as the same subproblem.
- Ignoring impossible parameter choices such as too many symbols for the allowed depth.
- Assuming every compression format uses Package-Merge internally.
- Forgetting deterministic tie handling when reproducible encoders are required.
13. Feasibility checks before optimization
A binary code with maximum length L can represent at most 2L positive-length codewords. If n exceeds that capacity, no valid complete assignment exists. Reject impossible instances before expensive work.
Also validate weights: negative frequencies or costs do not match the intended coding model. Zero-frequency symbols need a clearly defined policy because file formats may still require or omit them differently.
14. Verification tests
- Equal weights, where many optimal trees tie.
- Highly skewed weights that force the length bound to matter.
- L large enough that ordinary Huffman is already valid.
- L at the feasibility boundary.
- Random small alphabets checked against exhaustive enumeration of valid length multisets.
- Canonical reconstruction followed by a prefix-free verification.
For small n and L, exhaustive search is slow but invaluable as a truth oracle. It can confirm that the Package-Merge cost really is minimal.
15. Predict → Run → Investigate → Modify → Make
- Predict: decide whether an unrestricted Huffman tree will violate a chosen depth limit.
- Run: trace one package level using cards or a table.
- Investigate: unpack a selected package and explain which code lengths it contributes to.
- Modify: change one symbol weight or the maximum depth and predict which packages change.
- Make: implement package tracking, then canonical code generation and exhaustive small-case tests.
16. Beginner → professional pathway
- Beginner: build ordinary Huffman trees and read prefix codes.
- Foundation: understand Kraft’s inequality and why maximum depth can invalidate unrestricted Huffman output.
- Intermediate: perform package-and-merge steps by hand and reconstruct code lengths.
- Advanced: derive the binary coin-collector reduction and analyze O(nL) time.
- Professional: implement deterministic tie rules, validate feasibility, generate canonical codes, compare against exhaustive truth cases, and separate format requirements from encoder strategy.
Learning Hall Boundary
This article owns Package-Merge as a learning object for optimal length-limited binary prefix coding, the coin-collector reduction, package provenance and reconstruction of bounded Huffman code lengths. It complements existing compression articles such as LZW and asymmetric numeral systems. It does not replace MindOS, Bolt or Student/Studying Interface canonical jobs and contains no proprietary eduKateAI implementation detail.
Sources and further reading
- L. L. Larmore & D. S. Hirschberg, A Fast Algorithm for Optimal Length-Limited Huffman Codes, Journal of the ACM, 1990.
- RFC Editor, RFC 1951: DEFLATE Compressed Data Format Specification.
- Michael B. Baer, D-ary Bounded-Length Huffman Coding, IEEE ISIT 2007.
- MIT CSAIL bibliography entry for the Larmore–Hirschberg JACM paper: Journal of the ACM Bibliography.
- Sentance, Waite & Kallia, Teachers’ Experiences of Using PRIMM to Teach Programming in School.
Professional rule: you understand Package-Merge when you can explain why the depth constraint changes the optimization problem, trace the coin-collector reduction, reconstruct optimal code lengths from packages and independently verify the resulting prefix code.
