HuffmanDecoding

Huffman decoding is the process of reconstructing the original symbol sequence from a bitstream encoded with Huffman coding, a lossless data compression method that assigns shorter bit patterns to more frequent symbols. The code is a prefix code, meaning no code is a prefix of another, which guarantees unique decoding.

To decode, a decoder must have access to the same Huffman code as the encoder, typically represented as a binary tree where leaves hold symbols. Alternatively, a canonical Huffman code can be reconstructed from a list of code lengths. Decoding proceeds by reading bits from the encoded stream and traversing the tree: 0 means go to the left child, 1 to the right. When a leaf node is reached, its symbol is emitted to the output and the traversal restarts at the tree root for the next symbol. This continues until the end of the data or a designated end-of-stream symbol is encountered.

In practice, decoders implement a bit reader with a small buffer and may use a lookup table to speed up decoding, especially for long code trees. Some schemes support adaptive Huffman coding, where the tree changes as data is encoded, requiring the decoder to update its tree in tandem.

Huffman decoding is widely used in standards such as DEFLATE (ZIP, gzip, zlib) and JPEG, where the code tables are included in the bitstream. Its efficiency depends on the balance of the code tree and the overhead of transmitting the codebook. Errors in the bitstream may lead to misalignment and invalid decoding if not properly checked.