Compression

Introduction

Compression is needed to allow files to become small enough to store in secondary storage, transfer without taking too much bandwidth, therefore decreasing load times significantly.

There are two types of compression:

• Lossy
• Lossless

Lossy

Imagine you have a HD picture, 1920x1080 pixels, with 32 bit colour. This would take 1920*1080*4 bytes, roughly 8MB. There are many ways that we can compress this down, with lossy we remove information permanently.

One way could be to remove the alpha channel (Transparency), rather than 4 bytes per pixel, we have three. So now, we have 1920x1080x3=6.2MB. This is a slight improvement.

Our next option could be to decrease the colour depth, though this will increase banding, making the image noticeably less nice. If we have 5 bits per pixel instead of 8, we get 3.8MB, which is an even better improvement.

One final option would be to downscale the resolution, from FHD to maybe 720p. So 1280x720, which brings us down to 1.7MB, which is an ideal size. However, there is lots of quality lost, so it depends how far you want to go.

Finally, modern image formats like JPEG use algorithms. Instead of just removing pixels, they:

• Divide the image into blocks (usually 8x8 pixels).
• Approximate similar colours and patterns using an algorithm.
• Let you adjust the compression level - higher compression makes the file smaller but adds artifacts.

Lossless

Lossless compression is a whole different story. The data is still compressed, albeit less compactly. The original file can be completely restored.

There are two main types of lossless: RLE and Dictionary.

RLE (Run Length Encoding)

Imagine you have a grid of pixels:
⬛🟨🟨🟨⬛
⬛🟨⬛🟨⬛
⬛🟨🟨🟨⬛
⬛🟨⬛🟨⬛
⬛🟨⬛🟨⬛

You might notice, there are a few repeating patterns We can encode this as nB where n is the number, and B/Y as the colour so this would become

1b3y2b1y1b1y2b3y2b1y1b1y2b1y1b1y1b
                

Now of course, if we only use the number once, this can be reduced to

b3y2byby2b3y2by2bybyb
                

which is much shorter.

We do run into the risk that our data will show up as a delimiter, such as what if "2" is a potential value

Dictionary Encoding

If we take our same grid of pixels:
⬛🟨🟨🟨⬛
⬛🟨⬛🟨⬛
⬛🟨🟨🟨⬛
⬛🟨⬛🟨⬛
⬛🟨⬛🟨⬛

we can notice there is another pattern. Lets define # as ⬛🟨🟨🟨⬛ and * as ⬛🟨⬛🟨⬛

We can encode this into

#*#**
                

which is substantially shorter than RLE, though it may take longer to construct a dictionary