\documentclass[11pt]{article}

\usepackage{fullpage,french,epsf,fancyheadings}

\pagestyle{fancy}
\lhead{Plus long complément}
\rhead{Jean-Christophe Filliâtre}

\newcommand\cad{c'est-\`a-dire}
\newcommand\point{{\noindent$\bullet$~}}

\begin{document}

\begin{center}
  \LARGE\bf Plus long complément
\end{center}
\bigskip

On se propose ici de résoudre le problème suivant : étant donnés un ensemble
de mots $M = \{m_1, m_2, \dots, m_n\}$ et un mot $p$, existe-t-il des mots dans
$M$ dont $p$ soit un préfixe, et le cas échéant quel est le plus grand préfixe
commun à tous ces mots ?

Ce problème a des applications pratiques : certains environnements
informatiques proposent ce que l'on appelle en anglais ``{\em the
filename completion\/}'', \cad\ la possibilité de compléter les noms
de fichiers autant que possible tant qu'il n'y a pas d'ambigu\"\i té.
Si par exemple, j'ai dans le répertoire courant les trois fichiers
\begin{center}
  {\tt recursivite.ml \qquad recurrence.ml \qquad arbres.ml}
\end{center}
alors la chaîne de caractères {\tt re} peut être complété en {\tt
recur} (qui est le plus grand préfixe commun à tous les noms de
fichiers commençant par {\tt re}), {\tt recurs} complété directement
en {\tt recursivite.ml} et {\tt a} en {\tt arbres.ml}, par exemple.


\section{Solution naïve}

Imaginez une solution naïve (mais sans la réaliser) et évaluez sa complexité
en fonction du nombre de mots $n$ et de la longueur maximale $L$ des mots.


\section{Une solution efficace}

On propose ici une solution plus efficace consistant à construire un arbre
contenant les mots de $M$ tel que la recherche se fera ensuite en temps $L$.

L'idée est que les lettres du mot $p$ doivent permettre d'éliminer
successivement les mots dont $p$ n'est pas un préfixe, pour ne garder que
les autres. Pour cela, on construit à partir des mots de $M$ un arbre
dont les branches sont étiquetées avec des lettres et les n\oe uds avec
des mots, qui sont soit des préfixes de mots de $M$, soit des mots de $M$.

\medskip
Exemple : prenons $n=4$ et $M = \{ caml, cafe, cafes, java\}$. Alors
l'arbre est le suivant :

\bigskip
\epsfxsize=10cm%
\hfil\epsfbox{prefixe-arbre1.eps}\hfil

\noindent où l'on a marqué les mots de $M$ par une astérisque.


\subsection{Préliminaires}

\point Ecrire deux fonctions transformant les chaînes de caractères en
listes de caractères et réciproquement :
\begin{center}
  \verb!char_list_of_string : string -> char list! \\
  \verb!string_of_char_list : char list -> string!
\end{center}

On prendra pour le type des arbres le type {\sc Caml} défini ci-dessous.
Les n\oe uds de l'arbre sont étiquettés soit par un préfixe d'un mot de $M$,
soit par un mot de $M$. Les différentes branches partant d'un n\oe ud sont 
représentées par une liste d'association.
\begin{verbatim}
     type etiquette = Mot     of string
                    | Prefixe of string ;;

     type arbre = Noeud of etiquette * (char * arbre) list ;;
\end{verbatim}

De manière générale, une liste d'association est une liste de type
\verb!('a * 'b) list!, associant des objets de type \verb!'b! à des
objets de type \verb!'a!. L'utilisation des listes d'association en
{\sc Caml} est fréquente et il existe dans la bibliothèque standard
les fonctions suivantes : \verb!(mem_assoc! $a$ $l${\tt)} teste si
l'object $a$ est dans le domaine de $l$, et \verb!(assoc! $a$ $l${\tt)}
renvoie l'objet associé à $a$ dans $l$ (lève une exception si $a$ n'est pas
dans le domaine de $l$).
\begin{verbatim}
     mem_assoc : 'a -> ('a * 'b) list -> bool
     assoc     : 'a -> ('a * 'b) list -> 'b
\end{verbatim}

\point Ecrire une fonction \verb!change_assoc! modifiant une entrée dans
une liste d'association :
\begin{center}
  \verb!change_assoc : ('a * 'b) list -> 'a -> 'b -> ('a * 'b) list!
\end{center}


\subsection{Construction de l'arbre}

On va construire l'arbre correspondant à l'ensemble de mots $M$ en
partant d'un arbre initialement vide (\verb!Noeud (Prefixe "",[])!)
et en y insérant les mots de $M$ un à un.

\bigskip
\point Ecrire une fonction \verb!insere_mot : arbre -> string -> arbre! qui
insére un mot dans un arbre. (Il est conseillé d'écrire une fonction
prenant un arbre et la liste des caractères du mot, puis de l'appeler
en utilisant \verb!char_list_of_string!).

\bigskip
\point En déduire une fonction \verb!construit_arbre! prenant une liste
de mots (\verb!string list!) et construisant l'arbre associé.
La tester sur l'exemple donné ci-dessus.


\subsection{Recherche du plus grand complément}

\point Ecrire une fonction \verb!complete : arbre -> string -> string!
recherchant le plus complément possible d'un mot $p$, \cad\ le plus grand
préfixe commun à tous les mots de $M$ dont $p$ est un préfixe.

\bigskip
Quelle est la complexité de cette recherche, en fonction de $n$ et de la
longueur maximale $L$ des mots de $M$ ? Comparer avec la méthode naïve.


\subsection{Recherche de tous les compléments possibles}

\point Ecrire une fonction
\verb!trouve_complements : arbre -> string -> string list!
qui renvoie, pour un mot $p$, tous les mots
de $M$ dont $p$ est un préfixe.


\section{Optimisation}

On peut améliorer la recherche du plus grand complément de la façon suivante :
au lieu de stocker sur les n\oe uds de l'arbre le mot correspondant au
chemin qui va de la racine au n\oe ud, on y stocke directement le plus 
grand complément du mot correspondant au chemin depuis la racine.

\medskip
Exemple : pour le même ensemble $M = \{ caml, cafe, cafes, java\}$ on a
maintenant l'arbre suivant :

\bigskip
\epsfxsize=10cm%
\hfil\epsfbox{prefixe-arbre2.eps}\hfil

\bigskip
\point Ecrire une fonction \verb!optimise : arbre -> arbre! prenant un
arbre (construit avec la première méthode) et rendant un arbre
{\em optimisé\/}.

\bigskip
\point Ecrire une fonction \verb!complete_opt! effectuant la recherche
du plus grand complément dans un arbre optimisé.
Quelle est maintenant la complexité de la recherche ? Est-elle optimale ?


\bigskip
\subsection*{S'il vous reste du temps...}

\point Ecrire une fonction \verb!insere_opt! permettant d'insérer un mot
dans un arbre optimisé. Quelle est maintenant la complexité de la
construction de l'arbre ?


\bigskip
\subsection*{Pour les curieux...}

Les implantations pratiques de telles méthodes se font d'une manière similaire,
mais utilisent parfois des arbres équilibrés (AVL) pour stocker les mots.


\end{document}