# Introduction to Data Compression with the RLE Algorithm

I'm not going to teach you anything new here, the goal of a data compression algorithm is to take a piece of data (text, image, audio, video, etc.) and apply a certain number of operations to it in order to output lighter data.

But there are several things to know about these algorithms:

• Some are more suited for compressing data with a specific typology
• If it's not suited, an algorithm can have the opposite effect and make data grow bigger
• They are divided into two main families, lossy or lossless

The one we're going to discover today is lossless and particularly suited for images, this algorithm is called: RLE.

How does RLE work?

RLE stands for "Run-Length Encoding" and is often one of the first data compression algorithms studied because it's one of the simplest to understand and implement.

Lossless

As mentioned before, RLE is a lossless algorithm, which means absolutely no data is lost during compression, you could compress the same data three times in a row, and its output quality won't change.

If this seems counter-intuitive to you, just remember that during lossless compression, we trade a bit of memory space for a bit of computing power (for encoding and decoding).

The algorithm

RLE works by scanning an entire resource, from start to finish, and grouping together the repeating data ranges by indicating each time the number of occurrences of the data.

For example:

HellooooooooWoooooooorld becomes 1H1e2l8o1W8o1r1l1d

Here the input data contained 24 characters versus 18 characters after RLE compression, giving us a 25% reduction in data size!

But as you've probably understood, on more typical text, RLE becomes inefficient, even counter-productive:

HelloWorld becomes 1H1e2l1o1W1o1r1l1d

The output data has grown by 80% compared to the input data... So in what situation can RLE actually be used?

Use case

RLE is effective on data that repeats a lot, so the lower the variance between each piece of data, the greater the compression can be.

Images, for example, are often more likely to have contiguous pixels of the same value than letters in a natural language text (a blue sky, for instance).

For black and white images, RLE is more likely to be effective because the variance from one pixel to another is at most 255 levels of gray versus 255³ for the RGB of a color photo.

Take the image below for example:

Normally each pixel of the first row should be represented by 8 bits (in grayscale) and repeated 1920 times, taking a total of 1.8KB just for a completely black row without compression.

With RLE, this first row only weighs 11 bits to store the number (1920), and 8 bits for the grayscale value, which gives us a total of 19 bits, 97 times lighter than the original.

Obviously, this is very impressive for solid color areas, but as soon as we get to the center of the image, RLE's effectiveness will be lower, and this will be the case with most real images.

It's possible to get very good results on illustrations for example, since solid color areas are more frequent.

The RLE algorithm is quite specific, but it's often used as an additional algorithm, on top of other lossy compression algorithms, as in JPEG for example.

Because when we compress with loss first, we often lower the overall variance of the object's data, thus making RLE more effective after an initial compression.

I hope this article was useful, and see you soon on the blog