Quand un semi geek non spécialiste de la compression de données rencontre un autre semi geek également non spécialiste de la compression de données, et qu'ils évoquent un programme de compression de données écrit par l'un d'entre deux, ça donne quoi ? Ca donne ça.

Compression

Bouba, quand avez-vous commencé à vous intéresser à la compression ? J'ai commencé en 2006, je suis tombé par hasard sur le prix Hutter et je me suis dit bon tu gagneras jamais, mais voilà l'occasion de faire un peu de vraie informatique. A l'époque je m'étais même dit étant donné qu'il s'agit de compresser un fichier bien spécifique, j'ai même peut-être une chance infime d'arriver à quelque chose. Ce qui s'est avéré fort naïf. Je vois... Sans entrer dans les détails, quelles ont été les étapes les plus marquantes de votre approche pendant ces trois années. Tout d'abord il faut préciser une chose, j'ai été confronté à 2 types d'éléments marquants : 1. les évolutions conceptuelles en terme de taux de compression (quand c'est meilleur, ça fait plaisir) 2. les évolutions en terme de temps d'execution (quand c'est meilleur, ça fait extremement plaisir : quand la durée d'un test passe de 15 minutes à 30 secondes, c'est très agréable et cela permet de tatonner plus facilement pour la suite). Mais étrangement, jusqu'à un certain point, un meilleur taux de compression va avec de meilleurs performances. C'est ce qui est le plus troublant dans tout cela. Sinon pour les lister sans trop de details : 1. Création d'une classe d'arbre de Huffman qui marche. 2. Création d'un détécteur de répétition qui marche et qui est très performant. 3. Création d'un arbre de Huffman performant avec des poids qui changent dynamiquement (des dizaines d'heures de boulot) 4. Gestion d'un dictionnaire qui s'auto-rempli à la volée en fonction des "mots" qui arrivent souvent. 5. Abandon des dictionnaires de longs mots au profit d'un profilage en regardant les caractères précédents (au lieu d'avoir tous les mots de 5 lettres dans mon dictionnaire, pour chaque mot de 5 lettres j'ai juste les probabilités de chaque caractère suivant) 6. Découverte du codage arithmetique : qui rend l'arbre de Huffman ridicule à tout point de vue : espace memoire, utilisation CPU (du moins avec des données dynamiques), taux de compression. 7. Création d'un codeur / décodeur arithmetique qui marche et qui est performant (la aussi des dizaines d'heures). A ce stade j'avais en fait réinventé (sauf le codage arithmétique) la compression PPM (Prediction by Partial Matching) 8. Mise en place d'un vrai PPM très performant. Cela a été facilité par le fait d'avoir trouvé un autre couillon à en avoir codé un aussi en java et le battre en terme de performance semblait être un objectif atteignable. Par contre, étrangement, mes taux de compression sont un peu meilleurs, ce que je n'espérais pas. Ouaourche !! je pense qu'à partir de là, on est tranquille : y a plus que deux geeks égarés qui nous lisent. Mais c'est pour eux qu'on va faire notre maximum. Pour commencer, pouvez-vous nous expliquer le plus simplement possible ce qu'est un arbre de Huffman ? L'arbre de Huffman est une technique pour encoder en binaire des mots en fonction de leur fréquence, le but de la compression est d'utiliser moins de 0 ou 1 pour coder l'ensemble des mots. L'arbre de Huffman est une manière de faire en sorte que les mots les plus fréquents soient codés sur peu de booléens en désavantageant les mots moins fréquents. L'intérêt de ce type de codage est que c'est un codage par "symbole", la correspondance entre code binaire et les mots est bijective. L'algorithme de construction de l'arbre en fonctions des poids assure que c'est le meilleur codage par symbole possible. Un exemple sera plus explicite : BETTYBOOP ci-dessous la fréquence de chaque caractère : B 2 E 1 T 2 Y 1 O 2 P 1 Quand on construit l'arbre de Huffman cela nous donne cela : 00 B 01 T 10 O 1100 E 1101 Y 111 P Si on utilise cet arbre de Huffman, en écriture quand on rencontre un B on écrit 00, en lecture quand on rencontre 00 on lit B. BETTYBOOP s'écrira en binaire comme suit : 00110001011101001010111, soit 23 booléens, on peut faire l'exercice inverse et on retrouvera BETTYBOOP. Bien sûr, pour la compression, ce n'est pas si simple. Comment avoir les bons poids pour le fichier que l'on veut compresser, alors qu'on ne l'a pas encore lu ? Solution 1 : on utilise des arbres en dur en fonction du type de fichier que l'on veut compresser (pour les fichiers HTML, on va mettre un poids important aux "<" et ">", cela avait d'ailleurs été mis en place dans les premiers modems) Solution 2 : on lit le fichier pour compter les fréquences, on construit l'arbre et on recommence, mais cela nécessite de stocker les décomptes dans le fichier de sortie pour que l'on puisse reconstruire le même arbre à la décompression. Et oui, à la décompression, on ne peut pas compter les fréquences du fichier original puisqu'on ne l'a pas. Solution 3: on modifie l'arbre à la volée : à chaque fois que l'on rencontre un A (en lecture ou écriture) on incrémente la fréquence de A. Cela donne à peu près les mêmes taux de compression que la solution 2, mais c'est nettement plus gourmand en calcul : construire l'arbre de Huffman n'est pas si rapide. C'est lumineux. Du moins pour les solutions 1 et 2. En revanche, je ne suis pas certain de bien comprendre la solution 3. D'abord, quel avantage présente-t-elle si elle a permet de compresser avec le même taux que la solution 2, et qu'elle est plus gourmande en calcul ? L'avantage de la solution 3 est qu'elle ne nécessite pas de lire le fichier 2 fois. Elle est donc "streamable", ce qui peut avoir un intêret dans le monde réseau. Mais comme un arbre de Huffman adaptable est trop gourmand en calcul, il convient d'utiliser un autre système d'encodage. D'où l'intérêt du codage arithmétique, qui lui, est plus gourmand qu'un arbre de Huffman figé, en terme de codage et décodage car il ne s'agit pas d'une bijection entre les "mots" et des séquences de bits mais le résultat de calcul arithmétique (d'où son nom). Mais par contre, il est très performant en terme d'adaptabilité des fréquences : pour incrémenter un poids, il ne faut pas recalculer un arbre mais juste... incrémenter le poids. De plus, le codage arithmétique donne toujours un meilleur taux de compression que l'arbre de Huffman (sous réserve que les poids soient justes). En fait, le codage de Huffman dans le meilleur des cas peut donner les mêmes taux si et seulement si tous les poids des feuilles / noeuds / racines de l'arbre sont des puissances de 2 (ce qui en pratique n'arrive jamais). Exemple : si A à un poids de 31 et B un poids de 1 l'arbre de Huffman sera le suivant : 0 A 1 B C'est le même que si les poids était inversés, et on utilise alors 1 bit par mot. Alors qu'avec le codage arithmétique (je ne détaillerai pas le calcul) on aura 0,2 bit par mot. Ce serait tout de même dommage qu'on ne puisse pas tirer partie du fait que A apparaisse 31 fois plus que B. Le codage arithmétique, comment ça marche ? En fait, il s'agit de coder la probabilité globale du fichier en un seul et gigantesque nombre entre 0 et 1 (une probabilité globale pour le fichier). Pour l'exemple A 31, B 1, on a en fait deux intervalles : A [0, 31/32] B [31/32, 1] Au départ, l'encodeur arithmétique a pour intervalle [0,1]. On a un A, l'intervalle devient [0, 31/32]. On a encore un A : on place l'intervalle de A dans celui de l'encodeur on obtient [0, (31*31)/(32*32)] etc... Un schéma ici éclaircira la chose même si ce ne sont pas les poids de l'exemple. L'encodeur ecrit en fait un chiffre se trouvant dans l'intervalle. Ainsi quand le décodeur lit ce chiffre il est toujours capable de savoir quel intervalle parmis celui a A ou B (ou plutot les N) à permis de l'encoder. Qu'est-ce que le PPM ? Le PPM (Prediction by Partial Matching) est un mode de compression qui consiste en cela : on accumule en mémoire le nombre d'occurrences de chaque caractère en fonction des caractères précédents. Et on se sert de ces données pour "calculer" les probabilités de chaque caractère. Prenons l'exemple PPM(1) : Imaginons la chaine ABAA 1. A Je n'ai pas de caractère précédent, j'ai un contexte "racine" qui est initialisé avec un poids de 1 pour chaque caractère possible. Je code le A, et j'augmente le poids de A dans ce contexte racine. 2. B J'ai un caractère précédent (le A) mais il n'a jamais été suivi par quoi que soit et ne comporte donc aucune information. Je ne m'en sers donc pas et j'utilise le contexte "racine" pour coder le B. J'augmente le poids de B dans ces deux contextes. 3. A même topo 4. A J'ai un caractère précédent qui a déjà été suivi par quelque chose il est donc utilisable (une fois par B). Or ce contexte n'a jamais vu A, il ne peut pas le coder, il code donc "Je ne sais pas". On va se servir alors du contexte racine pour coder le A mais avec un raffinement supplémentaire. Le contexte précédent nous a dis "je ne sais pas" or on sait qu'il connait B, donc on sait que ce n'est pas B. On code donc le A avec le contexte racine dont on exclu la probabilité de B. J'augmente le poids de A dans ce contexte et dans le contexte racine. Un PPM(0) n'utilise en fait que le contexte racine tous le temps. Un PPM(N) va garder tous ces contextes pour les longueurs de chaine allant de 0 (racine) à N caractères. C'est pourquoi ce procédé utilise énormément de mémoire. Par contre, il y a quelque chose que je n'arrive pas vraiment à élucider : mon PPM(9) compresse moins bien que mon PPM(8). Bon, on arrête les frais ? Je vous propose de balourder l'exécutable et ses sources, histoire d'être débarrasé de ces problèmes qui m'ont l'air bien compliqué et de reprendre des activités saines. Ca marche. Tout est là.