Lossless Compression

• Lossless compression


  The digital data is stored in a compressed form such that it can be recovered, sample for sample, with nothing altered. Nothing is taken away or lost.
• Lossless compression


  • Computer ZIP file (created using the popular Winzip compression software)
• Dictionary-based coding


  A powerful form of lossless coding
• Dictionary-based coding


  • Lempel–Zev–Welch (LZW) algorithm, found in the Winzip software
• Compression algorithm


  1. Scans for patterns

  2. Translates patterns into something that takes up less space
• Text compression example


  • When the going gets tough, the tough get going.
• The original sentence uses 47 units of memory
• The compressed version uses only 27 units of memory
• Dictionary


  • the
  • going
  • tough
• Compressed version


  When 1 2 gets 3, 1 3 get 2.
• Run-length encoding


  Compression method where 'runs' of similar data items are recognised and replaced with a single instance of the data item, together with a number indicating how many times the item is repeated
• Run-length encoding example


  • The striped pattern 01010101010101 can be represented as 7(01)
• Lossless coding use


  • Simple images, such as line drawings and simple shapes in the GIF (Graphics Interchange Format) format used for images on websites