MATH3411 Chap.3 Compression Using Huffman Trees
Compression Using Huffman Trees
Compression assigns shorter codewords to more likely symbols while preserving unique recovery. This chapter separates uniquely decodable codes from instantaneous prefix codes, uses Kraft-McMillan to test feasible length lists, and builds optimal prefix trees with Huffman's algorithm. It also extends coding to radix-r alphabets, blocks and stationary Markov sources, where context can change the best code.
Three objects must remain distinct: a proposed set of codewords, the list of their lengths and the probability distribution being encoded. Prefix testing concerns the actual words, Kraft-McMillan constrains possible lengths, and expected length pairs those lengths with source probabilities. Huffman's merge algorithm links the three by placing low-probability symbols deeper in a prefix tree.
Ties can change literal bit labels while preserving the same optimal cost. A defensible solution records each merge, reads leaf depths, computes the probability-weighted average and checks it against entropy in the same radix. Source extensions can lower overhead per original symbol, but the block rate must be divided by block length and weighed against a larger codebook.
What this chapter covers
- 01
Unique decodability
- 02
Instantaneous prefix codes
- 03
Kraft-McMillan inequality
- 04
Binary Huffman algorithm
- 05
Radix-r Huffman coding
- 06
Source extensions
- 07
Stationary Markov sources
Worked example · free
Merge Probabilities into a Huffman Tree
- +1Merge 0.1 and 0.2 to form 0.3.
- +1Merge the two 0.3 nodes to form 0.6.
- +1Join 0.4 and 0.6 and read leaf words.
- +1Compute expected length 1.9 bits per symbol.
Key terms
- Uniquely decodable code
- A code whose concatenations have only one parsing into codewords.
- Prefix code
- A code in which no codeword begins another codeword.
- Expected length
- The probability-weighted average number of code symbols used per source symbol.
Compression Using Huffman Trees FAQ
Does a failed prefix test prove ambiguity?
No. It proves the code is not instantaneous, but a delayed decoder may still recover every concatenation uniquely. To prove ambiguity, exhibit one finite encoded string with two distinct codeword parsings.
What does the Kraft sum test?
It tests whether a list of lengths can belong to a uniquely decodable code and guarantees an instantaneous construction when the sum is at most one.
Why use source extensions?
Coding blocks creates finer probability combinations and can reduce integer-length overhead per original source symbol, at the cost of a larger codebook. Divide expected block length by the block size before comparing rates.
Exam move
Organise compression revision around three decisions: whether decoding is unique, whether it is immediate, and whether the expected length is optimal for the stated source. Begin with short codeword sets and test the prefix property directly. When one word begins another, conclude only that instantaneous decoding fails; search for an actual double parsing before claiming ambiguity.
Use a suffix procedure when no short counterexample is visible. Separate this word-level analysis from Kraft-McMillan, which first tests whether a length list is feasible. Calculate the Kraft sum in the correct radix before drawing a tree, and interpret equality or unused capacity without assuming that a particular supplied word set is well designed. For Huffman work, keep a complete merge ledger.
At every row circle or otherwise identify the two smallest weights, insert their sum in order, and preserve tied alternatives rather than forcing one left-right convention. Draw the tree from the ledger, assign branch labels consistently and read each codeword from root to leaf. Calculate expected length by pairing each original probability with its leaf depth; do not weight internal nodes as if they were source symbols.
Compare the result with entropy using the same logarithm base, and state the unit per source symbol. Decode one concatenated stream by returning to the root after each leaf. That exercise verifies the prefix structure and often exposes a copied branch label. Extend the method to blocks only after the one-symbol case is secure.
List ordered block probabilities for a memoryless source, build the new code, and divide expected block length by the block size before comparing rates. For a Markov source, condition on the current state instead of multiplying marginal probabilities blindly.
Keep an error ledger for merging a nonminimal pair, reading bits from leaf to root, pairing a probability with the wrong depth, using a binary Kraft sum for another radix, or treating non-prefix as automatically ambiguous. Timed practice should finish with a four-part written answer: merge history, explicit code, expected-length arithmetic and one optimality or feasibility check.
Finally, explain why compression removes predictable redundancy while Chapter 2 deliberately added structured redundancy. That contrast is a frequent conceptual bridge and makes the two coding goals easier to distinguish when a question changes context midstream.
Working through Compression Using Huffman Trees in MATH3411? Sia is AskSia’s AI Mathematics tutor — ask any MATH3411 Compression Using Huffman Trees question and get a clear, step-by-step explanation grounded in how MATH3411 is taught and assessed. Read this chapter free, then take your hardest questions to Sia.
