Somewhere deep in human history, shortly after we began counting with numbers and before more “complex” math like “x” (multiply) or x/y (divide) were discovered, our brains were working on inventing something new.

So you maybe wondering why I am mentioning addition, subtraction, multiplication and divide on a page for run length encoding. Well, you are beginning to notice that I make connections between algorithms and human behaviour almost like a social science. That is because we as humans do so many things on a subconscious level that it is like a world of secrets are kept in our minds and in our “natural” responses to problems. Study yourself and a world or secrets will be revealed to you.

Back to math to illustrate RLE, if you look at simple addition and what multiplication does you will see run length encoding at work.

14 = 1 + 1 + 1 + 1 + 2 + 2 + 2 + 2 + 2

14 = (4 x 1) + (5 x 2)

Here we see that run length encoding is exactly like what multiplication does for addition. It shortens long running repeated numbers into a simple form using a new math symbol multiply “x”. Odds are that you if you ever had a bunch of 1, 5, 10 or 20 dollar bills in your wallet (who has paper money anymore, lol), you used run length to figure out how much money you have.

Simple Diagram of RLE

Run-lengthEncoding1

Now that you get the basic concept of RLE, let’s look at source code of a working example. There are dozens of different versions of RLE, ranging from bit level to Unicode characters. In this example you will see RLE working on byte level for simplicity and a possible run length of UInt16 or 65535 characters.

