\documentclass{tpcaml}

\tp{3}{Recherche de Motifs}

\begin{document}

  \maketitle

  La recherche de motifs consiste à trouver un texte court (le motif) dans
  un texte plus long. Il existe un algorithme naïf très simple qui consiste
  à essayer, pour chaque indice $i$ dans le texte long, de voir si le motif
  se trouve dans le texte long à cette position.

  \vspace{12pt}
  \begin{question}
    \'Ecrire la fonction utilisant l'algorithme naïf pour chercher un
    motif dans une chaîne. L'utiliser pour trouver \code{"tatare"}
    dans le texte \code{"tardive taxonomie tatare"}. Quelle est la
    complexité de cet algorithme?
  \end{question}

  \vfill

\section{Knuth--Morris--Pratt}

  On sait déjà qu'on peut utiliser des automates pour reconnaître un mot dans un texte 
  en temps constant, par exemple en recherchant le premier passage de l'automate 
  reconnaissant \code{".*tatare"} par son état final. 

  \vfill
  \begin{question}
    Construire un automate non-déterministe reconnaissant les mots qui se
    finissent par \code{"tatare"}, puis le déterminiser. 
  \end{question}
  \vfill

  Une fois déterminisé, l'automate permet de calculer en temps $O(n)$ 
  l'existence d'un motif dans un texte (puisque chaque transition se
  fait en temps constant). Il reste néanmoins le problème de la taille
  de l'automate déterminisé.

  \vfill
  \begin{question}
    Montrer que cette déterminisation produit un automate ayant
    \code{n+1} états, où \code{n} est la longueur du suffixe reconnu.

    Montrer que l'on peut reconfigurer l'automate déterministe en un
    automate à $\varepsilon$-transitions où chaque état (sauf le premier
    et le dernier) ont exactement deux transitions sortantes, dont une
    qui est étiquetée par une lettre.
  \end{question}
  \vfill

  On utilise l'approche suivante: lorsqu'on lit une lettre, si elle permet
  de suivre la flèche étiquetée, alors on la suit. Sinon, on suit la seule
  $\varepsilon$-transition sortante ou, si on est sur l'état initial, on
  reconnaît n'importe quoi en y restant. Cela permet d'avoir une complexité
  $O(n)$ en mémoire et en temps.

  \vfill
  \begin{question}
    On suppose que l'on se donne un automate comme une chaîne de caractères
    représentant le motif, et un tableau d'indices indiquant la destination
    de chacune des $\varepsilon$-transitions. Programmer une fonction
    \code{kmp\_chercher m a t} qui utilise l'automate pour déterminer la présence
    d'un motif dans un texte. Prouver que la complexité est linéaire.
  \end{question}
  \vfill

  Il reste une seule zone d'ombre: la construction de l'automate à partir
  du motif. 

  \vfill
  \begin{question}
    Supposons l'automate construit, et utilisons cet automate sur le motif
    privé de sa première lettre. Quel est le rapport entre l'état dans
    lequel se trouve l'automate après avoir lu $k$ lettres, et la
    destination de la transition issue de l'état $k+1$ ?
    
    Réutiliser la fonction de reconnaissance pour écrire la fonction de
    création de l'automate. Quelle est sa complexité?

    En déduire une fonction \code{kmp m t} qui cherche un motif dans un
    texte, en utilisant les fonctions de création et de reconnaissance.
  \end{question}

  \vfill

\newpage
\section{Rabin--Karp}

  On considère maintenant, lorsque $t$ est un mot, le mot $T_m$ défini
  comme:
  \[T_m[i] = (t[i]\ldots t[i+m-1])\]

  Autrement dit, les lettres de $T_m$ sont des facteurs de longueur $m$ du
  mot $t$ (et qui se chevauchent les uns les autres). Dans ces conditions,
  déterminer si un motif $M$ de longueur $m$ apparaît dans $t$, il suffit
  de déterminer si $T_m$ contient la lettre $M$. 

  \vfill
  \begin{question}
    \'Ecrire une fonction \code{rk\_applique a m t} qui applique
    la fonction \code{a} sur tous les facteurs de longueur \code{m}
    du mot \code{t}, dans l'ordre croissant. Elle renvoie \code{true}
    si \code{a} a renvoyé \code{true} sur l'un des facteurs.
  \end{question}
  \vfill

  La méthode naïve est donc un cas particulier de cette
  approche. Cependant, pour gagner en performances, on va utiliser une
  \em fonction de hachage \em pour comparer les chaînes plus facilement. On
  associe au mot $t[i]\ldots t[j-1]$ la clé:
  \[ hash(t[i]\ldots t[i+m-1]) \equiv \sum_{k=1}^m A^k t[i+m-k] [q] \qquad
  A = 256 \quad q = 524287\]
  
  Cette fonction permet d'associer des entiers aux mots d'une manière qui
  minimise le risque de collision. 

  \vfill
  \begin{question}
    \'Ecrire une fonction \code{hash s i j} qui calcule la clé associée à
    $t[i]\ldots t[j-1]$. Quelle est la complexité de cette fonction?
  \end{question}
  \vfill
  
  Cette approche n'apporte néanmoins pas d'amélioration si l'on doit
  calculer la clé associée à chaque facteur. Néanmoins, on observe qu'il
  existe une relation permettant de calculer la clé d'un facteur en temps
  constant à partir de la clé du facteur précédent.

  \vfill
  \begin{question}
    Expliciter cette relation mathématiquement, puis écrire une fonction 
    \code{transition} qui effectue ce calcul.

    En déduire une fonction \code{rk\_egal m} qui construit une fonction 
    utilisable par \code{rk\_applique}. La fonction renvoyée doit renvoyer
    \code{true} lorsque \code{m} est reconnu. Toutes les exécutions de
    cette fonction doivent se faire en temps $O(1)$, sauf la première qui
    peut s'effectuer en temps $O(m)$. 

    En déduire une fonction \code{rk} qui recherche un motif dans un texte.
  \end{question}
  \vfill
  \vfill

\end{document}