\documentclass{article}
\usepackage{a4}
\usepackage{xypic}
\usepackage{francais}

\newtheorem{exercise}{Exercice}[section]

\begin{document}
\centerline {TP numéro 3}
\centerline {2 et 5 novembre 1999}
\bigskip
\bigskip
\bigskip
\centerline{\bf Arbres: codage de Huffman.}
\bigskip

Le codage de Huffman peut être utilisé pour comprimer une suite
d'éléments (par exemple un texte, qui est une suite  de caractères)
en remplaçant chaque élément par son code,  qui est une séquence
de  valeurs booléennes.  On s'intéressera  ici à coder et décoder
des suites de {\tt char}.

Cette séance se décompose en deux parties : on crée quelques
fonctions générales de manipulation d'un arbre ; dans un deuxième
temps on utilisera ces fonctions pour mettre en place le codage de Huffman.

\section{Manipulation d'arbres}

Le type de données \verb|arbre| devra décrire un arbre
binaire dont les n{\oe}uds sont étiquetés par un
\verb|char|.

\begin{exercise}[Le type de données arbre]
Pour le type de données \verb|arbre| définie  comme suit

\begin{verbatim}
struct chararbre {
  char data;
  struct chararbre *gauche;
  struct chararbre *droite;
};
typedef struct chararbre *arbre;
\end{verbatim}

définissez les fonctions suivantes:\\
Constructeurs:
\begin{itemize}
  \item \verb|arbre empty()| construit un arbre vide
  \item \verb|arbre node(char data, arbre g, arbre d)| construit
        l'arbre à partir de sa racine et de ses sous-arbres.
\end{itemize}
Testeurs:
\begin{itemize}
  \item \verb|int isempty(arbre a)| renvoie 1 si l'arbre est vide et 0 sinon
\end{itemize}
Destructeurs:
\begin{itemize}
  \item \verb|char data(arbre a)| renvoie la donnée dans la racine de {\tt a}
  \item \verb|arbre filsg(arbre a)| renvoie le sous-arbre gauche de {\tt a}
  \item \verb|arbre filsd(arbre a)| renvoie le sous-arbre droit de {\tt a}
\end{itemize}
\end{exercise}

\begin{exercise}[Affichage d'un arbre]
Écrivez une fonction \verb|void affiche(arbre a)| qui affiche
l'arbre, en utilisant \emph{uniquement} les fonctions définies ci-dessus.
Une idée est de fabriquer une focntion auxiliaire
\verb|void afficheavecblanc(arbre a, int b)| qui affiche un arbre
en mettant \verb|b| espaces au début de chaque ligne, qui fait un parcours
infixe de l'arbre.

Par exemple, l'arbre
\(
\spreaddiagramrows {-1pc}
\diagram
& b\dlto\drto & & \\
a & & c\dlto\drto & \\
& d & &e \\
\enddiagram
\)
sera affiché :
\begin{minipage}{10em}
\begin{verbatim}
b a
  c d
    e
\end{verbatim}
\end{minipage}
\end{exercise}

\begin{exercise}[Miroir d'un arbre]
Écrivez une fonction \verb|arbre miroir(arbre a)| qui construit
l'arbre miroir de {\tt a},
en utilisant \emph{uniquement} les fonctions definies ci-dessus.\\
Testez votre fonction.
\end{exercise}

\begin{exercise}[Modification en place]
En utilisant la fonction \verb|void echange(arbre a)| ci-dessous,
reécrivez  la fonction \verb|miroir|.
Commentez sur la différence des deux approches.
\begin{verbatim}
void echange(arbre a) {
  arbre X = a->gauche; a->gauche = a->droite; a->droite = X;
}
\end{verbatim}
\end{exercise}

\section{Le codage de Huffman.}
\subsection*{Préliminaires.}

Voyons d'abord le décodage, qui  est le plus simple à  réaliser.
Un codage de Huffman d'une séquence de caractères est est constitué
d'un couple (arbre de décodage, séquence binaire codée).

L'arbre de décodage est un arbre binaire dont les feuilles
sont étiquetés par des caractères.
Chaque feuille (caractère) est codée par une séquence binaire de la façon
suivante :
le chemin qui va de la racine de l'arbre à une feuille  peut être
représenté par la  liste des choix  0 ({\it  sous-arbre de gauche}) 
ou  1 ({\it sous-arbre  de droite}) effectués a  chaque  n{\oe}ud
interne. Ceci définit une injection  de l'ensemble  des  feuilles de
l'arbre dans l'ensemble des séquences binaires.
\\
Appelons {\it ensemble des codes valides} l'image de cette injection.  
Par exemple, le dessin  suivant représente un arbre avec  des {\tt char}
sur les feuilles.
Pour cet  arbre, la liste {\tt  [1; 1; 0]} est  un code valide qui
représente la feuille {\tt g}.  Par contre, les listes {\tt [1; 1]} et
{\tt [1; 0; 0]} ne sont pas des codes valides.

\[
\spreaddiagramrows {-1pc}
\diagram
	&\bullet\dlto\drto		&	&	&	\\
a	&		&\bullet\dlto\drto	&	&	\\
	&	e	&	&\bullet\dlto\drto	&	\\
	&		&g	&	&h	\\
\enddiagram
\]

Aucun code valide n'est préfixe d'un autre.
Le décodage de Huffman se fait donc ainsi :
étant donné un couple (arbre de décodage, séquence binaire codée)
tel que la séquence binaire codée soit une suite de codes valides,
on parcours la séquence binaire codée pour en extraire cette suite
de codes valides et en déduire la suite de caractères.

\subsection*{Le décodage.} 

On utilisera le type \verb|arbre| défini en première partie
et le type \verb|sequence| ci-après pour coder les séquences binaires :
\begin{verbatim}
typedef struct intliste { int data; struct intliste *suivant; } *sequence;
\end{verbatim}

\begin{exercise}[Décodage d'un élément]
Écrivez une fonction \verb|decode_un| qui, étant donnés un {\tt
arbre} et une {\tt sequence} $L$ qui commence par un code valide,
retourne l'élément codé et le reste de la liste (le suffixe de $L$
qui n'a pas été utilisé pour trouver l'élément.)  Par exemple,
\verb|decode_un| appliquée à l'arbre ci-dessus et la séquence
\verb|1100| retourne  {\tt g} et {\tt [0]}.
\end{exercise}

\begin{exercise}[Décodage d'une séquence binaire]
\item  Écrivez une fonction {\tt decode} qui, étant donnés un
{\tt arbre} et une {\tt liste} obtenue par concatenation de codes
corrects, affiche la séquence de caractère ainsi codée.  Par
exemple, \hbox{\tt decode} appliquée à l'arbre ci-dessus et la
séquence \verb|1100| imprime {\tt ga}.
\end{exercise}

\subsection*{L'arbre de Codage.} 

Le codage de Huffman est efficace si l'arbre de départ est bien choisi~:
il faut placer les  éléments souvent rencontrés le  plus proches
possible de la racine. On va définir les types ci-dessous :
\begin{verbatim}
struct arbrepoids { arbre element; int poids; };
typedef struct liste { struct arbrepoids data; struct liste *suivant; } *liste;
\end{verbatim}

On commence par fabriquer une liste $L$ de la forme
{\tt [(<elem$_1$>, poids$_1$);  \dots; (<elem$_n$>,  poids$_n$)]},
où  les {\tt elem$_i$} sont
les éléments qui doivent apparaître dans l'arbre de Huffman,
et les {\tt poids$_i$} représentent leur fréquence probable dans les textes
à comprimer.
La notation {\tt <elem$_1$>} représente l'arbre à un seul n{\oe}ud
étiqueté par {\tt elem$_i$}.

Il est facile de construire un arbre de Huffman optimal
contenant les {\tt elem$_i$} :
On suppose que la liste est triée par poids croissants.
L'algorithme suivant permet de construire un arbre optimal~:
On choisit dans la liste deux arbres $a_1$ et $a_2$ de poids $p_1$
et $p_2$ minimaux.
On construit l'arbre $A$ suivant~:

\[
\diagram
        &		&\bullet\dlto\drto		&	& \\
        &\stackrel{\displaystyle a_1}{\vdots}	&		&\stackrel{\displaystyle a_2}{\vdots}	&\\
\enddiagram
\]

On lui  donne le poids  $p_1 + p_2$,  et on considère  alors la liste de
départ, moins les couples {\tt ($a_1$, $p_1$)} et {\tt ($a_2$,  $p_2$)},
plus {\tt ($A$, $p_1  + p_2$)} insérée comme  il faut pour préserver
l'ordre des poids.  Cette nouvelle liste  contient un élément de moins
que la  précédente.  On applique à nouveau la  transformation
jusqu'à obtenir  une liste réduite  à un seul couple.
Elle contient l'arbre optimal.


\begin{exercise}[Manipulation de la liste]
Programmez les fonctions qui permettent de récupérer le plus
petit élément d'une liste triée et d'y insérer un nouvel élément.
\end{exercise}

\begin{exercise}[Construction d'un arbre optimal]
Programmez une fonction {\tt make\_huff} qui prend une {\tt liste}
en argument, et qui retourne un arbre de Huffman optimal pour cette liste.
\end{exercise}

\begin{exercise}[Codage d'un caractère]
Écrivez une fonction qui prend un arbre de Huffman en argument,
un argument de type {\tt char} et renvoie la {\tt sequence} qui mène à
cet élément dans l'arbre donné.
\end{exercise}

\begin{exercise}[Codage d'une chaîne de caractères]
Écrivez une fonction qui prend un arbre de Huffman en argument,
une chaîne de caractères (de type \verb|char *|, terminée par le
caractère {\tt 0}) et renvoie la {\tt sequence} qui est
le codage de Huffman de cette chaîne.
\end{exercise}

\begin{exercise}[Liste des fréquences]
Écrivez une fonction qui une chaîne de caractères en argument
et fabrique la liste des fréquences des caractères
(celle qui sera utilisée pour faire l'arbre de Huffman).
\end{exercise}

\begin{exercise}[Questions supplémentaires]
.
\begin{enumerate}
\item
Pensez-vous qu'on pourrait rendre vos fonctions ``polymorphes'',
c'est à dire capable de manipuler des codages pour des éléments
arbitraires et non pas seulement des {\tt char}? Si oui, est-ce que votre
solution a des désavantages? Lesquels?
\item
Comment écririez vous le vrai programme de codage qui travaille
sur des réels fichiers?
\end{enumerate}
\end{exercise}

\end{document}
