ℹ️Information Theory Unit 6 – Lossless Data Compression Algorithms

Fundamentals of Data Compression

• Data compression reduces the size of data by removing redundancy and representing information more efficiently
• Compression ratio measures the effectiveness of data compression calculated as the ratio of the original data size to the compressed data size
• Lossless compression preserves the original data exactly and allows perfect reconstruction of the original data from the compressed data
• Lossy compression achieves higher compression ratios by allowing some loss of information and approximating the original data
• Entropy is a measure of the average amount of information contained in a message and provides a theoretical limit to the maximum compression achievable without loss
  • Claude Shannon's source coding theorem states that the entropy of a source is the lower bound on the average number of bits per symbol required to encode the source
• Data redundancy occurs when the same information is repeated or can be inferred from other parts of the data
  • Statistical redundancy arises from non-uniform distribution of symbols in the data
  • Syntactic redundancy stems from patterns or structures in the data that can be exploited for compression

Types of Lossless Compression Algorithms

• Entropy encoding techniques assign variable-length codes to symbols based on their probabilities or frequencies in the data
  • Examples include Huffman coding and arithmetic coding
• Dictionary-based methods replace repeated occurrences of data with references to a dictionary that stores the original data
  • Lempel-Ziv (LZ) algorithms such as LZ77 and LZ78 are widely used dictionary-based methods
• Run-length encoding (RLE) replaces consecutive repeated symbols with a single instance of the symbol and a count of the number of repetitions
• Burrows-Wheeler transform (BWT) rearranges the symbols in the data to group similar symbols together enabling more effective compression
• Delta encoding stores the differences between successive values instead of the actual values themselves
• Prediction by partial matching (PPM) builds a statistical model of the data and predicts the next symbol based on the context of previous symbols

Run-Length Encoding (RLE)

• RLE is a simple lossless compression technique that replaces consecutive repeated symbols with a single instance of the symbol and a count of the repetitions
• Suitable for data with long runs of repeated symbols such as simple images with large areas of uniform color
• Encoding process:
  1. Scan the input data and identify runs of repeated symbols
  2. Replace each run with the symbol and the count of repetitions
• Decoding process:
  1. Read the encoded data symbol by symbol
  2. For each symbol read the count and repeat the symbol that many times
• Example: The string "AAAABBBCCCCCCDD" would be encoded as "A4B3C6D2"
• RLE is computationally inexpensive and easy to implement but may not achieve high compression ratios for complex data
• Variations of RLE include:
  • Run-length limited (RLL) encoding used in magnetic and optical storage devices
  • Packbits a variant used in Macintosh graphics formats

Huffman Coding

• Huffman coding is an entropy encoding algorithm that assigns variable-length codes to symbols based on their frequencies in the input data
• Generates an optimal prefix code where no code is a prefix of any other code ensuring unique decodability
• Encoding process:
  1. Build a frequency table counting the occurrences of each symbol in the input data
  2. Construct a Huffman tree by repeatedly combining the two least frequent symbols into a new node until a single root node remains
  3. Assign codes to symbols by traversing the Huffman tree from the root to each leaf node where left branches represent '0' and right branches represent '1'
• Decoding process:
  1. Traverse the Huffman tree from the root following the encoded bits until a leaf node is reached
  2. Output the symbol associated with the leaf node and return to the root to decode the next symbol
• Example: For the string "AAAABBBCCCCCCDD" the Huffman codes might be: A=00 B=01 C=1 D=001
• Huffman coding achieves good compression ratios for data with non-uniform symbol frequencies but may not perform well for small alphabets or uniformly distributed symbols
• The Huffman tree needs to be transmitted or agreed upon in advance between the encoder and decoder

Arithmetic Coding

• Arithmetic coding is an entropy encoding technique that assigns a unique interval to each symbol based on its probability and recursively subdivides the interval according to the sequence of symbols in the input data
• Achieves near-optimal compression ratios approaching the entropy of the source
• Encoding process:
  1. Initialize the current interval [0,1)
  2. For each symbol in the input data:
     • Subdivide the current interval into subintervals proportional to the probabilities of the symbols
     • Select the subinterval corresponding to the current symbol and update the current interval
  3. Output enough bits to uniquely identify the final subinterval
• Decoding process:
  1. Initialize the current interval [0,1)
  2. While there are more symbols to decode:
     • Find the subinterval containing the encoded value
     • Output the symbol corresponding to that subinterval
     • Update the current interval to the found subinterval
