\documentclass[a4paper,twside, openright,12pt]{report} %twoside, openright

\usepackage[latin1]{inputenc}
\usepackage[francais]{babel}
\usepackage[T1]{fontenc}
\usepackage{graphics}
\usepackage{graphicx}
\usepackage{epic, eepic}
\usepackage{fancyheadings}
\usepackage{moreverb}
\usepackage[normalem]{ulem}
\usepackage{ecltree}
\usepackage{epsfig}
\usepackage{makeidx}


\pagestyle{fancy}

\lhead[]{PROJET TUTORE}
\rhead[]{Compression de textes} 
\lfoot[]{{\bf UMLV}}
\rfoot[]{juin 2001}
\setlength{\headrulewidth}{0.4pt}
\setlength{\footrulewidth}{0.4pt}



\title{ 
\begin{center}
{\rule{\textwidth}{0.5mm}}
PROJET TUTORE\\Compression de textes
{\rule{\textwidth}{0.5mm}}
\end{center}
\vspace{8,6  cm}
\begin{flushleft}
{\small Koku NOGLO, Gr\'egory LUGUAY, St\'ephane MEUNIER \& J\'er\^ome MORGADO}
{\rule{\textwidth}{0.5mm}}
\end{flushleft}
}
\date{}

\makeindex


\begin{document}
\maketitle

\strut\thispagestyle{empty} %tout ce qui suit c'est pour eviter d'avoir No1 au verso de la 1ere page
\vfill
\pagebreak

\setcounter{page}{1}

\tableofcontents

\pagebreak
\setcounter{page}{1}


\chapter*{INTRODUCTION}
\addcontentsline{toc}{chapter}{INTRODUCTION}
\vspace{2 cm}

Le but du projet est d'implanter deux m\'ethodes de compression de texte (sans perte d'information). La 1\textsuperscript{ere} est  bas\'ee sur l'utilisation d'un anti-dictionnaire
(lexique de mots interdits). La 2\textsuperscript{ème} consiste à établir un dictionnaire statique de mots (multigrammes) fréquents qui sont ensuite codés par des mots
courts. Apres avoir expliqué ces deux méthodes, nous verrons les avantages et les inconvénients de chacune d'elle. 


