Lossless Compression

The purpose of lossless compression is to reduce the amount of storage space needed to save some information, without loosing any information hence without loosing quality.

Lossless compression can be used to store text-based information in a more effective way.

lossless-compression-lego-towerLook at the above text file used to store the pattern of a lego tower. Can you think of a better way to store this information?


Method #1: Run-length Encoding


Run-length encoding (RLE) is a very simple form of lossless data compression in which runs of data (that is, sequences in which the same data value occurs in many consecutive data elements) are stored as a single data value and count.

lossless-compression-lego-tower-2
Apply run-length encoding to the lego tower:


Method #2: Dictionary Coding


Dictionary coding, aka substitution coding, is a lossless data compression approach which consists of searching for matches between the text to be compressed and a set of strings contained in a data structure (called the ‘dictionary’) maintained by the encoder. When the encoder finds such a match, it substitutes a reference to the string’s position in the data structure.

For instance in we could use the following dictionary:

  • B -> Blue
  • G -> Green
  • R -> Red
  • Y -> Yellow

lossless-compression-lego-tower-4
Apply diciotnay codeing to the lego tower:


Combining Both Techniques:


We can combine both Dictionary Coding and Run-Length Encoding to compress out file even further:
lossless-compression-lego-tower-5

Apply both techniques to your lego tower:





Lossless compression of bitmap pictures


We have applied lossless compression to a text file. How could we use this type of compression for picture files?

Share Button
Posted in Computer Science, Computing Concepts

Our Latest Book

Follow this blog