R Language
Encodage de longueur d'exécution

Remarques

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

Encodage de longueur d'exécution avec `rle`

Le codage de longueur d'exécution capture les longueurs des exécutions d'éléments consécutifs dans un vecteur. Prenons un exemple de vecteur:

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

La fonction rle extrait chaque exécution et sa longueur:

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

Les valeurs pour chaque exécution sont capturées dans les r$values :

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

Cela montre que nous avons d'abord vu une série de 1, puis une série de 2, puis une série de 3, puis une série de 1, etc.

Les longueurs de chaque exécution sont capturées en r$lengths :

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

Nous voyons que la série initiale de 1 était de longueur 1, la série de 2 qui a suivi était de longueur 3, et ainsi de suite.

Identification et regroupement par exécutions dans la base R

On pourrait vouloir grouper leurs données par les analyses d'une variable et effectuer une sorte d'analyse. Considérons le jeu de données simple suivant:

(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

La variable x a trois exécutions: une longueur de 2 avec une valeur de 1, une longueur de 3 avec une valeur de 2 et une longueur de 1 avec une valeur de 1. On peut calculer la valeur moyenne de la variable y dans chacun des exécutions de la variable x (ces valeurs moyennes sont 1,5, 4 et 6).

Dans la base R, nous calculons d'abord le codage de la longueur de la variable x à l'aide de rle :

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

L'étape suivante consiste à calculer le numéro d'exécution de chaque ligne de notre jeu de données. Nous savons que le nombre total d'exécutions est de length(r$lengths) , et que la longueur de chaque exécution est r$lengths , nous pouvons donc calculer le numéro d'exécution de chacune de nos exécutions avec rep :

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

Maintenant, nous pouvons utiliser tapply pour calculer la valeur moyenne y pour chaque exécution en regroupant sur l'ID d'exécution:

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

Identifier et regrouper par exécutions dans data.table

Le package data.table fournit un moyen pratique de regrouper par analyses dans les données. Prenons les exemples de données suivants:

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

La variable x a trois exécutions: une longueur de 2 avec une valeur de 1, une longueur de 3 avec une valeur de 2 et une longueur de 1 avec une valeur de 1. On peut calculer la valeur moyenne de la variable y dans chacun des exécutions de la variable x (ces valeurs moyennes sont 1,5, 4 et 6).

La fonction data.table rleid fournit un identifiant indiquant l'identifiant d'exécution de chaque élément d'un vecteur:

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

On peut alors facilement regrouper sur cet identifiant et résumer les données y :

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

Encodage de longueur d'exécution pour compresser et décompresser les vecteurs

Les vecteurs longs avec des longueurs élevées de la même valeur peuvent être compressés de manière significative en les stockant dans leur codage de longueur (la valeur de chaque exécution et le nombre de fois où cette valeur est répétée). À titre d'exemple, considérons un vecteur de longueur 10 millions avec un grand nombre de 1 et seulement un petit nombre de 0:

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

Stocker 10 millions d'entrées nécessitera beaucoup d'espace, mais nous pouvons créer un bloc de données avec l'encodage de longueur de ce vecteur:

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

À partir de l'encodage, nous voyons que les 52 818 premières valeurs du vecteur sont des 1, suivies d'un seul 0, suivies de 219 329 1 consécutives, suivies d'un 0, etc. Le codage de longueur d’exécution ne contient que 207 entrées, ce qui nous oblige à ne stocker que 414 valeurs au lieu de 10 millions de valeurs. Comme rle.df est un rle.df données, il peut être stocké à l'aide de fonctions standard telles que write.csv .

La décompression d'un vecteur en codage par longueur d'exécution peut être réalisée de deux manières. La première méthode consiste à appeler simplement rep , en passant l’élément de values du codage d’exécution comme le premier argument et l’élément lengths du codage d’exécution comme second argument:

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

Nous pouvons confirmer que nos données décompressées sont identiques à nos données d'origine:

identical(decompressed, dat)
# [1] TRUE

La seconde méthode consiste à utiliser la fonction inverse.rle intégrée à inverse.rle sur l'objet rle , par exemple:

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

Nous pouvons confirmer à nouveau que ce produit exactement l'original dat :

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