Run Length Encoding a Swan

Run Length Encoding (RLE) is a simple data compression scheme.
This scheme compresses strings by replacing consecutive characters by the number of occurrences of the character followed by that character.
For example aaaBBccD@@@ would be represented as 3a2B2c1D3@ or 3a2B2cD3@, i.e. the number 1 can be omitted when, like above with D, there is only one character. In this post we will leave the 1 out.
Each sequence of a repeated character is called a run thus the name Run Length Encoding.

RLE or more complicated data compression schemes  make modern communication possible: by reducing the size of images and videos by 20 times or more, the compressed image/video is much faster and cheaper to transmit.
Consider the following swan "image"

@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@
@@@@@@@@@@@@@@@@@@,,,@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@
@@@@@@@@@@@@@@.#S@@@@..%:@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@
@@@@@@@@@@@@@%:@@@@@@@@@S%,@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@
@@@@@@@@@@@@+@@@@@@@@@@@@@%.@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@
@@@@@@@@@@@.S@@@@@@@@@@@@@@@%+@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@
@@@@@@@@@@@%@@@@@@@@@@@@@@@@@.@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@
@@@@@@@@@@@%@@@@@%@@@@@@@@@@@@%@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@
@@@@@@@@@@:+@@@@S%@@@@@@@@@@@@@%@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@
@@@@@@@@@@*.@@@*##@@@@@@@@@@@@@,#@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@
@@@@@@@@@@*.@@@%.?@@@@@@@@@@@@@@.@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@
@@@@@@@@@@:?,@?*%#@@@@*%.%@@@@@@@+@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@
@@@@@@@@@@:.%@+.:@@@:%S@@S@@@@@@@?@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@
@@@@@@@@@@?,@%:@@@:..@@@@@:@@@@@@.@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@
@@@@@@@@@@.@@:.#%*@@@@@@@@#@@@@@@,S@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@
@@@@@@@@@%@@@#@@@@@@@@@@@@*@@@@@@@#@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@
@@@@@@@@#*@@S,@@@@@@@@@@@@:@@@@@@@%@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@
@@@@@@%+@@.?@@@@@@@@@@@@@:@@@@@@@@%@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@
@@@@@@?@,..@@@@@@@@@@@@@@S@@@@@@@@%@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@
@@@@@@#?#,@@@@@@@@@@@@@@@%@@@@@@@@.@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@
@@@@@@@@@@@@@@@@@@@@@@@@,?@@@@@@@@%@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@
@@@@@@@@@@@@@@@@@@@@@@@@S:@@@@@@@@%@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@
@@@@@@@@@@@@@@@@@@@@@@@@%@@@@@@@@@?@@@@@@@@@@@@@@@@@@@@@@@@::*+SSSSS.*:@@@@@@@@@@@@@@@@@@@@@@@@@@@@@
@@@@@@@@@@@@@@@@@@@@@@@:.@@@@@@@@,%@@@@@@@@@@@@@@@@@@@@..%%?+.:,,,,,*.S?%%?@@@@@@@@@@@@@@@@@@@@@@@@@
@@@@@@@@@@@@@@@@@@@@@@@%@@@@@@@@@.,@@@@@@@@@@@@@@@,.?+,@@@@@@@@@@@@@@@@@?.@@@@@@@@@@@@@@@@@@@@@@@@@@
@@@@@@@@@@@@@@@@@@@@@@@S@@@@@@@@@%@@@@@@@@@@@@@@:%S,@@@@@@@@@@@@@@@@@@@?,@@@@@@@@@@@@@@@@@@@@@@@@@@@
@@@@@@@@@@@@@@@@@@@@@@.@@@@@@@@@@*@@@@@@@@@@@@.%S@@@@@@@@@@@@@@@@@@@@@.,@@@@@@@@@@@@@@@@@@@@@@@@@@@@
@@@@@@@@@@@@@@@@@@@@@*#@@@@@@@@@%@@@@@@@@@@,%.@@@@@@@@@@@@@@@@@@@@@@@S*@@,..%??%%%%%S.:,@@@@@@@@@@@@
@@@@@@@@@@@@@@@@@@@@@%@@@@@@@@@++@@@@@@@@@%%,@@@@@@@@@@@@@@@@@@@@@@@,%,%%.*@@@@@@@@@,:+?%S:@@@@@@@@@
@@@@@@@@@@@@@@@@@@@@%:@@@@@@@@,%@@@@@@@@@%*@@@@@@@@@@@@@@@@@@@@@@@@@%#.@@@@@@@@@@@@@@@@@@,S%+@@@@@@@
@@@@@@@@@@@@@@@@@@@*,@@@@@@@@@%@@@@@@@@%*@@@@@@@@@@@@@@@@@@@@@@@@@@@.@@@@@@@@@@@@@@@@@@@@@@@@,#.@@@@
@@@@@@@@@@@@@@@@@@@%@@@@@@@@@@:@@@@@@,%@@@@@@@@@@@@@@@@@@@@@@@@@@@@.@@@@@@@@@@@@@@@@@@@@@@@@:%.@@@@@
@@@@@@@@@@@@@@@@@@#:@@@@@@@@@%@@@@@@+%@@@@@@@@@@@@@@@@@@@@@@@@@@@@:%@@@@@@@@@@@@@@@@@@@@@@@%.@@@@@@@
@@@@@@@@@@@@@@@@@%:@@@@@@@@@.S@@@@@%@@@@@@@@@@@@@@@@@@@@@@@@@@@@@*%@@@@@@@@@@@@@@@@@@@@@@..@@@@@@@@@
@@@@@@@@@@@@@@@@@.@@@@@@@@@@%@@@@:#@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@#,@@@@@@@@@@@@@@@@@@@@@#*@@@@@@@@@@
@@@@@@@@@@@@@@@@.@@@@@@@@@@:.@@@@%@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@.,@@@@@@@@@@@@@@@@@@@@@.,@@@@@@@@@@@
@@@@@@@@@@@@@@@:%@@@@@@@@@@%@@@S.@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@%.@@@@@@@@@@@@@@@@@@@@@%@@@@@@@@@@@@@
@@@@@@@@@@@@@@@%@@@@@@@@@@@%@@SS@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@.S@@@@@@@@@@@@@@@@@@@@@%,@@@@@@@@@@@@@
@@@@@@@@@@@@@@*S@@@@@@@@@@*.@@S@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@,.@@@@@@@@@@@@@@@@@@@@@.*@@@@@@@@@@@@@@
@@@@@@@@@@@@@@#@@@@@@@@@@@%@.%@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@%S@@@@@@@@@@@@@@@@@@@@@@S@@@@@@@@@@@@@@@
@@@@@@@@@@@@@.:@@@@@@@@@@@%:%@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@S%@@@@@@@@@@@@@@@@@@@@@@*@@@@@@@@@@@@@@@@
@@@@@@@@@@@@@%@@@@@@@@@@@@%%@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@S.@@@@@@@@@@@@@@@@@@@@@@@%@@@@@@@@@@@@@@@@
@@@@@@@@@@@@@,@@@@@@@@@@@@#@@@@@@@@@@@@@@@@@@@@@@@@@@@@@.%@@@@@@@@@@@@@@@@@@@@@@@@.:@@@@@@@@@@@@@@@@
@@@@@@@@@@@@S@@@@@@@@@@@@@,@@@@@@@@@@@@@@@@@@@@@@@@@@@@%*@@@@@@@@@@@@@@@@@@@@@@@@@%@@@@@@@@@@@@@@@@@
@@@@@@@@@@@@%@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@S%@@@@@@@@@@@@@@@@@@@@@@@@@@.:@@@@@@@@@@@@@@@@@
@@@@@@@@@@@@%@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@:%.@@@@@@@@@@@@@@@@@@@@@@@@@@@@?@@@@@@@@@@@@@@@@@@
@@@@@@@@@@@@%@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@*%S@@@@@@@@@@@@@@@@@@@@@@@@@@@@@*@@@@@@@@@@@@@@@@@@@
@@@@@@@@@@@@%@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@:%%+@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@%@@@@@@@@@@@@@@@@@@@
@@@@@@@@@@@@#@@@@@@@@@@@@@@@@@@@@@@@:,,:*+%%#+@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@*S@@@@@@@@@@@@@@@@@@@
@@@@@@@@@@@@.@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@%@@@@@@@@@@@@@@@@@@@@
@@@@@@@@@@@@*@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@.:@@@@@@@@@@@@@@@@@@@@
@@@@@@@@@@@@@:@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@%@@@@@@@@@@@@@@@@@@@@@
@@@@@@@@@@@@@%@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@%@@@@@@@@@@@@@@@@@@@@@@
@@@@@@@@@@@@@.S@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@S.@@@@@@@@@@@@@@@@@@@@@@
@@@@@@@@@@@@@@#,@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@+S@@@@@@@@@@@@@@@@@@@@@@@
@@@@@@@@@@@@@@@?,@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@.,@@@@@@@@@@@@@@@@@@@@@@@@
@@@@@@@@@@@@@@@@%@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@:%*@@@@@@@@@@@@@@@@@@@@@@@@@
@@@@@@@@@@@@@@@@,%@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@#%@@@@@@@@@@@@@@@@@@@@@@@@@@@
@@@@@@@@@@@@@@@@@@+%:@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@,.%%:@@@@@@@@@@@@@@@@@@@@@@@@@@@@@
@@@@@@@@@@@@@@@@@@@@S#%..S.*:,@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@:S%%.@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@
@@@@@@@@@@@@@@@@@@@@@@@,,:*.+.%#%S.*,,@@@@@@@@@@@@@@@@@@@@,+.%%S*@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@
@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@,+:*.++SS...#..S.*,@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@
@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@

