Intrigué par les algorithmes de compression de données, je me suis penché sur RLE qui est sans conteste l'un des moins complexe à implémenter. Il s'applique aux données qui présentent de longues répétitions d'un même caractère. Le principe consiste à ne conserver qu'un seul caractère de chaque plage auquel on préfixera le nombre réel de répétitions attendues. Par exemple :

AAAABBBBBBCDDDDDEEEEEEEEE (25 octets)

devient

4A6B1C5D9E (10 octets)

Dans ce cas bien choisi le niveau de compression est intéressant, mais loin d'être systématiquement satisfaisant : l'algorithme s'avère en effet très peu approprié aux données qui ne présentent pas de répétitions suffisantes. Ainsi :

ABCDE (5 octets)

devient

1A1B1C1D1E (10 octets)

On voit clairement que RLE ne peut être envisagé que dans des domaines d'application bien précis pour pouvoir en espérer un quelconque bénéfice. Initialement inventé pour compresser les documents scannés en noir et blanc (qui présentent inévitablement de longues plages d'octets "blancs"), on peut l'appliquer au cas typique des images bitmaps formées de grandes zones d'une couleur unie. Ces pixels contigus dont le code couleur est identique se traduiront dans le fichier par une suite consécutive d'octets identiques.

Pour illustrer ce principe, j'ai testé la compression du fichier bitmap ci-contre. La compression RLE a permi de réduire le poids du fichier de 67.3 Ko à 9.1 Ko, c'est qui est déjà appréciable.
Ce qui laisse rêveur, c'est d'imaginer l'inventivité mise en oeuvre par le format PNG, pour arriver avec ce même fichier source à un résultat final d'à peine 400 petits octets !

Ma classe PHP

/**
 * "Run-length encoding" algorithm compression class
 *
 * @author  Geoffray Warnants - http://www.geoffray.be/
 * @version 1.0
 */
class RLE
{
    /**
     * Compress a string using RLE
     *
     * @param   string  $str
     * @return  string
     */
    public static function encode($str)
    {
        $encoded = '';
        for ($i=0, $l=strlen($str), $cpt=0; $i<$l; $i++) {
            if ($i+1<$l && $str[$i]==$str[$i+1] && $cpt<255) {
                $cpt++;
            } else {
                $encoded .= chr($cpt).$str[$i];
                $cpt = 0;
            }
        }
        return $encoded;
    }
    
    /**
     * Uncompress a RLE string
     *
     * @param   string  $str
     * @return  string     
     */
    public static function decode($str)
    {
        $decoded = '';
        for ($i=0,$l = strlen($str); $i<$l; $i+=2) {
            if ($i+1<$l && ord($str[$i]) > 0) {
                $decoded .= str_repeat($str[$i+1], 1+ord($str[$i]));
            } else {
                $decoded .= $str[$i+1];
            }
        }
        return $decoded;
    }
}

<<< Retour