Run Length Encoding in Python

The following code is my implementation of RLE in Python. I’ve included a method to modify values without having to decode the entire value.

Please note that this algorithm is inferior to the RLE with Positioning I posted about here.

'''
Created on 09/06/2011

@author: adam
'''

import itertools
import copy

# Code modified from
# http://www.builderau.com.au/program/python/soa/Run-length-encoding-in-Python/0,2000064084,339280649,00.htm
def encode( values ):
    return [ (len(list(group)), name) for name, group in itertools.groupby( values ) ]

def decode( rleValues ):
    return sum( [length * [item] for length, item in rleValues], [] )

def getValueAt( rleValues, index ):
    # iterate down the list until we
    # reach our requested length
    start = 0
    for group in rleValues:
        if \
            index >= start and \
            index < (start + group[ 0 ]):
            return group[ 1 ]
        start += group[ 0 ]

def setValueAt( rleValues, index, value ):
    start = 0
    groupIndex = 0
    for group in rleValues:
        if \
            index >= start and \
            index < (start + group[ 0 ]):
            break
        start += group[ 0 ]
        groupIndex += 1

    # to make this easier, lets expand the current group, previous, and next
    # we will modify the value, then run our encoder over it
    # get the groups from our encoded array
    startIndex = groupIndex - 1 if groupIndex > 0 else groupIndex
    endIndex = groupIndex + 1 if groupIndex < len(rleValues) else groupIndex

    # de-code the values from our subset
    values = sum( [length * [item] for length, item in rleValues[ startIndex : endIndex + 1]], [] )

    # determine our offset within the decoded values
    groupStart = start
    if startIndex < groupIndex:
        groupStart -= rleValues[ startIndex ][ 0 ]

    # write our new value into the appropriate location
    values[ index - groupStart ] = value

    # re-encode the groups
    encoded = encode( values )

    # re-insert the values back into the encoded list
    rleValues[ startIndex : endIndex + 1 ] = encoded

    return rleValues
Advertisements

2 Responses to “Run Length Encoding in Python”

  1. […] implemented updated RLE algorithm with proper getValueAt / setValueAt functions and posted the code here. Be aware that I believe this is inferior to the algorithm I mention […]

  2. […] we created a volume pretty quickly Part 1, we also implemented basic RLE and Position Aware RLE […]

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 )

Twitter picture

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

Facebook photo

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

Google+ photo

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

Connecting to %s

%d bloggers like this: