Run-length encoding

Identifying and grouping by runs in base R

One might want to group their data by the runs of a variable and perform some sort of analysis. Consider the following simple dataset:

(dat <- data.frame(x = c(1, 1, 2, 2, 2, 1), y = 1:6))
#   x y
# 1 1 1
# 2 1 2
# 3 2 3
# 4 2 4
# 5 2 5
# 6 1 6

The variable x has three runs: a run of length 2 with value 1, a run of length 3 with value 2, and a run of length 1 with value 1. We might want to compute the mean value of variable y in each of the runs of variable x (these mean values are 1.5, 4, and 6).

In base R, we would first compute the run-length encoding of the x variable using rle:

(r <- rle(dat$x))
# Run Length Encoding
#   lengths: int [1:3] 2 3 1
#   values : num [1:3] 1 2 1

The next step is to compute the run number of each row of our dataset. We know that the total number of runs is length(r$lengths), and the length of each run is r$lengths, so we can compute the run number of each of our runs with rep:

(run.id <- rep(seq_along(r$lengths), r$lengths))
# [1] 1 1 2 2 2 3

Now we can use tapply to compute the mean y value for each run by grouping on the run id:

data.frame(x=r$values, meanY=tapply(dat$y, run.id, mean))
#   x meanY
# 1 1   1.5
# 2 2   4.0
# 3 1   6.0

Run-length Encoding with `rle`

Run-length encoding captures the lengths of runs of consecutive elements in a vector. Consider an example vector:

dat <- c(1, 2, 2, 2, 3, 1, 4, 4, 1, 1)

The rle function extracts each run and its length:

r <- rle(dat)
r
# Run Length Encoding
#   lengths: int [1:6] 1 3 1 1 2 2
#   values : num [1:6] 1 2 3 1 4 1

The values for each run are captured in r$values:

r$values
# [1] 1 2 3 1 4 1

This captures that we first saw a run of 1’s, then a run of 2’s, then a run of 3’s, then a run of 1’s, and so on.

The lengths of each run are captured in r$lengths:

r$lengths
# [1] 1 3 1 1 2 2

We see that the initial run of 1’s was of length 1, the run of 2’s that followed was of length 3, and so on.

Run-length encoding to compress and decompress vectors

Long vectors with long runs of the same value can be significantly compressed by storing them in their run-length encoding (the value of each run and the number of times that value is repeated). As an example, consider a vector of length 10 million with a huge number of 1’s and only a small number of 0’s:

set.seed(144)
dat <- sample(rep(0:1, c(1, 1e5)), 1e7, replace=TRUE)
table(dat)
#       0       1
#     103 9999897

Storing 10 million entries will require significant space, but we can instead create a data frame with the run-length encoding of this vector:

rle.df <- with(rle(dat), data.frame(values, lengths))
dim(rle.df)
# [1] 207   2
head(rle.df)
#   values lengths
# 1      1   52818
# 2      0       1
# 3      1  219329
# 4      0       1
# 5      1  318306
# 6      0       1

From the run-length encoding, we see that the first 52,818 values in the vector are 1’s, followed by a single 0, followed by 219,329 consecutive 1’s, followed by a 0, and so on. The run-length encoding only has 207 entries, requiring us to store only 414 values instead of 10 million values. As rle.df is a data frame, it can be stored using standard functions like write.csv.

Decompressing a vector in run-length encoding can be accomplished in two ways. The first method is to simply call rep, passing the values element of the run-length encoding as the first argument and the lengths element of the run-length encoding as the second argument:

decompressed <- rep(rle.df$values, rle.df$lengths)

We can confirm that our decompressed data is identical to our original data:

identical(decompressed, dat)
# [1] TRUE

The second method is to use R’s built-in inverse.rle function on the rle object, for instance:

rle.obj <- rle(dat)                            # create a rle object here
class(rle.obj)
# [1] "rle"

dat.inv <- inverse.rle(rle.obj)               # apply the inverse.rle on the rle object

We can confirm again that this produces exactly the original dat:

identical(dat.inv, dat)
# [1] TRUE

Identifying and grouping by runs in data.table

The data.table package provides a convenient way to group by runs in data. Consider the following example data:

library(data.table)
(DT <- data.table(x = c(1, 1, 2, 2, 2, 1), y = 1:6))
#    x y
# 1: 1 1
# 2: 1 2
# 3: 2 3
# 4: 2 4
# 5: 2 5
# 6: 1 6

The data.table rleid function provides an id indicating the run id of each element of a vector:

rleid(DT$x)
# [1] 1 1 2 2 2 3

One can then easily group on this run ID and summarize the y data:

DT[,mean(y),by=.(x, rleid(x))]
#    x rleid  V1
# 1: 1     1 1.5
# 2: 2     2 4.0
# 3: 1     3 6.0

Remarks

A run is a consecutive sequence of repeated values or observations. For repeated values, R’s “run-length encoding” concisely describes a vector in terms of its runs. Consider:

dat <- c(1, 2, 2, 2, 3, 1, 4, 4, 1, 1)

We have a length-one run of 1s; then a length-three run of 2s; then a length-one run of 3s; and so on. R’s run-length encoding captures all the lengths and values of a vector’s runs.

Extensions

A run can also refer to consecutive observations in a tabular data. While R doesn’t have a natural way of encoding these, they can be handled with rleid from the data.table package (currently a dead-end link).