Lossless Compression

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

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

Look 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.

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

Apply dictionary codeing to the lego tower:

Combining Both Techniques:

We can combine both Dictionary Coding and Run-Length Encoding to compress out file even further:

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?