Projet de programmation -- Moteur de recherche Web

• Présentation (objectif, contenu, bibliographie)
• Ressources
• Organisation
• Calendrier

Présentation

(Voir aussi un résumé du projet lors de la réunion du 26 janvier 2005, amphi 34B.)

L'objectif du projet est d'implémenter un "mini" moteur de recherche. Un moteur de recherche (comme Google) est composé de trois modules :

• le crawler (araignée, robot) qui collecte les pages en suivant récursivement les liens ;
• l'indexer (répertoire) qui interprète et stocke les pages collectées ;
• le module d'interrogation qui interprète les requêtes et renvoie les résultats dans l'ordre de leur importance pour la requête.

Le point de départ de ce projet est une implémentation primitive du moteur. Cette implémentation utilise :

• un crawler séquentiel
• un indexer de documents et de liens implémenté avec un BDD SQL
• un module d'interrogation en PHP pour la recherche et l'affichage des résultats (dans un ordre aléatoire)

Cette implémentation doit être améliorée dans au moins deux des points suivants :

• CP : crawler parallèle (distribué) (article)
• CI : crawler incrémental
• RA : stockage compacte et interprétation des URI
• RD : stockage compacte des pages
• ID : indexage des documents pour une recherche rapide
• IG : indexage des liens pour une calcul sur le graphe
• PR : calcul d'une priorité des pages en général (PageRank)
• SH : calcul d'une priorité des pages par recherche (HITS)
• EX : autre amélioration citée dans le tutoriel Google.

Les connaissances nécessaire à la réalisation du projet sont :

• Réseau (CP, CI) :
  • URI [notes de cours]
  • langage HTML [notes de cours]
  • protocole HTTP et serveurs HTTP [notes de cours]
  • interface CGI [notes de cours]
  • programmation socket TCP (Java ou C) [ notes de cours, tutoriel Java]
• Programmation concurrente (CP, ID, IG, PR) :
  • en Java [tutoriel Java]
  • en C (voir cours Systeme 2 Licence)
• Algorithmique (partie indexer et moteur d'interrogation) :
  • compression de texte (RA, RD)
  • indexage des données (ID, IG)
  • parcours de graphes (PR, SH)
• Moteurs de recherche (toute partie) :
  • recherche d'information sur le web [ tutoriel, article]
  • moteur de recherche Google
  • algorithme PageRank (PR)
  • algorithme HITS (SH)
• Gestionnaire de versions (toutes parties) :
  • CVS
  • RCS
• Générateur de documents et documentation (toutes parties) :
  • javadoc, doxygen
  • LaTeX

Ressources

• Implementation primitive initiale
• Autre implementation, moins primitive
• Squelette de rapport en LaTeX
• Architecture du projet
• Liste de discussion

Organisation

• Le responsable du projet est Mihaela Sighireanu. L'enseignement a lieu le 2eme semestre. La première séance a lieu le 2 février. L'horaire est le suivant :

  jour	heure	salle
  mercredi	12h30	J7 ou TP 108

• Évaluation : le projet est individuel. La note finale est calculée comme (Ex-mid + Ex-fin)/2 où
  • Ex-mid est la note de la soutenance mi-terme : date à fixer mi-avril.
  • Ex-fin est la note de la soutenance finale : date à fixer fin juin.
  A chaque soutenance, vous devez rendre un rapport et faire une demo.
• Inscription : par mail (Sujet: inscription projet long) au responsable du projet.
  • L'inscription est valide si vous recevez un mail de confirmation dans les 72h.
  • Consultez la liste d'inscrits.

Calendrier des séances

Pour toute information sur les cours et les TD contactez les enseignants.

Dernière modification : Wed Mar 2 16:24:34 CET 2005
URL: http://www.liafa.jussieu.fr/~sighirea/cours/mini-google/index.html