• Generalities
• Lossy vs. Lossless
• Theories/Methodologies
• Examples
• Full Text Version
• References and Useful Links

Generalities

Lossless vs. Lossy

Theories/methodologies

• Huffman coding
• Arithmetic coding
• Dictionary techniques: LZ77, LZ78, LZW
• RLE
• Quantization
• Transform coding
• Linear prediction
• Video compression

Huffman coding

• Substitute a code for each symbol in source data
  
  
• Short codes assigned to common symbols
  
  
• Longer codes assigned to rarer symbols

Arithmetic coding

• Code (usually a range between 0 and 1) assigned to a sequence of symbols
  
  
  • Note: this is an oversimplification
    
    
• Works well for sources with small alphabets and/or skewed probabilities
  
  
• JBIG (Joint Bi-level Experts Group) standard for b/w images

Dictionary Techniques

• Algorithm looks for repeated sequences of symbols in source
  
  
• Stores (hopefully shorter) code instead of strings
  
  
• Works well for small sources of frequently occurring symbol patterns (example: text)
  
  
• Jacob Ziv and Abraham Lempel's 1977 and 1978 papers

LZ77

• Dictionary is source output itself
  
  
• Compressed file made up of codes which point back to their "meanings"
  
  
• Examples: PKZip, Zip, LHarc

LZ78

• Dictionary constructed from patterns found in source ouput
  
  
  • Dictionary separate from source output
    
    
  • LZW
    
    • Variant of LZ78
    • Started interest in LZ families
    • Examples: compress, V.42bis, GIF

Run Length (En)coding

• "Run" of repeated symbols coded into two parts:
  
  
  • One part: the symbol/bit
    
  • One part: how many times the symbol/bit is repeated in the run
    
    
• Example: standards for facsimile data compression

Quantization

• Algorithm represents a set/block/series/group of values with a much smaller representative set
  
  
• GIF does color quantization
  
  

Transform coding

• Divides the source into components
  
  
• Compresses each component in whatever way is best for that component
  
  
• Example: JPEG lossy variant

Linear prediction

• Values of individual pixels predicted based on the values of surrounding pixels
  
  
• Example: JPEG lossless variant

Video compression

• Compressing a series of images over a period of time (temporal compression)
  
  
• Motion compensation
  
  
• Produces a lot of data, even after compression
  
  
• MPEG-2: full screen/full motion video compresses
  to 500KB/second

Data Compression Examples

GIF (49KB)	Medium quality JPEG (19KB)

Maximum quality JPEG (67KB)	Medium quality JPEG (19KB)