Unit 9: Huffman Coding and Data Compression - Subjective Questions

Data compression is the process of representing information using fewer bits than its original representation.

• Lossless compression: The original data can be reconstructed exactly from the compressed data. It is used when losing information is unacceptable. Examples include Huffman coding, ZIP, PNG, and FLAC.
• Lossy compression: Some information is permanently discarded to achieve a higher compression ratio. The reconstructed data is an approximation of the original. Examples include JPEG, MP3, and MPEG.

Key difference: Lossless compression preserves every symbol, whereas lossy compression trades accuracy or quality for a smaller size. Huffman coding is a lossless compression technique.

A prefix code is a set of codewords in which no codeword is a prefix of another codeword.

For example, the set is prefix-free. However, is not prefix-free because is a prefix of .

The prefix property is important because:

• It permits instantaneous decoding without separators.
• A decoder can determine the end of each codeword as soon as it reaches a leaf in the coding tree.
• It prevents ambiguity during left-to-right decoding.

In a Huffman tree, symbols occur only at leaves. Therefore, the path to one symbol cannot be the prefix of the path to another symbol.

The binary Huffman algorithm constructs an optimal prefix code using the following greedy procedure:

1. Create one leaf node for every symbol and label it with the symbol's frequency.
2. Insert all leaf nodes into a min-priority queue.
3. Remove the two nodes having the smallest frequencies.
4. Create an internal node whose frequency is the sum of the two removed frequencies.
5. Make the removed nodes the children of the new node.
6. Insert the new node back into the priority queue.
7. Repeat until only one node remains. This node becomes the root.
8. Label one edge from each internal node as and the other as .

The codeword for a symbol is the sequence of edge labels on the root-to-leaf path for that symbol.

Arrange the frequencies in increasing order and repeatedly combine the two smallest values:

One valid assignment is:

The weighted path length is:

Since the total frequency is , the average code length is:

Different assignments of and may produce different codewords, but the code lengths and compression efficiency remain the same.

Encoding:

• Obtain the codeword of each input symbol from the Huffman tree or a lookup table.
• Replace every symbol in the input by its corresponding codeword.
• Concatenate all codewords to form the compressed bitstream.

Decoding:

1. Begin at the root of the Huffman tree.
2. Read the next bit.
3. Follow the left child for and the right child for , according to the selected convention.
4. When a leaf is reached, output its symbol.
5. Return to the root and continue until the bitstream ends or the required number of symbols has been decoded.

Decoding is unambiguous because Huffman codes satisfy the prefix property.

Huffman coding is a greedy algorithm because it repeatedly combines the two least frequent symbols or subtrees.

Greedy-choice property: In some optimal prefix tree, the two symbols with the smallest frequencies can be placed as sibling leaves at the greatest depth. Thus, combining them first does not eliminate all optimal solutions.

Optimal substructure: Suppose the two least frequent symbols and are replaced by a combined pseudo-symbol with frequency

An optimal code for the reduced alphabet can be expanded by replacing with an internal node having and as children. If the reduced tree were not optimal, replacing it with a better reduced tree would also improve the original tree, producing a contradiction.

These properties establish that repeated greedy merging produces an optimal binary prefix code.

Fixed-length coding:

• Every symbol uses the same number of bits.
• For an alphabet containing symbols, each symbol generally needs bits.
• Encoding and random access are simple.
• Symbol probabilities are not exploited.

Variable-length coding:

• Different symbols may use different numbers of bits.
• Frequent symbols receive shorter codewords, while rare symbols receive longer codewords.
• Prefix-free codes enable unambiguous decoding.
• Compression is usually better when symbol frequencies are unequal.

Huffman coding is a variable-length method. Its benefit over fixed-length coding depends on the probability distribution and the cost of storing the codebook.

A binary Huffman tree has the following properties:

• Every source symbol is stored at a leaf.
• Every internal node has exactly two children, except for the special one-symbol case.
• The frequency of an internal node equals the sum of its children's frequencies.
• The root frequency equals the total frequency of all symbols.
• Each left or right edge contributes one bit to a codeword.
• The length of the codeword for symbol equals the depth of its leaf.

For frequencies , the total encoded size is the weighted external path length:

Huffman coding minimizes this quantity among all binary prefix trees for the given frequencies.

Let be the number of distinct symbols.

• Creating the initial nodes requires space.
• Building a binary min-heap can be performed in time.
• There are merge operations.
• Each merge performs two minimum extractions and one insertion, each costing .

Therefore, the usual construction time is:

The tree, heap, and code table require auxiliary space. If frequencies are already sorted, two queues can be used to construct the tree in time. Encoding then takes time proportional to the number of output bits, while decoding takes time proportional to the number of bits read.

For symbols with probabilities , the source entropy is:

Entropy represents the theoretical lower bound on the average number of bits needed per symbol by a lossless binary code under the assumed source model.

If is the average codeword length of a binary Huffman code, then:

The redundancy of the code is . Huffman coding is optimal among symbol-by-symbol binary prefix codes, but it may not attain entropy exactly because codeword lengths must be integers. Coding blocks of symbols or using arithmetic coding can approach entropy more closely.

A data compression problem should consider:

