Claudio Cherubino's blog Life of a Googler

11Mar/081

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.

Comments (1) Trackbacks (0)
  1. 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
    

Leave a comment

(required)

No trackbacks yet.