• Example: For the string "AAAABBBCCCCCCDD" with probabilities A=0.4 B=0.3 C=0.2 D=0.1 the final subinterval might be [0.0768 0.0776)
• Arithmetic coding can compress data close to the entropy limit but is more computationally intensive than Huffman coding
• The probabilities of symbols need to be known or estimated in advance and transmitted to the decoder

Dictionary-Based Methods

• Dictionary-based methods replace repeated occurrences of data with references to a dictionary that stores the original data
• The dictionary can be static (predefined) or adaptive (built dynamically during the encoding process)
• Lempel-Ziv (LZ) algorithms are widely used dictionary-based methods:
  • LZ77 maintains a sliding window of previously seen data and replaces matches with references to the window
  • LZ78 builds a dictionary of previously seen phrases and replaces matches with references to the dictionary
• Encoding process (LZ77):
  1. Initialize the sliding window and look-ahead buffer
  2. Find the longest match of the look-ahead buffer in the sliding window
  3. Output a reference (distance length) to the match and the next unmatched symbol
  4. Move the sliding window and look-ahead buffer forward
• Decoding process (LZ77):
  1. Initialize the output buffer
  2. For each reference (distance length) and unmatched symbol:
     • Copy length symbols from the output buffer at distance back
     • Append the unmatched symbol to the output buffer
• Example (LZ77): The string "ABABCBABABAA" would be encoded as (0 0 'A')(0 0 'B')(0 0 'C')(2 2 'B')(5 4 'A')
• Dictionary-based methods are efficient for data with repeated patterns and achieve good compression ratios
• The dictionary size affects the compression ratio and computational complexity
• Variants of LZ algorithms include LZSS LZW and LZMA which are used in popular compression formats like ZIP GIF and 7Z

Performance Metrics and Comparisons

• Compression ratio: The ratio of the size of the compressed data to the size of the original data
  • Higher compression ratios indicate better compression
  • Lossless compression typically achieves compression ratios between 2:1 and 10:1 depending on the data type and algorithm
• Compression speed: The time taken to compress the data
  • Faster compression speeds are desirable for real-time applications and large datasets
  • Algorithms like RLE and Huffman coding are relatively fast while arithmetic coding and dictionary-based methods are slower
• Decompression speed: The time taken to reconstruct the original data from the compressed data
  • Fast decompression is important for applications that require frequent access to the original data
  • Decompression is usually faster than compression for most algorithms
• Memory usage: The amount of memory required by the compression and decompression processes
  • Lower memory usage is preferred for resource-constrained systems and embedded devices
  • Algorithms like RLE and Huffman coding have low memory requirements while dictionary-based methods may require more memory
• Algorithmic complexity: The computational complexity of the compression and decompression algorithms
  • Lower complexity algorithms are easier to implement and may be more suitable for hardware implementations
  • RLE and Huffman coding have relatively low algorithmic complexity while arithmetic coding and dictionary-based methods are more complex
• Adaptability: The ability of the algorithm to adapt to different types of data and changing statistics
  • Adaptive algorithms like arithmetic coding and adaptive dictionary-based methods can handle a wide range of data types and achieve good compression ratios
  • Static algorithms like Huffman coding may need to be optimized for specific data types to achieve optimal performance

Real-World Applications

• File compression: Lossless compression is widely used to reduce the size of files for storage and transmission
  • Examples include ZIP RAR and 7Z formats which use a combination of dictionary-based methods and entropy encoding
• Text compression: Lossless compression is essential for compressing text documents source code and database records
  • Huffman coding arithmetic coding and dictionary-based methods are commonly used for text compression
• Image compression: Lossless image compression is used when exact reconstruction of the original image is required (medical imaging satellite imagery)
  • Formats like PNG and GIF use a combination of dictionary-based methods (LZ variants) and entropy encoding (Huffman coding)
• Audio compression: Lossless audio compression is used for high-quality audio archiving and distribution
  • Formats like FLAC and ALAC use linear prediction and entropy encoding to achieve compression ratios around 2:1
• Network data compression: Lossless compression is used to reduce the amount of data transmitted over networks improving bandwidth utilization and latency
  • Algorithms like Huffman coding and dictionary-based methods are used in network protocols like HTTP and SSH
• Genomic data compression: Lossless compression is crucial for storing and analyzing large amounts of genomic data generated by next-generation sequencing technologies
  • Specialized algorithms like CRAM and DSRC exploit the repetitive nature of genomic data and use a combination of dictionary-based methods and entropy encoding
• Blockchain and cryptocurrency: Lossless compression is used to reduce the size of transaction data stored on the blockchain
  • Bitcoin uses a custom Huffman coding scheme to compress public keys and signatures in transactions