23 Jan 2010

Les secrets de la compression

Category: Algo,Devadmin @ 14:46

La compression de données a toujours été un mystère pour vous ? Vous avez toujours souhaité en savoir plus sur les algorithmes et leurs secrets ? L’anglais ne vous fait pas peur ? Alors je vous conseille de lire la suite, et découvrir « Hacking Data Compression » écrit par Andy McFadden. C’est une documentation bien écrite et très instructive sur la manière de compresser efficacement des données.

Et si vous avez peur de l’anglais, ou si vous n’avez pas le temps de tout lire, j’ai écrit un (très court) résumé pour vous, qui reprend l’essentiel des trois premiers chapitres. Ça, c’est de la compression !

Voici le lien tant attendu : Hacking Data Compression. A ma connaissance, il n’y a pas de traduction en français de ses textes, mais si vous connaissez, faites-le partager dans les commentaires.

Une autre ressource que vous trouverez sûrement intéressante est un manuel sur le décryptage des formats de fichiers, en particulier des fichiers ressources, ces fameux fichiers utilisés dans les jeux ou les applications éducatives pour stocker les musiques, vidéos, sons, images… Document très intéressant à tout curieux du reverse engineering, le voici : The Definitive Guide To Exploring File Formats. Ce document a été écrit par les créateurs de MultiEx Commander et de Game Extractor, respectivement Mr.Mouse et WATTO.

Et maintenant, le résumé : Le secret d’une bonne compression n’est pas de chercher à encoder les caractères de la plus petite manière que ce soit (comme ce que j’avais tenté de faire avec mon programme PAK…), mais de faire en sorte d’avoir le moins de données à stocker, tout simplement. Et comment ? En étant prévisible ! Si je peux « deviner » les caractères à l’aide d’une suite logique ou de règles prédéfinies, alors je n’ai pas besoin de stocker cette information, car je peux la calculer. Exemple, les algorithmes qui utilisent des dictionnaires afin de ne pas répéter plusieurs fois un même gros bloc d’information. Rien que dans la page Wikipédia consacrée à l’algorithme de Huffman, nous retrouvons les termes « estimation des probabilités d’apparition des symboles », « modélisation probabiliste », « prédiction par reconnaissance partielle », « pondération de contextes »… autant de manières de deviner l’information plutôt que la stocker.

Je vous laisse découvrir le texte de McFadden, très bien écrit, pour tous les goûts (aussi bien les développeurs affamés de code que les théoriciens) et aux explications et aux exemples clairs (beaucoup plus clairs que moi).

Étiquettes : , ,

Laisser une réponse