Codage RLE

Le système de codage RLE (Run Length Encoding ou codage par longueur des plages), est certes ancien, mais a longtemps été utilisé dans les transmissions par fax.

L’image ci-contre est codée par les nombres figurant à sa droite.

Expliciter le codage employé

Quel est le taux de compression de cette image ?

S’agit-il d’un système de compression avec ou sans pertes ?

Algorithme

Soit l’image implémentée en Python à l’aide d’une liste de listes :

img = [[0,1,1,1,0],
       [0,0,0,0,1],
       [0,1,1,1,1],
       [1,0,0,0,1],
       [1,0,0,0,1],
       [0,1,1,1,1],
      ]

On se propose de coder cette image sous la forme d’une autre liste de listes, nommée rle  et qui aura après exécution de l’algorithme la valeur suivante :

[[1, 3, 1], 
 [4, 1], 
 [1, 4], 
 [0, 1, 3, 1], 
 [0, 1, 3, 1], 
 [1, 4]]

Implémenter cet algorithme de codage en Python.

Calculer l’ordre de complexité de cet algorithme.