\chapter*{$\cal{I}$ - MANUEL DE L'UTILISATEUR}
\addcontentsline{toc}{chapter}{$\cal{I}$ - MANUEL DE L'UTILISATEUR}

\rhead{Manuel de l'utilisateur}

\section*{Compression à l'aide d'un dictionnaire}
L'ensemble du programme pourra être exécuté à tout moment en tapant la commande {\sf make}. Le nom de l'exécutable est {\sf com\_dec}.

La ligne de commande devra être au format suivant :  {\bf com\_dec -cdwr [fichier] }.
Les actions correspondantes aux options sont :
\begin{itemize}
\item {\sf -c} pour compresser
\item {\sf -d} pour décompresser
\item {\sf -w} pour créer un dictionnaire  
\item {\sf -r} pour rechercher un motif dans le fichier compressé
\end{itemize}
Bien entendu ces options ne sont pas cumulables.\\
Si vous entrez la commande {\bf com\_dec -c [fichier] }, le programme vous demandera le mode de compression :
\begin{itemize}
\item {\sf s} pour une compression sans dictionnaire
\item {\sf a} pour une compression avec dictionnaire
\end{itemize}

Si vous choisissez l'option {\sf a}, le programme vous demandera d'entrer le nom du dictionnaire. Il convient donc de fournir au programme un dictionnaire
qui correspond au texte que vous cherchez à compresser. Trois dictionnaires sont fournis avec le programme :
\begin{itemize}
\item {\sf dico\_french} pour compresser des textes en fran\c cais
\item {\sf dico\_c} pour compresser des fichiers au format {\sf c}
\item {\sf dico\_html} pour compresser des fichiers au format {\sf html}
\end{itemize}
Apres compression du fichier {\sf fic} le fichier compressé s'appelera {\sf fic.comp}. Un fichier {\sf fic.dico} est aussi généré qui va servir pour
la décompression. {\bf Il ne faut surtout pas l'effacer}.

Si les dictionnaires fournis ne vous conviennent pas ou si vous désirer compresser un texte dont le dictionnaire correspondant n'est pas fourni, vous pouvez créer 
vous-même un dictionnaire avec l'option {\sf w}.

Si vous choisissez cette option, le programme vous demandera :\\
{\sf Entrez le type du dictionnaire }
Si vous entrez {\sf anglais} par exemple, le nom du dictionnaire sera {\sf dico\_anglais}


L'option {\sf r} quant à elle prend sur la ligne de commande un nom de fichier compressé. Le programme vous demandera ensuite le motif à rechercher puis affichera
les numéros des lignes contenant ce motif. 

\section*{Compression à l'aide d'un anti-dictionnaire}
Après avoir éxécuté la commande make, on obtient un fichier éxécutable dca, c'est le fichier qui permettra la compression ou la décompression.

La ligne de commande devra être au format suivant :  {\bf com\_dec [fichier] -cdt -o [fichier] -h [taille]}.
On ne peut pas avoir les options {\bf-c et -d} en même temps dans la ligne ( seul la derniére options est prise en compte ).
Il n'est pas indispensable de mettre l'option {\bf-h} lorsque l'on utilise la partie des tests.
\begin{itemize}
\item -c pour compresser
\item -d pour décompresser
\item -t pour éffectuer des tests
\item -h valeur pour affecter valeur a la hauteur de l'arbre des prefixes
\item -o fic pour que le fichier de sorti soit fic
\end{itemize}

%--------------------------------------------------------------------------------------------------------------------------------------
\chapter*{$\cal{II}$ - COMPRESSION A L'AIDE D'UN DICTIONNAIRE}
\addcontentsline{toc}{chapter}{$\cal{II}$ - COMPRESSION A L'AIDE D'UN DICTIONNAIRE}

\rhead{Compression à l'aide d'un dictionnaire}

Cette méthode consiste à remplacer des mots qui apparaissent fréquemment dans le texte par des mots plus courts qui eux n'apparaissent pas dans le texte.

\section*{1 - Création du dictionnaire}
\addcontentsline{toc}{section}{1 - Création du dictionnaire}

L'objectif est de créer à partir d'un texte donné un fichier contenant les mots du texte qui sont interressant à coder (qui font gagner de la place). 
Ces mots sont obtenus apres plusieurs compression du texte (on compresse le texte jusqu'à ce qu'il soit incomprssible ou qu'il n'y ait plus de code
disponible et à chaque étape, on relève le mot le plus interressant à coder).

Les fonctions relatives à la création d'un dictionnaire se trouvent dans le fichier {\sf dico.c}.

\subsection*{Obtention des codes}

Tout d'abord il faut obtenir les caractères ASCII qui vont constituer les codes : ce sont les caractères qui ne sont pas présents dans le texte.
On les obtient grâce à la fonction de prototype :
\begin{verbatim}  
char* Codes (char nom_source[],int *nb_cars_restants)
\end{verbatim}
Dans cette fonction, on dispose d'un tableau contenant tous les codes ASCII sauf le caractère de fin de mot. Ensuite, on effectue un parcour
du texte et on supprime du tableau tous les caractères qui sont présents dans le texte. La valeur de retour de la fonction {\sf Codes} est un tableau
contenant les caractères qui ne sont pas présents dans le texte.

\subsection*{Recherche du mot le plus fréquent}

Pour trouver le mot le plus fréquent du texte, on se sert des fonctions suivantes : 
\begin{verbatim}  
void ChercheMotsLongueurDonnee (char nom_source[],int taillemot)
char* MotPlusFrequent (char nom_source[])
\end{verbatim}
La fonction {\sf ChercheMotsLongueurDonnee} parcours le texte et affiche dans un fichier tous les segments de mots du texte de taille {\sf taillemot}.
La fonction {\sf MotPlusFrequent} appelle {\sf ChercheMotsLongueurDonnee} pour afficher tous les segments de mots du texte dont la longueur est comprise
entre 3 et {\sf TAILLEMOT} (TAILLEMOT étant une constante dont la valeur est 9). Ces mots sont ensuite triés grâce à la commande système sort. Ensuite, 
le texte étant trié, il est plus facile de trouver le mot dont le coût est maximal ({\sf coût} = {\sf longueur du mot} * {\sf nombre d'occurences}).
Par exemple si le fichier obtenu est le suivant :
\begin{verbatim}  
il fait
il fait
beau
beau
beau
beau
chaud
chaud
chaud
\end{verbatim}
On obtient les coûts suivants :
\begin{itemize}
\item cout(il fait) = $7 * 2 = 14$
\item cout(beau) = $4 * 4 = 16$
\item cout(chaud) = $5 * 3 = 15$
\end{itemize}
Donc le mot le plus interressant à coder est {\sf beau} car 16 est le coût maximal.

\subsection*{Compression du texte}

Une fois le mot le plus fréquent trouvé, on parcours le texte et on remplace chaque occurence du mot par un code qu'on vient de créer (la plupart des codes sont des codes 
à une lettre mais on se réserve toutefois les 11 dernières lettres du tableau de codes pour s'en servir comme 1\textsuperscript{ère} lettre des codes à deux lettres).
Cette opération est réalisée par la fonciton de prototype :
\begin{verbatim} 
void Reduction (char nom_source[],char *code,char *mot)
\end{verbatim}
La fonction :
\begin{verbatim} 
char* Compression(char nom_source[])
\end{verbatim}
éffectue des réductions successives du texte jusqu'à ce que le texte soit incompressible. A chaque réduction le mot le plus fréquent ainsi que le
code correspondant sont écrits dans un fichier et à la fin, ce fichier contient tous les mots les plus fréquents du texte et les codes.\\
{\bf N.B.} Les mots les plus fréquents du texte peuvent aussi contenir des codes.   
Une fois ce fichier obtenu, on fait appel à la fonction :
\begin{verbatim} 
void Construit_Table(char nom_fic_dico[],Table tab)
\end{verbatim}
qui remplit une table de hachage avec les mots et les codes du fichier (la valeur de hachage est la somme des codes ASCII des lettres du code).
Ensuite, la fonction :
\begin{verbatim} 
char* CreerDico (char nom_dico_codes[],Table tab,char type_dico[])
\end{verbatim}
extrait les mots de la table, les traite (remplace les codes à l'intérieur des mots par les segments de mots correspondants), et écrits le résultat du traitement 
dans un fichier (le dictionnaire en fait).\\
{\bf N.B.} Les mots du dictionnaire ne contiennent pas de code.

\subsubsection*{Détails}
On utilise une table de hachage pour pouvoir extraire les mots en temps constant.

La création du dictionnaire est la partie du programme qui met le plus de temps à s'exécuter. Ceci est en grande partie du à la recherche du mot le plus fréquent 
à chaque réduction et à l'appel système {\sf sort}.

\section*{2 - Compression}
\addcontentsline{toc}{section}{2 - Compression}

Les fonctions relatives à la compression d'un texte se trouvent dans le fichier {\sf comp.c}.

La compression peut se faire selon les deux modes suivants : 

\subsection*{a - Compression avec dictionnaire}
\addcontentsline{toc}{subsection}{a - Compression avec dictionnaire}

Cette méthode nécessite la création au préalable d'un dictionnaire. On va utiliser ce dictionnaire pour connaitre les mots les plus fréquemment utilisés que
nous associeront par la suite à des codes grâce à la fonction :
\begin{verbatim} 
void AssocieCodes(char nom_dico[],char nom_source[])
\end{verbatim}
On obtient un fichier d'extension {\sf .dico} qui contient les mots du dictionnaires et les codes qui leur correspondent.
Ensuite grâce à la fonction :
\begin{verbatim} 
Arbre Cree_Arbre (char nom_dico_codes[] )
\end{verbatim}
on insère tous les mots du fichier obtenu dans un arbre lexicographique ainsi que le code associé à chaque mot.

Par exemple pour les mots :
\begin{itemize}
\item bal de code A
\item balle de code B
\item Bye de code C
\item moue de code D
\end{itemize}
on obtient l'arbre lexicographique suivant :\\

\begin{figure}[h]
\begin{center}
\epsfig{file=fig1.eps,width=6.5cm}
\caption{Arbre lexicographique}
\end{center}
\end{figure}
\newpage
On parcours le texte et à chaque lettre lue, on se déplace dans l'arbre. Si on arrive à la fin d'un mot dans l'arbre, on récupère le code correspondant
et on écrit le code dans un fichier (d'extension {\sf .comp}). Si on ne peut plus descendre dans l'arbre, on écrit la première lettre du mot en cours, et on recommence à partir de l'endroit
o\`u on s'était arrêté dans le fichier source. 

Le fichier d'extension {\sf .comp} obtenu est le fichier compressé.

\subsection*{b - Compression sans dictionnaire}
\addcontentsline{toc}{subsection}{b - Compression sans dictionnaire}
La compression sans dictionnaire est faite suivant le même principe que la création d'un dictionnaire (vu plus haut). La seule différence est qu'à la fin de la compression,
on garde le fichier compressé (d'extension {\sf .comp} et le fichier d'extension {\sf .dico}.\\
{\bf N.B.} Ce mode de compression met beaucoup plus de temps que la compression avec un dictionnaire.

\section*{3 - Décompression}
\addcontentsline{toc}{section}{3 - Décompression}

Les fonctions relatives à la décompression d'un texte se trouvent dans le fichier {\sf decomp.c}.

La décompression d'un texte se fait en deux étapes :
\begin{itemize}
\item tout d'abord on extrait tous les mots du dictionnaire et on les insère dans une table de hachage.
\item ensuite, on lit une par une les lettres du texte et on forme un code à une lettre avec la lettre lue et un code à deux lettres avec la lettre lue et la lettre précédente.
On regarde d'abord si le code à deux lettres est présent dans la table de hachage, s'il existe on écrit dans un fichier le mot correspondant au code apres avoir
effacé la dernière du fichier (1\textsuperscript{ère} lettre du code à deux lettres) . Si le code à deux lettres n'existe pas dans la table, on regarde si le code à une lettre existe.
Si c'est le cas, on écrit le mot correspondant dans le fichier. Sinon on écrit la lettre lue. Et la lettre lue va devenir à la prochaine étape la première lettre du code à deux lettres. 
\end{itemize}


\section*{4 - Recherche de motifs}
\addcontentsline{toc}{section}{4 - Recherche de motifs}

Il s'agit de rechercher un motif dans le texte compressé. 
Pour ce faire, nous nous servons principalement de deux fonctions :\\
\begin{verbatim}
void RechercheMotifs( int lignes[], char motif[], char nom_fic[], 
                      Table tab)
\end{verbatim}
et
\begin{verbatim}
char* RechercheMotifs_Mot( int lignes[], char motif[], int *indice, 
                           char *mot, int num_ligne)
\end{verbatim}

La fonction {\sf RechercheMotifs\_Mot} prend en argument un motif et un mot et recherche le motif dans le mot. S'il est présent, elle met le numéro de
la ligne courante (pris aussi en argument) dans le tableau {\sf lignes[]}.\\
{\bf Valeur de retour : }
\begin{itemize}
\item le mot si sa taille est inférieure à la taille du motif
\item les {\sf strlen(motif)}-1 dernières lettres sinon
\end{itemize}

La fonction {\sf  RechercheMotifs} effectue une lecture du texte caractère par caractère. A chaque lecture, elle vérifie si le caractère lu forme un code à deux lettres avec le caractère
précédemment lu ou bien s'il forme un code à une lettre. Si c'est le cas, le code est remplacé par le mot correspondant. Le mot ainsi obtenu est concaténé avec le segment de mot renvoyé par 
la fonction {\sf RechercheMotifs\_Mot}. Le résultat de cette concaténation est enfin passé à {\sf RechercheMotifs\_Mot} pour une nouvelle recherche de motif.

\section*{5 - Exemples}
\addcontentsline{toc}{section}{5 - Exemples}

\subsection*{Exemples de création d'un dictionnaire}

Le temps mis pour créer le dictionnaire correspondant à un texte est le même que le temps mis pour effectuer une compression sans dictionnaire sur ce texte.\\

\begin{tabular}{|l|c|r|}
\hline
Fichier & Taille (octets) & Temps de créeation (min)\\
\hline
Balzac & 414994 & 23\\
\hline
Gargantua & 273787 & 17\\
\hline
Fille & 162836 & 19\\
\hline
graphes.c & 66842 & 33\\
\hline
index.html & 71337 & 41\\
\hline
\end{tabular}\\\\
On constate que le temps mis par le programme pour créer un dictionnaire ne dépend pas de la taille du fichier mais plutôt de son taux de compressibilité. C'est pourquoi 
la création du dictionnaire pour le fichier {\sf Fille} qui est plus petit que le fichier {\sf Gargantua} met moins de temps.  

\subsection*{Exemples de compression avec dictionnaire}
Ce mode de compression est assez rapide (quelques secondes).

On compresse un fichier de nom {\sf tout} et de taille 851517 octets avec les dictionnaires obtenus plus haut. Les résultats obtenus sont les suivants :\\

\begin{tabular}{|l|c|c|c|r|}
\hline
Dictionnaire & Taille du {\sf .comp} & Taille {\sf .dico} & Total & Taux (en \%)\\
\hline
dico\_balzac & 538517 & 1737 & 540254 & 36.57\\
\hline
dico\_gargantua & 545964 & 1224 & 547188 & 35.75\\
\hline
dico\_fille & 550983 & 1241 & 552224 & 35.16\\
\hline
\end{tabular}\\\\

On constate que plus la taille du  dictionnaire est grande et meilleur est le taux de compression. 

\subsection*{Exemples de compression sans dictionnaire}

Avec une compression sans dictionnaire des fichiers précédents, on obtient les résultats suivants :\\\\
\begin{tabular}{|l|c|c|c|c|r|}
\hline
Source & Taille du source & Taille {\sf .comp} & Taille du {\sf .dico} & Total & Taux (en \%)\\
\hline
Balzac & 414994 & 250844 & 1524 & 252368 & 39.19\\
\hline
Gargantua & 273787 & 165747 & 1069 & 166816 & 39.07\\
\hline
Fille & 162836 & 99590 & 1124 & 100714 & 38.15\\
\hline
graphes.c & 66842 & 17788 & 6884 & 24632 & 63.15\\
\hline
index.html & 71337 & 20915 & 8744 & 29659 & 58.42\\
\hline
\end{tabular}\\\\

On constate que les fichiers spéciaux (d'extension {\sf html}, {\sf c} ...) offrent une meilleure compression que les fichiers texte.


%--------------------------------------------------------------------------------------------------------------------------------------

\chapter*{$\cal{III}$ - COMPRESSION A L'AIDE D'UN ANTI-DICTIONNAIRE}
\addcontentsline{toc}{chapter}{$\cal{III}$ - COMPRESSION A L'AIDE D'UN ANTI-DICTIONNAIRE}

\rhead{Compression à l'aide d'un anti-dictionnaire}

\section*{1 - Création de l'arbre des préfixes}
\addcontentsline{toc}{section}{1 - Création de l'arbre des préfixes}

Les fonctions relatives à la création de l'arbre se trouvent dans le fichier {\sf arbre.c}.
L'arbre des préfixes est l'ensembles des mots de longueurs finies qui apparaissent dans le texte.
L'arbre des prefixes est utilisé pour obtenir l'arbre des mots interdits (anti-mots).

L'arbre des préfixes  est représenté sous forme d'un arbre binnaire dont la structure est la suivante :

\begin{verbatim}
typedef struct noeud
{
  int etat;
  //represente le lien suffixe
  struct noeud * lien_suffixe;
  //represente le bit 0
  struct noeud * gauche;
  //represente le bit 1
  struct noeud * droite;
}noeud;
\end{verbatim}

La création de l'arbre se fait avec la fonction 
\begin{verbatim}
long creer_arbre(FILE * src,noeud * racine)
\end{verbatim}

Si le texte est 10100100 on obtient l'arbre des préfixes suivant.

\begin{figure}[h]
\begin{center}
\epsfig{file=arbre.eps,width=9cm}
\caption{Arbre}
\end{center}
\end{figure}

\section*{2 - Création de l'anti-dictionnaire}
\addcontentsline{toc}{section}{2 - Création de l'anti-dictionnaire}

Les fonctions relatives à la création de l'anti-dictionnaire se trouvent dans le fichier {\sf anti.c}.
L'anti-dictionnaire représente les mots qui n'apparaissent pas dans le fichier (anti-mots).

La création de l'anti-dictionnaire se fait avec la fonction. 
\begin{verbatim}
long creer_anti(FILE * src,noeud * racine)
\end{verbatim}

Si le texte est 10100100 on obtient l'arbre des préfixes , ainsi que l'anti-dictionnaire suivant.

\begin{figure}[h]
\begin{center}
\epsfig{file=arbre+ls+anti.eps,width=10cm}
\caption{Arbre,Liens Suffixe,Anti}
\end{center}
\end{figure}

\section*{3 - Création de l'automate}
\addcontentsline{toc}{section}{3 - Création de l'automate}

Les fonctions relatives à la création de l'automate se trouvent dans le fichier {\sf anti.c}.
La création d'un automate permet la recherche d'un anti mot rapidement.
La création de l'automate se fait a partir de l'antidictionnaire.

La création de l'automate se fait avec la fonction 
\begin{verbatim}
void creer_automate(noeud * racine)
\end{verbatim}

Si l'anti-dictionnaire est l'anti-dictionnaire obtenu avant, on obtient l'automate suivant.

\begin{figure}[h]
\begin{center}
\epsfig{file=automate.eps,width=7cm}
\caption{Automate}
\end{center}
\end{figure}

\section*{4 - Compression}
\addcontentsline{toc}{section}{4 - Compression}

Les fonctions relatives à la compression se trouvent dans le fichier {\sf compression.c}.
Pour pouvoir décompresser le fichier avec la fonction de décompression, on a besoin de stocker des informations :
\begin{itemize}
\item - la taille du fichier
\item - l'anti-dictionnaire
\item - les données compressées  
\end{itemize}

L'anti-dictionnaire qui est formé de noeud  est stocké sous forme d'une suite de bits.
pour chaque noeud on peut soit stocker \textbf{00} pour dire que le noeud n'a pas de fils, soit stocker \textbf{10} pour dire que le noeud n'a que le fils gauche, soit stocker \textbf{01} pour dire que le noeud n'a que le fils droit, soit stocker \textbf{11} pour dire que le noeud a deux fils.

Les données compressées sont obtenues avec la prédiction des bits.
On parcour tout le texte bit à bit, si on peut predire 1 bit grâce a l'automate (anti-dictionnaire) alors on passe au bit suivant.
Si on ne peut pas predire ce bit alors on le stocke sur le disque.
Les données compressées representent en fait les endroits ou l'on a pas pu predire de bit.
On a donc stocké tous les endroits où on etait bloqué.
Plus on peut prédire de bits, plus le taux de compression est grand.

La compression d'un fichier se fait avec la fonction 
\begin{verbatim}
void compresser(FILE * src,FILE * des)
\end{verbatim}

Si le texte 10100100, on a donc les anti-mots {000,0101,11} on obtient :
1\textbf{0}1\textbf{00100}

Les bits en \textbf{gras} sont les bits que l'on peut predire grace aux anti-mots.
Ces bits ne serront donc pas inscrits sur le disque.

La compression se fait en lisant 2 fois le fichier, la 1ere fois pour créer l'anti-dictionnaire et la 2eme fois pour compresser.

\section*{5 - Décompression}
\addcontentsline{toc}{section}{5 - Décompression}

Les fonctions relatives à la décompression se trouvent dans le fichier {\sf decompression.c}.
Pour pouvoir décompresser le fichier, on recupere les informations qui ont été données par la fonction de compression:
\begin{itemize}
\item - taille du fichier
\item - anti-dictionnaire
\item - données compressées  
\end{itemize}

On a besoin de la taille du fichier d'origine car sinon on ne pourrait pas s'arreter lors de la decompression vu que 10100100 et 10100100100100... sont codés de la même façon.
On a besoin de l'anti-dictionnaire pour pouvoir décompresser les données.
Les données compressées sont les endroits où l'on a pas pu prédire de bit lors de la compression.

la décompression d'un fichier se fait avec la fonction 
\begin{verbatim}
void decompresser(FILE * src,FILE * des)
\end{verbatim}


si le texte compressé est 11 et que l'anti-dictionnaire est {000,0101,11} on obtient : 
1\textbf{0}1\textbf{00100}

Les bits en \textbf{gras} sont les bits que l'on peut predire grace aux anti-mots.
Ces bits ne serront donc pas rajoutés sur le disque.

La compression se fait en lisant 1 fois le fichier.
La reconstitution de l'arbre se fait a la volée, vu que celui-ci est stocké sur le disque.

\section*{6 - Réduction de l'anti-dictionnaire}
\addcontentsline{toc}{section}{6 - Réduction de l'anti-dictionnaire}

Les fonctions relatives à la réduction de l'anti-dictionnaire se trouvent dans le fichier {\sf anti.c}.
La réduction de l'antidictionnaire permet de gagner en compression.
On peut compresser l'arbre par 2 méthodes :

\subsubsection*{a - Réduction Simple}
\addcontentsline{toc}{subsection}{a - Réduction Simple}

Les fonctions relatives à la réduction de l'anti-dictionnaire se trouvent dans le fichier {\sf anti.c}.
Chaque noeud de l'arbre serra representé sur le disque par une des chaine suivante 00,01,10,11 vu que l'on travaille sur 1 arbre binnaire.
On peut donc supprimer certains anti-mots qui prennent trop de place sur le disque pour pouvoir gagner en compression.
Pour cela on compte, lors de la création de l'anti-dictionnaire, le nombre de fois que l'on ``passe''sur l'anti-mot et on applique la formule suivante sur chaque noeud de l'arbre.\\

\begin{displaymath}
G(S) = \left\{ \begin{array}{ll}
C(S) -2 & \textrm{ si S est une feuille }\\
G(S1) -2 & \textrm{ si S a un fils }\\
MAX(G(S1),G(S2),G(S1)+G(S2))-2 & \textrm{ sinon }\\
\end{array}
\right.
\end{displaymath}

Ou C représente le nombre de fois que l'on est ``passé'' sur l'anti-mot et G le gain en bit de la suppression de l'anti-mot.

La réduction de l'anti-dictinnaire se fait avec la fonction
\begin{verbatim}
int reduit_anti(noeud * ne)
\end{verbatim}

\subsubsection*{b - Auto-compression de l'anti-dictionnaire}
\addcontentsline{toc}{subsection}{b - Auto-compression de l'anti-dictionnaire}

Les fonctions relatives à l'auto-compressionse trouvent dans le fichier {\sf anti.c}.
L'auto-compression permet un gain lors de la compression, vu que l'anti-dictionnaire prend une place non négligeable lors de la compression.
L'auto-compression compresse l'anti-dictionnaire par lui meme.
Ex : si on a l'anti-dictionnaire {000,0101,1001,11} , celui-ci s'auto-compressera en {000,011,100,11}
pour plus de renseignement sur l'auto-compression , cf section 8.

L'auto-compression de l'anti-dictinnaire se fait avec la fonction.
\begin{verbatim}
noeud * auto_compresser(noeud * ne)
\end{verbatim}

\section*{7 - Exemple de compression de fichiers}
\addcontentsline{toc}{section}{7 - Exemples de compression de fichiers}

Les tests on été éffectués avec une hauteur d'arbre de 35 bits.\\

\begin{tabular}{|l|c|c|c|c|r|}
\hline
Source & Taille d'origine & Taille apres compression & Taux de compression\\
\hline
Balzac & 414994 & 182357 & 57\%\\
\hline
Gargantua & 273787 & 127155 & 55\%\\
\hline
Fille & 162836 & 73265 & 55\%\\
\hline
graphes.c & 66842 & 22607 & 67\%\\
\hline
index.html & 71337 & 23439 & 68\%\\
\hline
\end{tabular}\\\\

\section*{8 - Compression des facteurs}
\addcontentsline{toc}{section}{8 - Compression des facteurs}

La compression des facteurs sert a montrer le taux de compression lors de la compression de l'anti-dictionnaire.
l'anti-dictionnaire prennant beaucoup de place sur le disque , on peut donc en deduire que plus le taux de compression des facteurs est grand , plus le taux de compression du fichier est grand.

La compression des facteurs se fait avec la fonction.
\begin{verbatim}
void compression_facteurs(noeud * arbre, noeud * automate)
\end{verbatim}
On a avant la compression des facteurs l'arbre suivant :

\begin{figure}[h]
\begin{center}
\epsfig{file=arbre.eps,width=8cm}
\caption{Arbre des facteurs non compressé}
\end{center}
\end{figure}

Apres la compression des facteurs, on obtient l'arbre suivant :

\begin{figure}[h]
\begin{center}
\epsfig{file=compresse.eps,width=8cm}
\caption{Arbre des facteurs compressé}
\end{center}
\end{figure}

Sur cet exemple , on obtient 6 noeuds seulement sur les 22 noeuds a l'origine , soit un taux d'environ 75\%.\\


\section*{9 - Tests sur la compression des facteurs}
\addcontentsline{toc}{section}{9 - Tests sur la compression des facteurs}

Les tests ont été éffectués sur les headers de fonctions du projet.
On obtient les resultats suivant.\\\\

\begin{tabular}{|l|c|c|c|c|r|}
\hline
Source & Taux de compression\\
\hline
compression.h & 99,78\%\\
\hline
decompression.h & 99,78\%\\
\hline
compression.h & 99,70\%\\
\hline
compression.h & 99,59\%\\
\hline
\end{tabular}
%--------------------------------------------------------------------------------------------------------------------------------------

\chapter*{CONCLUSION}
\addcontentsline{toc}{chapter}{CONCLUSION}

\rhead{Comprssion de textes}

On consate que la méthode de compression avec antidictionnaire est souvent plus avantageuse que la méthode avec dictionnaire.
La compression à l'aide d'un antidictionnaire permet de compresser un grand nombre de fichiers (fichier texte, images ...) contrairement
à la compression avec dictionnaire qui permet seulement la compression de fichiers texte.
La compression à l'aide d'un dictionnaire sera efficace si le texte obeit à une norme comme le HTML, le latex, les fichiers C ...


\end{document}