Compression

• Statistical Redundancy occurs when certain symbols or patterns appear more frequently than others; compression algorithms exploit this by assigning shorter codes to frequent symbols.

• Spatial Redundancy refers to the correlation between neighboring elements, such as adjacent pixels in an image having similar colors.

• Temporal Redundancy is found in video data where consecutive frames are often nearly identical, allowing the system to store only the changes between frames.

• Perceptual Irrelevancy is the basis for lossy compression, where information that the human eye or ear cannot detect is removed to save space.

Lossless Algorithms

• Run-Length Encoding (RLE): Replaces sequences of identical data elements (runs) with a single value and a count. It is most effective on data with many consecutive repeating values.
• Huffman Coding: A variable-length coding technique that uses a binary tree to assign shorter bit strings to more frequent characters, ensuring no code is a prefix of another.
• Lempel-Ziv-Welch (LZW): A dictionary-based algorithm that builds a table of recurring patterns on the fly, replacing long strings with short index codes.

Lossy Algorithms

• Transform Coding: Converts data from the spatial domain to the frequency domain (e.g., Discrete Cosine Transform) to isolate and discard high-frequency components that are less perceptible.
• Quantization: The process of mapping a large set of input values to a smaller set, effectively 'rounding' data to reduce precision and save bits.

• The choice between lossless and lossy compression depends entirely on the tolerance for data degradation versus the need for storage efficiency.

• Fixed-length vs. Variable-length: Fixed-length coding uses the same number of bits for every symbol, while variable-length coding (like Huffman) optimizes bit usage based on probability.

• Check the Context: If a question involves medical imaging or executable software, always prioritize Lossless methods because any data loss could be fatal or break the program.

• Calculate Ratios Carefully: Ensure you are dividing the original size by the compressed size. If the result is less than $1$, the file has actually grown (a common occurrence with already-compressed data).

• Entropy Limits: Remember that you cannot compress data below its entropy without losing information. If a problem asks for the 'theoretical minimum bits,' they are asking for the entropy calculation.

• Identify Redundancy: Before selecting an algorithm, identify the type of redundancy. RLE is for repeating sequences; Huffman is for frequency imbalances; DCT is for visual/audio patterns.

• The 'Infinite Compression' Myth: Students often think a file can be compressed repeatedly to reach near-zero size. In reality, once redundancy is removed, further compression attempts usually increase file size due to metadata overhead.

• Lossy is 'Bad': A common misconception is that lossy compression is always inferior. In streaming and telecommunications, lossy compression is essential because lossless files would exceed available bandwidth.

• Confusing Bitrate with Ratio: Bitrate (bits per second) is a measure of transmission speed, while compression ratio is a measure of storage efficiency. They are related but distinct concepts.