Facebook LinkedIn SourceForge Twitter RSS LastFM
logologo

La compression de données par RLE en PHP

Geoffray Warnants|28/05/2009|2 commentaires

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.

Piet Mondrian 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

Vos commentaires

1 commentaire posté

Syndrael
05/06/2009 09:00Posté par Syndrael
C'est vrai que la compression de données est un domaine des plus vaste. L'avantage de ton article est qu'il est à la portée de tous.. peut-être que cela titillera la curiosité de certains..

Réagir à cet article

*


(Ne sera pas publiée, servira uniquement à afficher votre gravatar)


(Lien en dur et dofollow)

zend framework