• Source model: Determine whether individual symbols, symbol pairs, runs, or larger contexts will be encoded.
• Frequency estimation: Obtain accurate probabilities from the current data or from a representative training source.
• Loss requirement: Decide whether compression must be lossless or may be lossy.
• Compression ratio: Compare compressed size, including metadata, with original size.
• Speed and memory: Evaluate construction, encoding, decoding, and storage costs.
• Codebook transmission: A decoder must receive or reconstruct the coding model.
• Streaming requirements: Decide whether the full input is available before encoding.
• Error sensitivity: A corrupted variable-length bitstream may cause loss of synchronization.

The most suitable technique depends on the characteristics and operational requirements of the data.

When two or more nodes have equal frequencies, the algorithm may choose any of them as long as it always selects two nodes having minimum frequency.

Consequences of ties include:

• Different implementations may produce different tree shapes.
• The actual bit patterns assigned to symbols may differ.
• Symbols tied in frequency may receive different code lengths in some instances.
• All correctly constructed alternatives still have the same minimum weighted path length.

A deterministic implementation can break ties using symbol order, node creation order, or a specified left-child rule. Deterministic tie-breaking is important when the encoder and decoder independently reconstruct the tree from the same frequency table.

Static Huffman coding:

• Frequencies are known or collected before encoding.
• The Huffman tree remains fixed while the data is encoded.
• It commonly requires two passes: one for frequencies and one for encoding.
• The frequency table or tree must normally be stored with the compressed data.

Adaptive Huffman coding:

• The tree changes as symbols are processed.
• Initial frequencies need not be known.
• Encoding can be performed in one pass and is suitable for streams.
• Encoder and decoder must update their trees identically after each symbol.
• Tree maintenance introduces computational complexity.

Static coding can be more efficient when a reliable distribution is available, whereas adaptive coding can respond to a changing source.

A canonical Huffman code is a standardized representation determined by the lengths of the symbol codewords rather than by the complete Huffman tree.

To construct it:

1. Sort symbols by increasing codeword length.
2. For equal lengths, sort symbols by a fixed symbol order.
3. Assign the all-zero codeword to the first symbol.
4. For each next symbol, increment the preceding codeword as a binary number.
5. If the next codeword is longer, left-shift the incremented value by the difference in lengths.

Canonical codes preserve the code lengths and average encoded size of the original Huffman code. Their main advantages are compact codebook storage, deterministic reconstruction, and efficient table-based decoding.

Important limitations of Huffman coding are:

• Codeword lengths are integral, so the average length may remain above entropy.
• A code tree or frequency description must be included in the compressed representation.
• Metadata overhead can make small files larger rather than smaller.
• Basic Huffman coding treats symbols independently and does not exploit contextual relationships.
• It generally cannot assign fewer than one bit to each encoded source symbol, even when one symbol is overwhelmingly probable.
• Corruption or loss of a bit can disrupt the boundaries of many later codewords.
• A static implementation may require two passes over the input.

These limitations can be reduced using block coding, context modeling, canonical representations, or arithmetic/range coding.

In a -ary Huffman code, each internal node has children and each code symbol belongs to an alphabet of size .

The algorithm repeatedly removes the nodes of minimum frequency, combines them into one node, and reinserts the combined node. For a full -ary tree with leaves, the following condition must hold:

If the condition is not satisfied, add zero-frequency dummy symbols until it holds. The number of dummy symbols is selected so that:

The resulting tree minimizes the weighted code length among -ary prefix codes. Binary Huffman coding is the special case , for which padding is unnecessary.

The encoded bitstream alone is not sufficient for decoding. The decoder must also know the symbol frequencies, tree structure, or canonical code lengths.

Therefore, the total compressed size is:

Here, is the encoded payload, stores the model or codebook, and accounts for byte alignment or format information.

If the original size is , the compression ratio may be written as:

For small files or files containing many distinct symbols, header overhead may exceed the savings in the payload. Canonical codes and predefined models reduce this overhead.

Huffman coding: Builds a tree bottom-up by repeatedly combining the least probable items. It produces an optimal symbol-by-symbol binary prefix code.

Shannon-Fano coding: Recursively divides a probability-sorted symbol list into groups with approximately equal total probabilities. It is easy to understand but is not guaranteed to produce an optimal prefix code.

Arithmetic coding: Represents an entire message as a subinterval of . Its effective code lengths can be fractional on a per-symbol basis, allowing it to approach entropy more closely than ordinary Huffman coding.

Huffman coding is comparatively simple and fast. Arithmetic coding often compresses highly skewed or context-modeled sources better, but it requires more complex interval computations and implementation care.

Compression systems often transform data before applying Huffman coding.

For example, run-length encoding (RLE) replaces repeated values by pairs such as (value, run length). If the input contains long runs, the transformed representation contains fewer tokens. Huffman coding can then assign short codewords to common values, run lengths, or value-length pairs.

A typical pipeline is:

1. Analyze structural redundancy in the source.
2. Apply a reversible transformation such as RLE, delta coding, or dictionary substitution.
3. Count frequencies of the transformed symbols.
4. Apply Huffman coding to remove statistical redundancy.
5. Store the inverse-transform information and codebook.

The decoder applies the stages in reverse order. The combination is effective only when transformation savings exceed metadata and processing overhead.

Perform the Huffman merges:

One valid code assignment is:

The Huffman payload size is:

For five symbols, a fixed-length code requires:

For symbols, its size is bits. Ignoring headers, the saving is:

or

The payload compression ratio is . Actual performance must also include codebook and padding overhead.