Mini moteur de recherche www

 

Algorithmes et Structures de données ESTE - T2 - Projet 2004
L. Perroton

 

Le but de ce projet est d'étudier et de développer un petit indexeur de page web locales avec la possibilité de rechercher des pages contenant un certain mot clé.

1 Objectif du projet

Vous devez réaliser un programme qui permet 1) de constituer un dictionnaire des mots présents dans des fichiers au format HTML (pages web), et 2) d'effectuer une recherche sur les mots de ce dictionnaire pour afficher les noms de fichiers (ou ``URL'' pour un véritable moteur de recherche) des pages web correspondantes (i.e. dans lesquels ces mots étaient présents).

2 Langage HTML

Une page web est un fichier texte qui utilise un langage particulier pour la mise en page et l' affichage des graphiques et du texte dans un navigateur tel que Netscape ou Internet Explorer. Ce langage est HTML: Hyper-Text Markup Language. Votre programme devra lire de tels fichiers et extraire le texte du contenu en éliminant toutes les instructions liées à la mise en page pour ne conserver que le texte. C'est un langage simple dont le principe de base est d'avoir toujours une balise (ou ``tag'' en anglais) de début (ex. <center> ) et une balise de fin (ex. </center> ) pour définir une zone d'action d'une commande.1

Pour simplifier le problème, votre programme devra tout simplement ignorer tout texte compris entre les caractères < et > qui sont des instructions HTML.

3 Le Dictionnaire

Un dictionnaire est un ensemble de mots associé à une référence, en l'occurrence les noms des fichiers des pages web où ces mots avaient été recensés. Un mot sera une suite de caractère alphabétiques exclusivement. Pour éviter de surcharger le dictionnaires de mots non significatifs, on indexera que les mots les plus fréquents d'un fichier HTML. Il faudra donc compter le nombre d'occurrence des mots dans un fichier HTML et ne retenir que les N premiers. De plus, on n'indexera pas non plus les mots de moins de L caractères, considérés comme non significatifs. On n'indexera pas non plus les nombres. N et L sont des paramètre qui devront être réglables, par exemple N égale à 10, 20 ou 30, et L est égale à 4 ou 5 (on ne garde que les 10, 20 ou 30 plus fréquents mots et de longueur supérieurs à 4 ou 5).

Le dictionnaire sera constitué par ajout itératif des mots des fichiers des pages web. La liste des fichiers des pages web devra être fournie au programme sous forme d'un fichier contenant lui-même les noms des fichiers HTML, à raison de un par ligne. Le dictionnaire devra contenir les mots, et pour chacun de ces mots, la liste des pages web où ils ont étés rencontrés, et la fréquence du mot dans cette page web. Lors de la recherche d'un mot, si le mot est présent dans plusieurs pages web, elles seront affichés par ordre décroissant de ces fréquences (les pages où ce mot est le plus fréquent sont considérés plus pertinentes).

Les paramètres N et L seront lus au démarrage du programme dans un fichier de configuration. Ce fichier contiendra également une liste de mots à exclure, c'est à dire que les mots dans cette liste ne devront pas être ajoutés au dictionnaire s'ils se présentent dans les fichiers HTML à indexer. Un exemple de syntaxe du fichier de configuration peut être :

N 35
L 4
liste
mots
exclus

4 Fonctionnalités du programme

Le programme devra offrir les fonctionnalités suivante avec un menu :

construire
le dictionnaire. Le programme demandera de saisir le nom du fichier contenant la liste des noms des fichiers des pages web à indexer et construira le dictionnaire
ajouter
au dictionnaire les mots d'une seule page web (saisie au clavier sous forme du nom du fichier correspondant)
rechercher
dans le dictionnaire les pages web contenant un mot clé. Le programme demande le mot à rechercher et affiche les pages web (les noms de fichiers) qui contiennent ce mot avec sa fréquence.
quitter
le programme.
Les fonctionnalités additionnelles suivantes sont destinés à l'administration du dictionnaire et vous seront précieuses pour la mise au point de votre programme :

liste
le nombre et la liste des mots présents dans le dictionnaire
détail
du contenu du dictionnaire. Affiche la liste des mots du dictionnaire, ainsi que les références de fichiers associés à chaque mot
modifier
les paramètres pour construire le dictionnaire (N et L) ou d'autres paramètres éventuels (s'il y en a). Cette fonction vous permet d'observer le comportement de votre programme en modifiant des paramètres sans recompiler.
Enfin vous pouvez ajouter toute autre fonctionnalité que vous jugerez utile.

5 Fonctionnalités optionnelles (obligatoires pour les redoublants et ex-ESIEE)

Vous pourrez ajouter les fonctionnalités optionnelles suivantes :

sauvegarder
le dictionnaire dans un fichier pour pouvoir le conserver entre 2 exécutions du programme
charger
un dictionnaire préalablement sauvegardé dans un fichier

6 Test

Vous pourrez tester le bon fonctionnement de votre programme à l'aide de 2 ou 3 pages web simples (par exemple la votre si vous en avez une ou celle d'un collègue).

Pour un test en grandeur nature, vous pourrez expérimenter votre indexeur avec les fichiers de la documentation technique d'une librairie de programmation graphique TiX qui se situe dans: /user/info_lib/Tck/Tix4.1.0/man. Ce répertoire contient 47 fichiers HTML et il sera extrêmement utile aux programmeurs de pouvoir chercher les pages contenant un mot clé. La liste des noms de ces fichiers est dans /user/info_lib/ts2/algo/fichiers.moteur.recherche

7 Evaluation

Le projet sera réalisé en binômes. Il sera évalué par une présentation orale de 20 minutes maximum avec un des professeurs responsable de l'évaluation. Vous effectuerez une démonstration de votre programme. Le source de votre programme devra être suffisamment clair et commenté pour être présenté et compréhensible dans l'intervalle de temps de la validation orale. Vous devez rendre au professeur responsable lors de cette présentation, un listing de vos sources et un jeu de tests.

Les évaluations devront avoir lieu Lundi 22, Mardi 23 et Mercredi 24 novembre 2004. Il est à la charge des binômes de convenir d'un rendez-vous avec le professeur responsable de son évaluation par e-mail, téléphone ou en allant le voir directement à son bureau, afin que l'évaluation soit faite avant le mercredi 24 au soir.

Mr. Cornec
binômes du groupe 2 (5105 - corneca@esiee.fr - 0145926634)
Mr. Perroton
binômes du groupe 1 (5254 - perrotol@esiee.fr - 0145926714)







Footnotes

...1
Pour plus d'explications sur HTML, voir les livres à la doctec, ou consulter les liens sur HTML que vous pouvez trouver sur le web, par exemple: http://www.ncsa.uiuc.edu/General/Internet/WWW/HTMLPrimerAll.html ATTENTION: La lecture de cette documentation n'est pas indispensable pour le projet.

laurent 2004-10-11