Le principal facteur de ralentissement d'un algorithme de compression est la lecture du fichier d'entrée. Ce projet nous a permis d'étudier 2 types d'exploration, que nous allons présenter ici.
La première se plaçait en un point d'un fichier [POSITION], lisait les caractères précédents, et en cas de correspondance, venait se replacer en [POSITION+1] pour y lire le caractère suivant. Ensuite, la fonction revenait à nouveau en arrière pour y trouver d'éventuelle correspondances. Le nombre de lecture dans le fichier est ainsi tout à fait impressionant.
Principe de fonctionnement du "parcours lent".
int prem_occurence(FILE* entree,long position,long sauvegarde[4095])
/* Cette fonction retourne le nombre d'occurences du caractere situé à la case [position]
** dans le fichier [entree]. La position de chaque occurence est sauvegardee par l'intermediaire
** de l'indice du tableau sauvegarde[4095]
*/
int occurences(FILE* entree,int nombre_occur,long position,int longueur,long sauvegarde[4095])
/* Cette fonction est utilisee dans une boucle. Elle renvoie le nombre d'occurence
** d'une chaine de taille "longueur", commençant à [position]. Le tableau contient les
** caractères à étudier, et nb_occurence donne le nombre de case du tableau à étudier.
*/
Ensuite, on utilise ces deux fonctions dans le programme compression
void compression () {
[...]
nb_occurences=prem_occurence(entree,position,sauvegarde);
if(nb_occurences==0) {...}
//S'il n'y a pas d'occurence, on écrit le caractère
else {
longueur=1;
while(nb_occurences!=0 && longueur<18 ) {
nb_occurences=occurences(entree,nb_occurences,position,longueur,sauvegarde);
if(nb_occurences!=0) longueur++;
}
/* Enfin tant que l'on trouve des occurences et qu'on ne dépasse pas la taille
** maximum (ici 18), on continue de chercher des occurences.
*/
Cliquez-ici pour télécharger le détail de ces fonctions.
|
La seconde méthode optimise quelque peut l'exploration, tout simplement en créant un tableau de la taille maximum d'une chaîne pouvant être encodée. (Si notre algorithme ne peut encoder que des chaînes de longueur 18, alors on crée un tableau nommé BUFFER[17].)
Puis on parcourt le fichier en cherchant à chaque caractère à trouver la chaîne la plus longue possible. L'avantage ici est qu'on ne retourne pas lire à chaque fois les caractères de la chaîne "en entrée."
Principe de fonctionnement du parcours "amélioré".
void remplissage_buffer(FILE *entree, long position, char buffer[17])
/* Cette fonction remplit le buffer du caractere présent à [position] ainsi que
** des 16 caractères suivant.
** Ce tableau constitue le "buffer", c'est à lui qu'on comparera les chaînes lues
** dans le fichier.
*/
void compression() {
[...]
remplissage_buffer(entree,position,buffer);
for(int i=0;i
fseek(entree,position-maxbuff+i,SEEK_SET);
longueur_max=0;
for(int j=0;j<18;j++) {
char_en_cours=fgetc(entree);
if(char_en_cours==buffer[j]) {
longueur_max++;
}
else break;
}
if(longueur_max>=longueur) {
longueur=longueur_max;
taille_saut=maxbuff-i;
}
}
/* Ces quelques lignes montrent l'utilisation du buffer dans le parcours du fichier.
** Pour chaque caractère lu, on compare les suivant au buffer. Si on trouve une chaîne.
** convenable, on en mémorise la longueur et la position jusqu'à trouver une chaîne
** de meilleure "qualité" (plus longue, ou plus proche de [position]
*/
Cliquez-ici pour télécharger ces quelques lignes.
|
|