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.

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 */ 
    }
}

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.

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

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.

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

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 */
        }
    }
    
}

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:

• [fghijklmnopqrst00000, fghijklmnopqrst10000[ pour le bit 0, et
• [fghijklmnopqrst10000, fghijklmnopqrst11111+1[ pour le bit 1.

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 */
    }
}

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.

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 b₀, b₁, b₂, … Étant donnés les i premiers bits b₀, …, b_i − 1, le prédicteur prédit le prochain bit, on note p_i la prédiction. Définissons a_i = 1 si b_i = p_i et a_i = 0 sinon. La suite des a_i est le flux transformé.

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

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 :

• quand on reçoit 11111111, c’est-à-dire que le prédicteur a vu juste huit fois de suite, on émet un bit 1;
• quand on reçoit 1...1 (avec k bits, 0 ≤ k < 8) suivi de 0, c’est-à-dire que le prédicteur a vu juste k fois puis s’est trompé, on émet 0 suivi de k codé sur quatre bits.
• si le flux d’entrée termine par une série en cours de sept bits 1 ou moins, on fait comme si elle était suivie d’un zéro.

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 */
    }
}

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.

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, 0100 → 4, 0101 → 5, 0011 → 3, 1 → 8, 0010 → 2 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;
        }
    }
}

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();
    }
}