Rapport 1

Structures de données

Structure de l'arbre (liste doublement chainée)

// Représente à la fois un noeud et une feuille
typedef struct t_noeud {
  struct t_noeud * parent;
  struct t_noeud * fg; // Fils gauche
  struct t_noeud * fd; // Fils droit
  char val; // Contient la lettre ASCII
  int ord_gal;
  int poids; // Poids de 'val'
} t_noeud, *ptr_t_noeud;

Tableau de pointeurs sur noeuds

Un tableau de 256 pointeurs (taille de la table ASCII) stockera le pointeur de chaque caractère (permet un parcours rapide lors des rééquilibrage).

Il sert à retrouver facilement un caractère dans le tableau et donc de savoir si celui-ci est déjà présent où non dans l'arbre (vaut NULL dans le cas où n'est pas présent).

ptr_t_noeud position_caractères[256];

Liste/tableau de l'ordre de Gallager

Est ordonné par ordre décroissant par rapport à l'ordre de Gallager et à la position des feuilles dans l'arbre (la plus à gauche aura l'indice le plus petit de ceux du même ordre qu'elle).

ptr_t_noeud ordre_gallager[256];

ou

ptr_t_liste ordre_gallager;

Vu que c'est ordonnée, on préférera un tableau ?

Problèmes soulevés

Détection de la fin de ficher - (résolu)

Sachant qu'il est impossible d'utiliser le caractère EOF car celui-ci peut se retrouver coder par accident par l'algorithme, il faut trouver un moyen de détecter la fin de fichier autrement.

Solution

On acquiert la taille du fichier que l'on veut lire grâce à fseek et on appel getc le même nombre de fois qu'il y a de caractères dans le fichier. Cela permet de ne plus avoir à se poser la question sur quel caractère on s'arrête puisque l'on a plus besoin de connaître leur valeur pou ça.

Ancienne solution (abandonnée)

Cause de l'abandon: problème de lecture de buffer, pour la fin du fichier il est impossible de savoir s'il faut lire tout le buffer ou non (cf. problème du caractère null).

La bibliothèque standard du C sur les entrées/sorties stdio.h a une fonction fgets qui permet de lire un certains nombre de caractères et ce jusqu'à la fin d'un fichier.

Écriture bit à bit

Il est impossible d'écrire bit à bit sur un support mémoire, il faut donc trouver le moyen d'écrire bit à bit à l'aide d'un octet.

Solution possible: utiliser un unsigned char qui fait office de buffer et un compteur. "Remplir" le unsigned char jusqu'à ce que le compteur atteigne 8, puis écrire le caractère dans le fichier et recommencer l'opération en ayant réinitialisé le compteur.

Se pose aussi la question: que faire si les derniers bits à écrire ne remplissent pas un octet ? (faire un bourrage ? mais comment faire en sorte que la fin de fichier soit toujours détectable (savoir qu'il ne faut pas prendre en compte le bourrage lors de la décompression) ?)

Caractère null

Lecture du buffer (plus d'actualité, plus de buffer utilisé)

Lors de la lecture du fichier, un buffer est utilisé. Le problème est que la présence de caractère null de la table ASCII peuvent causer des 'sauts' de caractères dans la lecture du buffer (celui-ci étant utilisé dans la condition d'arrêt de lecture du buffer).

Représentation caractère inconnu dans une feuille

Comment représenter un caractère inconnu vue que tous ceux de la table ASCII seront peut être lu dans le fichier ?

Solutions possibles

• Ajouter un booleen pour le type feuille qui permettrait de savoir si son caractère est inconnu ou non.
• Ne pas stocker les caractères dans un char mais dans un autre type (short?) qui permettrait d'avoir plus de valeurs et ainsi en définir une comme caractère null.
• Avoir la feuille qui vaut null (gérer le cas de la racine à part)

Problème des 2 premières solutions, la mémoire demandée par le programme va augmenter.

Lecture du fichier compressé

Comment s'y prendre pour lire le fichier compressé ?