Run Length Encoding (RLE) in C# source code

    public class RunLengthEncoder
    {
        public byte[] EncodeRLE(byte[] inarray)
        {
            int arrayposition = 0;
            int estimatedoutputsize = 0;
            byte[] rlearray = new byte[inarray.Length + 1024];
            for (int x = 0; x < inarray.Length; x++)
            {
                if (x + 6 < inarray.Length)
                {
                    UInt16 runlength = 0;
                    //FIND RUN LENGTH THAT USE LESS SPACE THAN COMPRESSED VERSION 6 BYTES MINIMUM IS REQUIRED HERE
                    if (inarray[x] == inarray[x + 1] && inarray[x] == inarray[x + 2] && inarray[x] == inarray[x + 3] && inarray[x] == inarray[x + 4] && inarray[x] == inarray[x + 5])
                    {
                        //ADD MARKER
                        rlearray[arrayposition] = (byte)0;
                        arrayposition = arrayposition + 1;
                        estimatedoutputsize = estimatedoutputsize + 1;

                        rlearray[arrayposition] = (byte)0;
                        arrayposition = arrayposition + 1;
                        estimatedoutputsize = estimatedoutputsize + 1;

                        //RUN LENGTH VALUE
                        rlearray[arrayposition] = (byte)inarray[x];
                        arrayposition = arrayposition + 1;
                        estimatedoutputsize = estimatedoutputsize + 1;

                        //ADD SCAN HEAD TO SEE HOW LONG RUN IS IN BYTES
                        for (int forwardx = x; forwardx  UInt16.MaxValue)
                                {
                                    runlength = UInt16.MaxValue - 1;
                                    x = x + runlength;
                                    break;
                                }
                            }
                            else
                            {
                                x = x + runlength - 1;
                                break;
                            }
                        }

			//SUPPORT FOR UInt16 SIZE RUNLENGTH
                        byte byte0 = (byte)(runlength >> 8);
                        byte byte1 = (byte)(runlength);

                        rlearray[arrayposition] = byte0;
                        rlearray[arrayposition + 1] = byte1;

                        arrayposition = arrayposition + 2;
                        estimatedoutputsize = estimatedoutputsize + 2;
                    }
                    //MARKER FOUND IN ARRAY NATURALLY WHICH REQUIRES CORRECTION TO ENSURE DECODING IS NOT MISREAD AS A VALID MARKER
                    else if (inarray[x] == 0 && inarray[x + 1] == 0)
                    {
                        rlearray[arrayposition] = (byte)0;
                        arrayposition = arrayposition + 1;
                        estimatedoutputsize = estimatedoutputsize + 1;

                        rlearray[arrayposition] = (byte)0;
                        arrayposition = arrayposition + 1;
                        estimatedoutputsize = estimatedoutputsize + 1;

                        rlearray[arrayposition] = (byte)0;
                        arrayposition = arrayposition + 1;
                        estimatedoutputsize = estimatedoutputsize + 1;

                        rlearray[arrayposition] = (byte)0;
                        arrayposition = arrayposition + 1;
                        estimatedoutputsize = estimatedoutputsize + 1;

                        rlearray[arrayposition] = (byte)0;
                        arrayposition = arrayposition + 1;
                        estimatedoutputsize = estimatedoutputsize + 1;

                        x = x + 1;
                    }
                    else
                    {
                        rlearray[arrayposition] = (byte)inarray[x];
                        arrayposition = arrayposition + 1;
                        estimatedoutputsize = estimatedoutputsize + 1;
                    }
                }
                //TRY TO COMPRESS LAST BYTE OF ARRAY
                else if (x + 1 < inarray.Length)
                {
                    if (inarray[x] == 0 && inarray[x + 1] == 0)
                    {
                        rlearray[arrayposition] = (byte)0;
                        arrayposition = arrayposition + 1;
                        estimatedoutputsize = estimatedoutputsize + 1;

                        rlearray[arrayposition] = (byte)0;
                        arrayposition = arrayposition + 1;
                        estimatedoutputsize = estimatedoutputsize + 1;

                        rlearray[arrayposition] = (byte)0;
                        arrayposition = arrayposition + 1;
                        estimatedoutputsize = estimatedoutputsize + 1;

                        rlearray[arrayposition] = (byte)0;
                        arrayposition = arrayposition + 1;
                        estimatedoutputsize = estimatedoutputsize + 1;

                        rlearray[arrayposition] = (byte)0;
                        arrayposition = arrayposition + 1;
                        estimatedoutputsize = estimatedoutputsize + 1;

                        x = x + 1;
                    }
                    else
                    {
                        rlearray[arrayposition] = (byte)inarray[x];
                        arrayposition = arrayposition + 1;
                        estimatedoutputsize = estimatedoutputsize + 1;
                    }
                }
                else
                {
                    rlearray[arrayposition] = (byte)inarray[x];
                    arrayposition = arrayposition + 1;
                    estimatedoutputsize = estimatedoutputsize + 1;
                }
            }

            //SINCE WE CAN TO DO THIS IN A SINGLE RUN WE DON'T KNOW FINAL OUTPUT SIZE
            //CHECK IF COMPRESSED VERSION IS SMALLER THAN ORIGINAL SIZE
            if (estimatedoutputsize < inarray.Length)
            {
                byte[] returnarray = new byte[estimatedoutputsize];
                for (int i = 0; i < estimatedoutputsize; i++)
                {
                    returnarray[i] = rlearray[i];
                }
                rlearray = null;
                return returnarray;
            }
            else
            {
                rlearray = null;
                return inarray;
            }
        }

        public byte[] DecodeRLE(byte[] inarray)
        {
            byte[] rlearray = new byte[inarray.Length * 2];
            int arrayposition = 0;
            int estimatedoutputsize = 0;
            for (int x = 0; x < inarray.Length; x++)
            {
                if (x + 1 < inarray.Length)
                {
                    //SEARCH FOR MARKER
                    if (inarray[x] == 0 && inarray[x + 1] == 0)
                    {
                        int runvalue = (byte)inarray[x + 2];

                        x = x + 3;

                        int byte0 = inarray[x];
                        int byte1 = inarray[x + 1];

                        x = x + 1;

                        //COMBINE VALUES TO GET FULL SIZE OF RUN LENGTH
                        int runlength = ((byte0 << 8) | byte1);

                        if (runlength == 0 && runvalue == 0)
                        {
                            rlearray[arrayposition] = (byte)0;
                            arrayposition = arrayposition + 1;
                            estimatedoutputsize = estimatedoutputsize + 1;

                            rlearray[arrayposition] = (byte)0;
                            arrayposition = arrayposition + 1;
                            estimatedoutputsize = estimatedoutputsize + 1;
                        }
                        else
                        {
                            for (int forwardx = 0; forwardx < runlength; forwardx++)
                            {
                                rlearray[arrayposition] = (byte)runvalue;
                                arrayposition = arrayposition + 1;
                                estimatedoutputsize = estimatedoutputsize + 1;
                            }
                        }
                    }
                    else
                    {
                        rlearray[arrayposition] = (byte)inarray[x];
                        arrayposition = arrayposition + 1;
                        estimatedoutputsize = estimatedoutputsize + 1;
                    }
                }
                else
                {
                    rlearray[arrayposition] = (byte)inarray[x];
                    arrayposition = arrayposition + 1;
                    estimatedoutputsize = estimatedoutputsize + 1;
                }
            }

            byte[] returnarray = new byte[estimatedoutputsize];
            for (int i = 0; i < estimatedoutputsize; i++)
            {
                returnarray[i] = rlearray[i];
            }
            rlearray = null;
            return returnarray;
        }
    }

Run length encoding is far from the more complex ways we compress our photos, videos and documents, but in so many cases it is unique and quite useful to understand.

Let me know if you want a Java or Objective C version of this.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google+ photo

You are commenting using your Google+ account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s