Dyrk

Coucou la compagnie !

Tout d'abord, je m'excuse de n'avoir pas eu le temps de vous écrire hier ...
J'ai aujourd'hui un sujet plutôt fun à aborder avec vous qui est la "compression".

Comment un fichier peut-il perdre 10%, 20%, 30%, ... de sa taille ?

Haha, je vous propose que nous analysions ceci ensemble.
Aussi, pour ce sujet j'ai réalisé un petit algorithme pour compresser du texte.

L'idée :

Nous avons une phrase.
Il faut découper cette phrase en mots
Ne garder que les mots uniques.
Stocker la position des doublons par rapport à celle de la première occurrence.

Graphiquement ça donne ceci

Notre phrase ici est :

ABCD BAC CDAD DCB ABCD DA BAC BAC

Ce qui nous donne 33 caractères (en incluant les espaces)
En ne gardant que les mots uniques nous obtenons ceci :

ABCD BAC CDAD DCB DA

Donc nous supprimons :

ABCD BAC BAC

Soit 12 caractères.
Néanmoins, nous devons quand même savoir qu'il existe et où il se place.
D'où l'importance de récupérer et stocker quelque part leurs positions.
On va donc se baser sur la première position de ces doublons.

ABCD est le premier mot, la prochaine occurrence de ABCD est quatre mots plus loin,
J'enregistre :

ABCD:4

BAC est le deuxième mot, la prochaine occurrence de BAC est cinq mots plus loin,
J'enregistre :

ABCD:4
BAC:5

Sachant qu'il y 'a 2 occurrences de BAC, j'enregistre l’occurrence suivante qui est à six mots de la première :

ABCD:4,
BAC:5,6

... si bien qu'a la fin, je me retrouve avec ceci :

ABCD:4
BAC:5,6
CDAD
DCB
DA

En compressant le tout, je me retrouve avec ceci :

ABCD:4-BAC:5,6-CDAD-DCB-DA

Soit 26 caractères !

Nous venons donc de passer d'un texte de 33 à 26 caractères soit une réduction de taille d'environ 22%

Pour décompresser ce texte, je n'aurais plus qu'à lire dans l'autre le texte compressé, en réajustant les positions lorsqu'il est indiqué l'emplacement d'un mot.

Bien sur ça reste de la théorie et j'ai simplifié les choses ;)
Il y a un million de façon de compresser les données, néanmoins, j'espère vous avoir apporté ici, une compréhension du fonctionnement et du type de méthodologique qui peut être appliquée.

Je vous offre donc 2 fonctions de javascript que j'ai écrite rien que pour vous afin de réaliser cette compression :

function chr(codePt) {

  if (codePt > 0xFFFF) { 

    codePt -= 0x10000;

    return String.fromCharCode(0xD800 + (codePt >> 10), 0xDC00 + (codePt & 0x3FF));

  }

  return String.fromCharCode(codePt);

}





CompressAscii = function (txt){

    tab = new Array(); buff=""

    while (txt.indexOf('  ') != -1) txt = txt.replace('  ', ' ');

 	txt = txt.split(" ");   

    for (i in txt){

        if (! tab[txt[i]] && tab[txt[i]] != ""){

        	 tab[txt[i]]="";

             for (j=parseInt(i)+1; j<= txt.length; j++)

              	if ( txt[i] == txt[j])

                 	  tab[txt[i]]+=(j-i)+chr(170); 

        }        

    }

    for (i in tab){

     buff += i+chr(172)+ tab[i].substr(0,tab[i].length-1)   +chr(171)

    }

    return buff;

}



UnCompressAscii = function (txt){

    tab = new Array(); buff="";x=0;

    txt = txt.split(chr(171));   

    console.log(txt);

    for (i in txt){

        b = txt[i].split(chr(172));

        word = b[0];

        if (tab[x]) while (tab[++x]);  

        tab[x++] = word;

        if (! b[1])  continue;

        bloc = b[1].split(chr(170));

        for (j in bloc) tab[parseInt(bloc[j])+x-1] = word;

    }

    for (i in tab){

     buff += tab[i] + " ";

    }

    return buff;

}

Petit exemple d'utilisation :

txt = "les cochons aiment manger du chocolat, car le chocolat ne vient pas du cochon, et le cochon c'est bon ! Ma maman c'est la reine du chocolat, cependant le chocolat doit se manger doucement";



//On compresse ici

cp  = CompressAscii(txt);



//On decompresse là

ucp = UnCompressAscii(cp);





//On observe le résultat !



console.log("======= COMPRESSED =====");

console.log(cp.length + "/" + txt.length);



console.log("====== UNCOMPRESSED ===");

console.log(ucp.length + "/" + txt.length);

console.log("Decompresse :"+ucp);





console.log("======= ORIGINAL ========");

console.log("Original    :"+txt);

Résultat ...