Arbres de Fenwick et compression

INF411 · TD6

 Login :  Mot de passe :

Exprimez-vous

Objectifs

La compression des données est un outil pour améliorer l’efficacité du stockage et des transmissions. L’objectif de ce TD est d’implémenter un algorithme de compression générique et sans perte, comme celui de gzip par exemple.

Si après avoir traité les questions 1 et 2 il ne vous reste que peu de temps, passez directement au bonus B.

 

Pour commencer:

1 — Arbres de Fenwick

Le but de cet exercice est de construire une structure de données, appelée arbre de Fenwick, qui représente – sans le stocker directement – un tableau d’entiers avec des indices dans [L, H[ et munie de deux opérations :

void inc(int i)
ajoute 1 à l’élément d’indice i du tableau représenté par this; ne fait rien si i n’est pas dans [L, H[.
int cumulative(i)
renvoie la somme de tous les éléments du tableau représenté par this avec des indices dans ] − ∞, i[ ∩ [L, H[.

On peut penser à deux implémentations naïves. La première incrémente la case a[i] d’un tableau int[] a à chaque appel de inc(i) (temps constant) ; cumulative(i) renvoie la somme des a[j] pour 0 ≤ j < i (temps linéaire en H − L).

La seconde stocke directement les valeurs de tous les cumulative(i), de sorte que cumulative(i) est calculé en temps constant mais c’est inc qui s’exécute en temps linéaire.

Un arbre de Fenwick assure un coût O(log (H − L)) à ces deux opérations en stockant quelques sommes partielles bien choisies. Un arbre de Fenwick sur l’intervalle [L, H[ est un arbre binaire équilibré où chaque nœud a 0 ou 2 fils. Les feuilles sont associées aux indices du tableau représenté par l’arbre et contiennent les valeurs correspondantes. Les nœuds internes sont associés à des intervalles et contiennent la somme des éléments du tableau sur cet intervalle. Les intervalles sont choisis de sorte que la valeur contenue dans un nœud interne soit la somme des valeurs des deux fils.

Le schéma ci-dessous illustre un arbre de Fenwick sur l’intervalle [0, 19[ représentant le tableau [2, 2, 3, 1, 0, 0, 1, 1, 2, 0, 1, 3, 4, 2, 0, 0, 2, 1, 3].

Schéma d’un arbre de Fenwick

 

Constructeur

class Fenwick {
    private final Fenwick left;
    private final Fenwick right;
    private final int lo;
    private final int hi;
    private int acc;

    Fenwick(int lo, int hi) {
        /* TODO */
    }
}

Les nœuds d’un arbre de Fenwick sont associés à un intervalle entier [lo, hi[. Les fils d’un nœud interne sont associés respectivement à des intervalles disjoints [lo, A[ et [A, hi[ pour A = (lo+hi)/2. Les feuilles de l’arbre correspondent aux intervalles singletons [i, i+1[.

De plus, chaque nœud contient un accumulateur acc initialisé à zéro.

Écrire le constructeur Fenwick. Il contiendra des appels récursifs pour construire les fils, le cas échéant.

Tester le code en exécutant Fenwick.java puis déposer Fenwick.java.

Le nom du fichier à déposer
Il faut se connecter avant de pouvoir déposer

Méthode get

Pour se familiariser avec la structure de l’arbre, on peut, par exemple, chercher les feuilles de l’arbre comme dans un arbre binaire de recherche (voir les diapos de l’amphi 5). On peut le faire itérativement ou récursivement.

class Fenwick {
    ...
    Fenwick get(int i) {
        /* TODO */ 
    }
}

Écrire la méthode get(i) qui renvoie la feuille associée à l’intervalle singleton [i, i+1[ si elle existe et null sinon.

La complexité doit être bornée par la profondeur de l’arbre.

Tester le code en exécutant Fenwick.java puis déposer Fenwick.java.

Le nom du fichier à déposer
Il faut se connecter avant de pouvoir déposer

Méthode inc

L’accumulateur acc d’un nœud associé à l’intervalle [lo, hi[ est la somme des éléments d’indices dans [lo, hi[ du tableau représenté par l’arbre.

Un appel inc(i) incrémente les accumulateurs de tous les nœuds de l’arbre associés à un intervalle contenant i. L’appel ne fait rien si i n’est pas dans [lo, hi[. On implémentera cette méthode avec des appels récursifs.

Le shéma ci-dessous illustre l’appel inc(12). Les flèches jaunes représentent les appels récurstifs. Les nœuds jaunes ont reçu un appel inc(12), incrémenté leur compteur et transmis l’appel à leurs fils. Les nœuds beiges ont reçu un appel inc(12) mais n’ont rien fait.

Appel inc(12) dans un arbre de Fenwick

 

class Fenwick {
    ...
    void inc(int i) {
        /* TODO */ 
    }
}

Écrire la méthode inc.

La complexité doit être bornée par la profondeur de l’arbre.

Tester le code en exécutant Fenwick.java puis déposer Fenwick.java.

Le nom du fichier à déposer
Il faut se connecter avant de pouvoir déposer

Méthode cumulative

La méthode cumulative(i) renvoie la somme des éléments aux indices strictement inférieur à i du tableau représenté par l’arbre. On remarque que si le nœud courant a des fils, alors cumulative(i) est égal à left.cumulative(i) + right.cumulative(i). Mais selon la valeur de i un calcul sans récursion est parfois possible.

Le schéma ci-dessous illustre l’appel cumulative(13). Il renvoie 21, la somme des nœuds jaunes (12+1+3+5), qui est aussi la somme des feuilles numérotées de 0 à 12. Les flèches jaunes représentent les appels récursifs. Les nœuds jaunes et beiges n’ont pas eu besoin de récursion pour renvoyer le résultat.

Appel cumulative(13) dans un arbre de Fenwick

 

class Fenwick {
    ...
    int cumulative(int i) { 
        /* TODO */
    }
}

Écrire la méthode cumulative.

La complexité doit être bornée par la profondeur de l’arbre.

Tester le code en exécutant Fenwick.java puis déposer Fenwick.java.

Le nom du fichier à déposer
Il faut se connecter avant de pouvoir déposer

2 — Le prédicteur

Pour l’application qui nous intéresse, les flux de données seront lus bit par bit. Un bit est représenté par un booléen (0 → false, 1 → true). On implémente maintenant une classe Predictor avec comme méthodes d’instance:

void write(boolean bit)
collecte des données statistiques sur les bits qui lui sont transmis,
boolean predictBit()
renvoie le bit qui va probablement suivre, selon les données statistiques recueillies par write.

Les données non compressées sont typiquement alignées sur des octets, c’est pour cela qu’on ne met à jour l’arbre de Fenwick qu’à la réception d’un octet complet.

Plus wordsize est grand, plus il faut de mémoire et plus les statistiques sont fines.

Pour définir le modèle statistique, on fixe d’abord une longueur de mot wordsize (mettons 20 bits). Chaque instance de Predictor est équipée d’un arbre de Fenwick freq pouvant compter des entiers dans l’intervalle [0, 2wordsize[. Quand le nombre de bits reçus est un multiple de 8, write appelle freq.inc(i)i est l’entier formé des wordsize derniers bits reçus.

Méthode write

class Predictor {
    private int wordsize;
    private int bits;
    private int data;
    Fenwick freq;

    Predictor(int wordsize) { ... }

    private int mask(int i) {
        /* TODO */
    }
    
    void write(boolean bit) {
        bits++;
        /* TODO */
        if (bits == 8) {
            /* TODO */
        }
    }
    
}

Écrire une méthode mask(i) qui renvoie le reste de la division euclidienne de i par 2wordsize. Autrement dit, mask(i) met à zéro les bits de poids fort de i, en ne conservant que les wordsize bits de poids faible. Boucles interdites. Par exemple, avec wordsize = 8 :

  • mask(101101001110) = 000001001110

On pourra utiliser les opérateurs bit << et &, voir les diapos de l’amphi 2.

Tester le code en exécutant Predictor.java puis déposer Predictor.java.

Le nom du fichier à déposer
Il faut se connecter avant de pouvoir déposer

Écrire la méthode write. Elle accumule les bits reçus dans la variable data. Si à un instant donné data = 000000000000abcdefghijklmnopqrst (en notation binaire sur 32 bits, où les lettres représentent des zéros ou des uns), alors après l’appel write(u) on a data = 000000000000bcdefghijklmnopqrstu. Tous les bits sont décalés à gauche, u est ajouté à droite et le bit a est effacé avec mask.

De plus, on maintient un compteur bits qui compte le nombres de bits reçus dans l’octet en cours. Quand l’octet est complet, on appelle freq.inc(data).

Tester le code en exécutant Predictor.java puis déposer Predictor.java.

Le nom du fichier à déposer
Il faut se connecter avant de pouvoir déposer

Illustration de la méthode write

 

Methode predictBit

Mettons qu’il reste cinq bits (c’est-à-dire bits = 8 - 5) pour compléter l’octet en cours et que data = 000000000000abcdefghijklmnopqrst. Alors si le prochain bit est 1, on aura data = 000000000000fghijklmnopqrst1???? à la fin de la réception de l’octet en cours avec des bits inconnus ?. De même, si le prochain bit est 0, alors on aura data = 000000000000fghijklmnopqrst0????. Ces deux possibilités correspondent à des intervalles disjoints, en l’occurence:

L’arbre de Fenwick, avec sa méthode cumulative, permet de savoir laquelle des deux possibilités est arrivée le plus fréquemment par le passé. Pour des valeurs lo, mid et hi bien choisies, predictBit() renvoie freq.cumulative(hi) - freq.cumulative(mid) > freq.cumulative(mid) - freq.cumulative(lo).

Pour le débogage, utilisez la méthode printBin(int a) pour afficher en base deux un entier.

class Predictor {
    ...
    boolean predictBit() {
        /* TODO */
    }
}

Écrire la méthode predictBit.

Tester le code en exécutant Predictor.java puis déposer Predictor.java.

Le nom du fichier à déposer
Il faut se connecter avant de pouvoir déposer

Le test utilise le texte complet de La Science et l’Hypothèse d’Henri Poincaré. On devrait observer un taux de prédiction des bits de 86% avec wordsize=16.

3 — Compression

On peut montrer que si le taux de prédiction est p ∈ [0, 1], on peut espérer un taux de compression de  − plog2(p) − (1 − p)log2(1 − p). Pour p = 86%, c’est environ 47%, c’est-à-dire que le fichier compressé ferait 47% de la taille originale. (Voir « Entropie de Shannon ».)

Si le prédicteur a un bon taux de prédiction, c’est que l’information est redondante. L’algorithme de compression essaie d’en tirer parti pour compresser un flux de données.

On utilise dans cette partie les classes BinaryIn et BinaryOut qui permettent respectivement de lire et d’écrire des données un bit à la fois. On lit et on écrit de gauche à droite comme d’habitude.

Première transformation

Cette transformation est intéressante car elle est inversible. De plus, si le prédicteur a un bon taux de prédiction, le flux transformé contiendra beaucoup plus de 1 que de 0. C’est ce sur quoi s’appuiera la compression.

Supposons que l’on reçoive un flux de bits b0, b1, b2, … Étant donnés les i premiers bits b0, …, bi − 1, le prédicteur prédit le prochain bit, on note pi la prédiction. Définissons ai = 1 si bi = pi et ai = 0 sinon. La suite des ai est le flux transformé.

class Predictor {
    ...
    boolean encode(boolean b) {
        /* TODO */
    }
    boolean decode(boolean a) {
        /* TODO */
    }
}

Écrire la méthode encode telle que sur les entrées successives b0, b1, b2, … elle renvoie successivement a0, a1, a2, ….

Tester le code en exécutant Predictor.java.

Écrire la méthode decode telle que sur les entrées successives a0, a1, a2, … elle renvoie successivement b0, b1, b2, ….

Tester le code en exécutant Predictor.java puis déposer Predictor.java.

Le nom du fichier à déposer
Il faut se connecter avant de pouvoir déposer

Seconde transformation

Cette deuxième transformation est en partie arbitraire. Elle est particulièrement adaptée si le taux de succès du prédicteur est d’environ 90%, ce qu’on observera sur des fichiers contenant principalement du texte. Le cours sur les arbres de Huffman vous en dira plus.

Partant de l’idée que la première transformation produit un flux avec beaucoup de 1, on propose la transformation suivante, à faire à la suite de la première :

Par exemple, si on reçoit 111101111100011101111111111, on coupe après chaque 0 ou après huit 1 consécutifs, ce qui donne 11110, 111110, 0, 0, 1110, 11111111, 110 (avec un zéro ajouté artificiellement au dernier). Puis on émet 0100, 0101, 0000, 0000, 0011, 1, 0010.

Les instances de la classe Encoder initialisent un prédicteur pred et encodent tout bit lu avec la méthode pred.encode pour effectuer la première transformation.

class Encoder {
    private Predictor pred;
    private BinaryOut out;

    Encoder(BinaryOut out) { ... }
    encode(BinaryIn in){
        /* TODO */
    }
}

Écrire la méthode encode.

in.readBoolean()
Lit un bit.
out.write(int i, int r)
Émet l’entier i codé sur r bits.
in.isEmpty()
Vaut true si et seulement s’il reste des bits dans l’entrée.

Tester le code en exécutant Encoder.java puis déposer Encoder.java.

Le nom du fichier à déposer
Il faut se connecter avant de pouvoir déposer

Le test de la compression utilise le texte de la licence GPLv3. On observe un taux de compression de 68%. De meilleures performances sont obtenues en augmentant wordsize. Sur des fichiers plus grand, l’apprentissage est plus performant.

Bonus A — Décompression

class Decoder {
    Predictor pred;
    private BinaryOut out;

    Decoder(BinaryOut out) { ... }
}

Tout comme Encoder, les instances de la classe Decoder initialisent un prédicteur. Pour la décompression, on procède en deux étapes.

Méthode readToken

Pour décoder un flux compressé, on commence par écrire une méthode int readToken(BinaryIn in). Elle lit un premier bit dans in. Si c’est 1, elle renvoie 8. Si c’est 0, elle lit les trois prochains bits et les renvoie sous la forme d’un entier dans [0,7]. Si elle ne parvient pas à lire trois bits quand elle le devrait (si l’entrée n’en contient plus que trois par exemple), readToken renvoie -1. Cette situation peut être détectée par l’exception NoSuchElementException levée par in.readInt.

Par exemple, 01004, 01015, 00113, 18, 00102 et 00.-1, où le point marque la fin du flux.

import java.util.NoSuchElementException;

class Decoder {
    ...
    int readToken(BinaryIn in) {
        try {
            /* TODO */
        } catch(NoSuchElementException e) {
            return -1;
        }
    }
}

Écrire la méthode readToken.

in.readInt(int r)
Lit un entier codé sur r bits. Lève l’exception NoSuchElementException s’il y a moins de r bits dans l’entrée.

Tester le code en exécutant Decoder.java puis déposer Decoder.java.

Le nom du fichier à déposer
Il faut se connecter avant de pouvoir déposer

Méthode decode

Pour finir le décodage et implémenter la méthode decode, on lit des entiers entre 0 et 8 en utilisant readToken. Sur un 8 on émet 11111111, et sur un k ∈ [0, 8[, on émet 1...10, avec k bits 1. Quand le flux est terminé ou quand readToken renvoie -1, on s’arrête.

Bien sûr, on n’oublie pas d’inverser la première transformation : quand on s’apprête à émettre un bit, on le décode au préalable avec pred.decode.

Enfin, la fin du flux est à étudier soigneusement. La compression peut produire un résultat avec un nombre de bits non multiple de 8. La classe BinaryOut rajoute alors automatiquement des zéros pour remplir le dernier octet (padding). C’est en lisant ces zéros que readToken peut renvoyer -1. Mais s’il y a quatre ou plus bits de padding, readToken renverra un 0 qui n’a en fait aucun sens. De même, lors de la compression, on est parfois amené à ajouter un 0 artificiel à la fin du flux qu’il ne faut pas émettre au décodage. Ces deux complications peuvent se traiter simplement. Elles ne peuvent pas produire plus de sept bits erronés à la fin du flux, pas de quoi remplir un octet. Ainsi, si on suppose que le nombre de bits des données originales (avant compression) est multiple de 8, il suffit de ne pas émettre l’éventuel octet incomplet. On appelle pour cela out.discardBuffer();

class Decoder {
    ...
    void decode(Binary in) {
        /* TODO */
        out.discardBuffer();
    }
}

Écrire la méthode decode.

Tester le code en exécutant Decoder.java puis déposer Decoder.java.

Le nom du fichier à déposer
Il faut se connecter avant de pouvoir déposer

Bonus B — Arbres de Fenwick creux

On propose une optimisation de l’implémentation des arbres de Fenwick. L’objectif est d’augmenter le paramètre wordsize pour améliorer les performances de la compression (vitesse et taux de compression) tout en gardant une utilisation raisonnable de la mémoire.

Voir aussi l’implémentation originale de Fenwick dans l’article «Fenwick tree» de Wikipedia.

Dans une utilisation typique de notre algorithme de compression, l’arbre de Fenwick du prédicteur est en fait très creux, la plupart des nœuds contiennent 0. Notons aussi que si un nœud contient 0, tous ses descendants aussi. Pour optimiser cela, on peut retarder l’initialisation des nœuds fils jusqu’au premier appel à inc.

Ainsi, si un nœud interne contient une valeur strictement positive, ses deux fils sont initialisés. Si un nœud interne contient 0, aucun de ses fils n’est initialisé.

Le schéma ci-dessous illustre un arbre de Fenwick creux après un appel inc(12). Les nœuds beiges n’existent pas encore en mémoire.

Schéma d’un arbre de Fenwick creux

 

public class FenwickSparse {
    private FenwickSparse left;
    private FenwickSparse right;
    private final int lo;
    private final int hi;
    int acc;

    public FenwickSparse(int lo, int hi) {
        this.lo = lo;
        this.hi = hi;
        acc = 0;
        left = null;
        right = null;
    }

    public void inc(int i) {
        /* TODO */
    }

    public int cumulative(int i) {
        /* TODO */
    }
}

Implémenter la classe FenwickSparse avec l’initialisation retardée.

La méthode FenwickSparse.inc est similaire à Fenwick.inc, sauf qu’elle initialise les fils s’ils ne le sont pas déjà avant de procéder aux appels résursifs. Les fils left et right sont toujours initialisés simultanément. Un nœud qui contient 0 a toujours deux fils null (que ce soit un feuille ou un nœud interne avec des fils non initialisés).

La méthode FenwickSparse.cumulative est similaire à Fenwick.cumulative sauf qu’elle ne tente jamais de descendre dans l’arbre au niveau d’un nœud qui contient 0 (elle renvoie 0 dans ce cas).

Tester le code en exécutant FenwickSparse.java puis déposer FenwickSparse.java.

Le nom du fichier à déposer
Il faut se connecter avant de pouvoir déposer

Avec cette implémentation, on peut aller jusqu’à wordsize=30. Au-delà, il faut changer le type de lo et hi en long, et on peut aller jusqu’à wordsize=62.

 


Proposition de solution : TD6.solutions.zip