SmallSearchEngine

Ce projet est un mini moteur de recherche local implémenté en C++.

Fonctionnalités principales

• Parsing de documents HTML locaux
• Construction d’un graphe de liens dirigé
• Calcul du PageRank :
  • par itération de puissance
  • par simulation Monte Carlo
• Accélération du sampling via :
  • alias method
  • optimisations SIMD (AVX2)
• Indexation texte avec index inversé
• Recherche simple combinant score textuel et PageRank

Structure du projet

├── build/                  
│   └── Makefile
├── include/
│   ├── alias_sampling.hpp
│   ├── document.hpp
│   ├── graph.hpp
│   ├── html_parser.hpp
│   ├── indexer.hpp
│   ├── markov_chain.hpp
│   └── pagerank.hpp
├── src/
│   ├── alias_sampling.cpp
│   ├── graph.cpp
│   ├── html_parser.cpp
│   ├── indexer.cpp
│   ├── main.cpp
│   ├── markov_chain.cpp
│   └── pagerank.cpp
├── test/
│   ├── index.html
│   └── ...
├── .gitignore
└── README.md

• include/ : headers
• src/ : implémentations
• test/ : faux site HTML servant de corpus de test, texte provenant de copiés-collés de Wikipedia.
• build/ : compilation via Makefile

---

Détails d’implémentation

Chaînes de Markov & PageRank

Le PageRank est modélisé comme une chaîne de Markov finie :

• la matrice de transition est construite à partir du graphe de liens,
• un facteur d’amortissement est appliqué pour garantir l’ergodicité.

Deux méthodes de calcul sont proposées :

• itération de puissance (déterministe),
• simulation Monte Carlo (random walks).

Pour la simulation :

• le tirage des transitions utilise la méthode de l’alias,
• certaines parties sont optimisées avec AVX2.

---

Parsing HTML & indexation

Les documents HTML sont parsés à l’aide de libhtmlcxx.

Pour chaque document :

• extraction du texte visible (hors script/style),
• extraction des liens <a href="...">,
• construction d’un index inversé (mot → documents),
• construction du graphe de liens dirigé.

La recherche combine :

• un score textuel simple (TF),
• et le score PageRank du document.

---

Dépendances

Pour installer les dépendances (g++ et libhtmlcxx), lancez les commandes suivantes :

sudo apt install build-essential
sudo apt install libhtmlcxx-dev

Compilation

cd build
make
./a.out

---

Exemples de résultat

query> lion
- ../test/mammiferes/lion.html | score=0.706698
- ../test/mammiferes.html | score=0.235566
- ../test/mammiferes/elephant.html | score=0.117783

query> chaud
- ../test/mammiferes.html | score=0.117783

query> froid
- ../test/reptiles.html | score=0.117783

query> et
- ../test/mammiferes/lion.html | score=0.353349
- ../test/mammiferes/elephant.html | score=0.235566
- ../test/mammiferes.html | score=0.235566
- ../test/index.html | score=0.235566
- ../test/reptiles/cobra.html | score=0.117783
- ../test/oiseaux/moineau.html | score=0.117783

query> espérance de vie
- ../test/mammiferes/elephant.html | score=1.4134
- ../test/mammiferes/lion.html | score=1.4134
- ../test/oiseaux/moineau.html | score=1.06005
- ../test/reptiles/cobra.html | score=0.706698
- ../test/mammiferes.html | score=0.235566
- ../test/index.html | score=0.235566
- ../test/oiseaux.html | score=0.117783