liveBook · Manning

Compression

As explained in Timeless Algorithms, The Foundational Ideas

Encoding information using fewer bits or symbols while preserving what is needed for its recovery or use.

Compression represents information with fewer bits by removing predictable redundancy without changing the information to be recovered. Entropy measures source uncertainty: AAAAAA can be written A × 6, while W7dX8$ offers little redundancy to remove. In communication systems, this distinction helps estimate transmission needs and channel capacity. Redundancy is not always waste: predictable redundancy can be removed, while deliberately added redundancy can help detect or correct errors caused by noise. section 5.1.4

Figure 5.1 Entropy measures the uncertainty associated with an information source in bits. A fair coin has an entropy of 1 bit, while a biased coin has lower entropy (0.47 bits) because one outcome is much more predictable than the other. A fair die (2.59 bits) and a standard deck of cards (5.7 bits) have progressively higher entropy because they contain larger sets of equally likely outcomes. As entropy increases, preserving the original information becomes increasingly important because there is less redundancy available for compression. Conversely, as entropy decreases, greater redundancy creates more opportunities to compress the source without losing information.

Compare entropy across coins, dice, and cards to see how greater uncertainty leaves less redundancy available for compression. section 5.1.4

How Timeless Algorithms, The Foundational Ideas covers it

How deep it goes
Explains predictable versus unpredictable sequences and distinguishes removable redundancy from redundancy added to detect or correct noise.
Examples
Contrasts AAAAAA, encoded as A × 6, with W7dX8$ and compares entropy values for coins, dice, and cards.
What you can do after
Evaluate compression opportunities by relating source entropy and predictable redundancy to the bits required for transmission.
How it connects
Connects entropy and redundancy to channel capacity, transmission noise, and error detection and correction.

Also explained in

Compare how 15 books explain compression →

Related concepts

This explainer was generated by Manning's knowledge graph from the text of Timeless Algorithms, The Foundational Ideas. The section links point to the parts of the book it draws on.