Meaning and mechanism
Lossless compression must be able to restore the original data exactly from the compressed representation. RunLength encoding utilizes continuous repetition, while Huffman encoding utilizes differences in the frequency of symbols.
It is important to assign short codes to frequently occurring symbols, but these codes must not create ambiguity. Using run lengths for data with infrequent repetition can increase size due to the frequency information.
Relationships and conditions
Entropy H is a reference for the ideal average information content of a symbol distribution. In binary Huffman coding with multiple symbols, the average code length L can be compared with H≤L<H+1.
The experiment excludes the use of a limited alphabet and a fixed number of original bits, and excludes the storage cost of Huffman tables. In actual files, header and dictionary costs, as well as block costs, must also be included.
What to observe in the simulation
Repetition and symbol frequencies determine compression efficiency.
Inputs use four symbols. Originals use 8 bits per symbol; RLE uses 8-bit symbol and count. Huffman table overhead is excluded.
Key relationships and symbols
H ≤ L < H + 1 · ratio = compressed / original
| Symbol | Meaning | Unit |
|---|---|---|
| H | Information entropy per symbol | bit/symbol |
| L | Average code length | bit/symbol |
| Compression ratio | compressed size/original size | Dimensionless |
Worked example
How are frequent symbols coded in Huffman?
Usually shorter · Repetition and symbol frequencies determine compression efficiency.
Common misconceptions
- The fact that the code itself has become smaller does not mean that the entire actual saved file has decreased by the same proportion.