Giving likely outcomes shorter representations
Fixed-length codes ignore differences in frequency. Entropy coding favors likely outcomes while retaining recoverability. Binary entropy H=-Σp log₂p measures average information for a distribution; coding bounds concern expected cost under that model.
A uniquely decodable symbol code cannot have average length below the source entropy. This does not promise exact H-times-length storage for every file or savings on every short or unlikely message. Headers, termination and models also cost bits.
Codeword assignment and interval refinement
Huffman places symbols at binary-tree leaves, optimizing weighted integer codeword lengths within symbolwise prefix codes. Arithmetic coding progressively refines a message interval without allocating a separate integer-length codeword to each symbol.
Encoder and decoder need matching probability information. A fixed model can be shared or transmitted; adaptive updates must be reproducible on both sides rather than using encoder-only history.
The model limits coding efficiency
Coding for q when the source follows p incurs extra average bits. For ideal lengths near negative log probability, this mismatch cost is related to D(p∥q). A more elaborate coder does not automatically repair an inaccurate model.
Single-symbol frequencies do not capture every dependency. Context models, dictionaries or reversible transforms can expose structure before coding. Modeling and bit encoding are distinct tasks, and model storage, time and memory remain part of evaluation.