Data compression algorithms

Data compression reduces the number of bits needed to store or transmit information by removing redundancy from the data. It falls into two broad kinds. Lossless compression encodes data so that the original can be reconstructed exactly, which is essential for text, programs and other files where every bit matters. Lossy compression achieves smaller sizes by discarding detail judged unimportant, an acceptable trade for images, audio and video but not for data that must remain exact. Compression algorithms are the specific procedures that carry out this encoding and decoding.

A classic lossless method is Huffman coding. It rests on the observation that, in most data, some symbols occur far more often than others. Instead of giving every symbol a code of the same length, Huffman coding assigns shorter codes to frequent symbols and longer codes to rare ones, so that the total length of the encoded data is reduced. The algorithm builds a binary tree from the symbols' frequencies, working up from the least common, and the path through the tree to each symbol defines its code. The codes are constructed so that none is a prefix of another, which lets the decoder read them back without ambiguity.

Ordinary Huffman coding needs to know the symbol frequencies in advance, which usually means examining the data first. Adaptive Huffman coding removes this requirement by building and adjusting the code tree as the data is processed, updating frequencies on the fly so that encoder and decoder stay in step without a separate analysis pass. This makes it suitable for streaming situations where the data is not all available at once, at the cost of continually maintaining the tree as symbols arrive.

Frequently asked questions

What is the difference between lossless and lossy compression?

Lossless compression lets the original data be restored exactly, while lossy compression saves more space by permanently discarding detail deemed less important.

How does Huffman coding save space?

It gives frequently occurring symbols shorter codes and rare ones longer codes, so common data is represented in fewer bits and the total encoded size shrinks.

What does adaptive Huffman coding add?

It builds and updates the code tree as data is processed instead of needing the symbol frequencies in advance, which suits streaming data that is not all available at once.