Claudio Cherubino's blog Life of a Googler

7Mar/081

Run-Length Encoding in F#

According to Wikipedia:

Run-length encoding (RLE) is a very simple form of data compression in which runs of data (that is, sequences in which the same data value occurs in many consecutive data elements) are stored as a single data value and count, rather than as the original run. This is most useful on data that contains many such runs: for example, relatively simple graphic images such as icons, line drawings, and animations.

Run-length encoding is used in fax machines. It is relatively efficient because most faxed documents are mostly white space, with occasional interruptions of black.

We will implement now the RLE algorithm in F#, writing a function that will take a list as argument and return a new list of couples (N,E), where N is the number of duplicates of the element E.

Let's show the code:

#light

let pack src =
  let rec pack2 src tmp out =
    match src with
    | [] ->
        if (tmp = [])
          then out
        else (List.append out [tmp])
    | h::t ->
      if (tmp = [])
        then (pack2 t [h] out)
      else
        if (h = (List.hd tmp))
          then (pack2 t (h::tmp) out)
        else (pack2 t [h] (List.append out [tmp]))
    in (pack2 src [] [])

let encode src = List.map (fun b -> (List.length b, List.hd b)) (pack src)

let source = ['a'; 'a'; 'a'; 'a'; 'b'; 'c'; 'c'; 'a'; 'a'; 'd'; 'e'; 'e'; 'e'; 'e']
let answer = source |> encode

First of all we need to pack consecutive duplicates of list elements into sublists, and this is done by the pack function.

Inside pack we define an inner function, called pack2, which is not accessible from outside this block. This also allows us to transform each call like "pack src" to "pack2 src [] []", adding two more arguments to the call.

This inner function moves elements from src to tmp while they are duplicates, and when a different element appears, the list contained in tmp is appended to out.

This process continues until the source list is exhausted, then the out list contains the packed output.

If you want to follow this procedure step-by-step, in the following image you can see the content of src, tmp and out at the beginning of each iteration, using ['a'; 'a'; 'a'; 'a'; 'b'; 'c'; 'c'; 'a'; 'a'; 'd'; 'e'; 'e'; 'e'; 'e'] as input.


Run-length encoding in F#

Now, the actual run-length encoding is trivial. We just have to pack the source list and then apply a function on each element that takes a list of duplicates and returns a couple (N,E), where N is the number of elements and E is the first element (they are all the same).

In our case the final result will be:

[(4, 'a'); (1, 'b'); (2, 'c'); (2, 'a'); (1, 'd'); (4, 'e')]

In the next article I'll present the decoding algorithm, even if I'm quite sure you can easily write it on your own.

Comments (1) Trackbacks (1)
  1. Here is my version of run which builds the encoding directly during the recursion:

    #light
    
    let source = ['a'; 'a'; 'a'; 'a'; 'b'; 'c'; 'c'; 'a'; 'a'; 'd'; 'e'; 'e'; 'e'; 'e']
    
    let encode list =
        let rec altpack list pack =
            match (list,pack) with
            | ([],_) -> (list,List.rev pack)
            | (hl::tl,[]) -> altpack tl [(1,hl)]
            | (hl::tl,(x,y)::tp) -> if y=hl then altpack tl ((x+1,y)::tp)
                                                  else altpack tl ((1,hl)::pack)
        snd (altpack list [])
    
    let answer = encode source
    

Leave a comment

(required)