Decoding RLE in F#

Encoding techniques are useless if you don’t have a way to restore the original message from the compressed data.

A couple of days ago, we saw how to implement the Run-Length Encoding (RLE) algorithm to encode an array of elements and now we are going to describe how to restore the original array.

To decode an array encoded with RLE we take the (length, element) couples, replicate each element by its length and then concatenate the output.

Let’s see the F# implementation:

#light

let decode src =
  let rec decode_block (num, elem) =
    match num with
    | 0 -> []
    | _ -> elem :: decode_block (num-1, elem)
    in List.concat (List.map decode_block src)

At line 8 we concatenate the output of the decode_block function applied to each couple of the src array.

Decode_block is a recursive inner function, which is very easy to understand. In fact, it just repeats elem the number of times indicated by num.

This is everything you need to know to encode and decode arrays (or anything else) by using the RLE algorithm. There are, of course, better compression techniques, if you want we can try to look at them in the future.

1 Comment »

claudio on March 11th 2008 in Functional programming

One Response to “Decoding RLE in F#”

  1. Doug Fort responded on 13 Mar 2008 at 7:59 pm # 

    let decode src =
    let unpack (count, item) =
        let unpack_to_array count item = Array.create count item
        Array.to_list (unpack_to_array count item)
    List.map_concat unpack src

Trackback URI | Comments RSS

Leave a Reply