The image consists of only the 11 symbols

#, ?, %, . , S, +, ., *, :, , , @

adding up to a total of 6400 characters (100 characters on each of 64 rows).
We can easily see that compressing this image using RLE will achieve a significant compression rate.

Encoding

How do we perform such compression?
First in the trinket code below notice how we have 2 files: one is the usual main.py and the other is named data.py.
This data.py file contains a single list called swan. Each element in the list is a row of the swan image above. So this list has 64 elements (64 rows) each with a string 100 characters long.

Access to this list from main.py is achieved through the line

import data

at the top of main.py. Then whenever we want to access the swan list we do

swan = data.swan 

We then loop through every element of the swan list. For each element we loop through each one of its characters and keep a running counter of how many consecutive identical characters there are. Once we detect a change of character we append the count and the character it counts to a string variable (rowEncoded) representing the RLE of the row, reset the counter to 1 and keep counting how many of the new character there are. If there is only one character we do not prepend the count to the character as mentioned above.

This becomes perhaps clearer looking at the code

 
import data

swan = data.swan

'''
Given an image (represented by a list of its rows)
Run Length Encodes each row of the image and returns
the result as a list of the encoded image rows
'''
def encode(image):
    imageEncoded = []
    # loop through every image row
    for row in image:
        rowEncoded = ''
        count = 0
        char = row[0]
        # loop through every character in the row
        # and count how many consecutive elements of 
        # that character are on that image row
        for character in row:
            # switching to a new character
            if  char != character:
               # dont add 1 
               if count == 1:
                   rowEncoded += char
               else:
                   rowEncoded += str(count) + char
               char = character
               count = 1
            else:
               count += 1
        # encode the last character in the row
        if count == 1:
            rowEncoded += char
        else:
            rowEncoded += str(count) + char
            
        # add encoded row to list holding the image encoding
        imageEncoded.append(rowEncoded)
    return imageEncoded    
    
