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.
Nous allons commencer par un algorithme bien connu et qui se programme très facilement en Objective Caml.
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).
fusionner : ('a -> 'a -> bool) -> 'a list -> 'a list -> 'a list
qui fusionne deux listes triées en une seule liste triée,
pour une relation de préordre total (une relation ≤
transitive et réflexive, telle que pour tout a et
b, a ≤ b ou
b ≤ a,
représentée par une fonction qui retourne true
sur deux arguments a et b
si et seulement si a ≤ b). Par exemple,
fusionner ( <= ) [1; 4; 9] [3; 5; 9]
donne
[1; 3; 4; 5; 9; 9]
.
trier : ('a -> 'a -> bool) -> 'a list -> 'a
list
qui trie une liste pour une relation de préordre total donnée.
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.
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
.
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.
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.
table
des tables de hachage
(module Hashtbl
)
des string
vers les ensembles de 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.
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.
mots_de_table : table -> 'a list
qui renvoie la liste (non triée) des mots dans la table.
indexer_fichier: string ->
table
telle que indexer_fichier
nom_de_fichier
table
videint ref
)
On se reportera à la documentation des fonctions
open_in
et suivantes ; on pourra utiliser le module Buffer
,
l'équivalent en Caml de la classe StringBuffer
de Java.
On définit le type de formules 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 *)
rechercher_formule : table
-> formule -> SceneSet.t
. En utilisant les opérations sur les
ensembles dans SceneSet
, rechercher_formule
table formule
doit renvoyer l'ensemble
des pages décrites par la table et vérifiant la
formule. Essayez cette fonction sur quelques exemples.
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 ::= expr2 & expr1 | expr2 expr0 ::= expr1 | expr0 | expr0 \ expr1 | expr1
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 (expliquée ci-dessous) ou l'utilisation d'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 }
sauter_espaces : tokenizer
-> unit
qui saute les caractères d'espacement
(' '
, '\r'
,
'\t'
, '\n'
).read_next_token : tokenizer
-> token
qui lit le prochain lexème et le renvoie (en «
avalant » les caractères concernés).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.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)