École Polytechnique, promotion X2002 - Majeure informatique 1
Cours de Caml - TD 4 & 5. Énoncé par David Monniaux.

Moteur de recherche

Nous désirons réaliser un moteur de recherche simplifié permettant de demander, dans un ensemble de textes, quels sont ceux qui contiennent tel ou tel mot, ou une combinaison logique de ces mots.

Un corrigé global est disponible ainsi que des solutions commentées.

1. Tri-fusion

Nous allons commencer par une petite disgression par un algorithme bien connu et qui se programme très facilement en Objective Caml.

  1. Programmez une fonction separer : 'a list -> 'a list * 'a list qui sépare une liste en deux sous-listes d'égale longueur à un près (par exemple en mettant un élément sur deux dans chaque sous-liste).
  2. Programmez une fonction fusionner : ('a -> 'a -> bool) -> 'a list -> 'a list -> 'a list qui fusionne deux listes triées en une seule liste triée au vu d'une relation de préordre total (une relation ≤ transitive et réflexive, telle que pour tout a et b, ab ou ba, représentée par une fonction qui retourne true sur deux arguments a et b si et seulement si ab). Par exemple, fusionner ( <= ) [1; 4; 9] [3; 5; 9] donne [1; 3; 4; 5; 9; 9].
  3. Programmez une fonction trier : ('a -> 'a -> bool) -> 'a list -> 'a list qui trie une liste au vu d'une relation de préordre total.

2. Lecture des fichiers

Nous ne lirons en fait qu'un seul fichier, contenant une pièce de théâtre divisée en actes et en scènes, Don Juan ou le Festin de pierre (sauvez ce fichier dans votre répertoire), de Molière.

Le fichier comprend successivement :

Il s'agit de lire successivement toutes les lignes contenues dans des scènes, de découper les mots, et de les stocker dans une table associant à chaque mot les couples (acte,scène) correspondants.

  1. On donne une fonction simple permettant de déterminer si un caractère est une lettre minuscule française :
    let est_une_lettre l = l >= 'a' && l<= 'z'
      || l = 'é' || l = 'è' || l = 'ê'
      || l = 'â' || l = 'ô' || l = 'î'
      || l = 'ù'|| l = 'à' || l = 'ç';;
    

    Écrivez une fonction decouper_mots : (string -> 'a) -> string -> unit telle que decouper_mots f s va appeler appeler f successivement avec comme argument les mots trouvés dans s. Par exemple, si s vaut "chat<->meau objectif", la fonction appelera (f "chat"), (f "meau") et (f "objectif"). Vous vous servirez des fonctions du module String.

  2. Écrivez une fonction chaine_au_debut : string -> string -> bool telle que chaine_au_debut chaîne ligne vale true si et seulement si le début de ligne est identique à chaîne. On prendra notamment garde au cas où chaîne est plus longue que ligne.
  3. Utilisez le foncteur Set.Make afin de créer un module SceneSet gérant des ensembles de couples d'entiers. Lors de la définition du module compatible avec Set.OrderedType, on aura type t = int * int. La fonction compare pourra soit être la fonction Pervasives.compare, soit une fonction ad hoc, par exemple implémentant l'ordre lexicographique.
  4. Définissez le type table des tables de hachage (module Hashtbl) des string vers les couples d'entiers. Ces tables permettent d'associer à un mot les couples (acte,scène) correspondants. Écrivez une fonction ajouter_dans_table : table -> int*int -> string -> unit telle que ajouter_dans_table table (acte,scène) mot ajoute (acte,scène) à l'ensemble des scènes associées au mot.
    Vous utiliserez la fonction Hashtbl.replace plutôt que la fonction Hashtbl.add. Cette dernière permet de « cacher » l'ancienne valeur associée à une clef, et de la récuperer au moment du remove, ce qui n'est pas le comportement attendu ici.
  5. Réalisez une fonction mots_de_table : table -> 'a list qui sorte la liste (non triée) des mots dans la table.
  6. Affichez la liste triée des mots.
  7. Réalisez une fonction indexer_fichier: string -> table telle que indexer_fichier nom_de_fichier

    On se reportera avec bonheur à la documentation des fonctions open_in et suivantes; on pourra utiliser le module Buffer, l'équivalent en Caml de la classe StringBuffer de Java.

  8. Programmez des fonctions annexes d'affichage et essayez de chercher les scènes contenant quelques mots.

3. Calcul sur les formules

On définit le type inductif suivant :

type formule =
    Mot of string (* les pages contenant le mot *)
  | Et of formule * formule (* les pages vérifiant les deux formules *)
  | Ou of formule * formule (* les pages vérifiant au moins une des deux formules *)
  | Moins of formule * formule (* les pages vérifiant la première mais pas la deuxième formule *)
  1. Définissez une fonction récursive rechercher_formule : table -> formule -> SceneSet.t. En utilisant les opérations sur les ensembles dans SceneSet, rechercher_formule table formule doit retourner l'ensemble des pages décrites par la table et vérifiant la formule. Essayez cette fonction sur quelques exemples.

Analyse lexicale et syntaxique

On désire que l'utilisateur puisse taper les formules de recherche selon une représentation textuelle. Pour cela, on va utiliser un langage défini par une grammaire hors contexte :

expr2 ::= ( expr0 )
        | mot
expr1 ::= expr1 & expr2
        | expr2
expr0 ::= expr0 | expr
        | expr0 \ expr
        | expr2

On en déduit le type des lexèmes :

type token =
  | EOF
  | PAREN_GAUCHE
  | PAREN_DROITE
  | SYMBOLE_ET
  | SYMBOLE_OU
  | SYMBOLE_MOINS
  | Identificateur of string;;

Vous avez le choix, pour réaliser l'analyse syntaxique de cette grammaire, entre une réalisation à la main (voir TD5 et TD6 d' INF431) ou l'utilisation de OCamlLex et OCamlYacc.

En cas de réalisation à la main, vous procéderez ainsi. Un type tokenizer contient l'état de l'analyseur lexical, initialisé au début d'une chaîne de caractères :

type tokenizer = {
  command : string;
  mutable point : int;
  mutable current_token : token option };;

let create_tokenizer command = {
  command = command;
  point = 0;
  current_token = None }
  1. Créez une fonction sauter_espaces : tokenizer -> unit qui saute les caractères d'espacement (' ', '\r', '\n').
  2. Créez une fonction read_next_token : tokenizer -> token qui lit le prochain lexème et le retourne (en « avalant » les caractères concernés).
  3. En utilisant le champ current_token, implémentez read_current_token : tokenizer -> token qui lit le lexème courant sans l'ôter, et la fonction advance_token : tokenizer -> unit qui passe au lexème suivant.
  4. Testez ces fonctions en faisant afficher la suite des lexèmes sur quelques exemples.
  5. Implémentez l'analyse syntaxique.

Pour finir, vous pouvez tester votre moteur de recherche sur quelques exemples.

$ ./indexeur
Requete: (aime | homme) & femme
((aime | homme) & femme) :
(1, 4) (2, 3) (4, 4)