imageEncoded = encode(swan)

With this encoding the first 5 rows of the above swan image become

100@
18@3,79@
14@.#S4@2.%:75@
13@%:9@S%,73@
12@+13@%.72@

Notice how the characters in each line add up always to 100 which is the number of characters in each row of the original image.

In total there are now 1196 characters instead of the 6400 in the original image, i.e.  1196/6400 = 0.186 or 18.6 percent of the original characters.

Decoding

To decode an image encoded with RLE (the inverse of what we just did) we again loop through each element of the list holding the encoded rows. For each such element we loop through its characters.
If the character is a digit we hold it in a counter variable. Otherwise we append the character following the digit as many times as the digit. If we find a character without a digit preceding it we assume it only appears once and thus we only append it once.

Some important details are in order in this process:  a character might appear more than 9 times in a row, i.e. 2 or more digits. For example above the second row is 18@3,79@. That is 18 @(s) followed by 3 , followed by 79 @(s). As we scan each of the characters we come across the 1 and store it in our count variable. The next character is also a digit, 8 so we want to store in our count variable

count = count*10+8 

we need to remember though that 1 and 8 will be represented by their ASCII characters (49 and 56).
Therefore we should instead do, in python,

count = count*10 + ord(character) - ord('0')

since the python function ord will return the ascii (more properly the unicode) value of the character we pass it to it.

Also because of the fact that the count can be greater than 9, we will assume for simplicity that our string does not have any numbers (otherwise a string like 222d that would be converted to 32d would seem to imply that d appears 32 times).

The decode code in python is then

 

'''
Given a run length encoded image (represented by a list of its rows)
decode each row of the image and return
the result as a list of the unencoded image rows. It also
returns the total number of characters in both the 
original encoded image and the unencoded image
'''
def decode(encodedImage):
    imageDecoded = []
    # loop through every image row
    for row in encodedImage:
        rowDecoded = ''
        count = 0
        char = row[0]
        # loop through every character in the row
        # and count how many consecutive elements of 
        # that character are on that image row
        for character in row:
            # switching to a new character
            if  character.isdigit():
               count = count*10 + ord(character)-ord('0')
            else:
               if count == 0:
                   count = 1
               rowDecoded += character*count
               count = 0
        # add decoded row to list holding the image decoding      
        imageDecoded.append(rowDecoded)
    return imageDecoded
   

Note how we do

rowDecoded += character*count

This will append count number of character to the string rowDecoded. It is a very short way of doing what we want rather than the more verbose way of looping count times and adding character each time to rowDecoded.


Assembling the encode and decode methods in a class RunLengthEncoding and a few tests in a Test class we end this post with the following python code