# Rapport DAAR Nico & Théo lébo ###### tags: `DAAR` # Introduction Le projet qui nous a été confié était de réaliser une application web de moteur de recherche de document dans une bibliothèque de livres sous format textuel. Il est grandement inspiré de la base de Gutenberg. L'idée est de proposer aux utilisateurs la possibilité de trouver et de lire des livres, parmi une grande bibliothèque (qui s'agrandit de jour en jour) qu'ils auront cherché par un/des mot(s) clef(s) ou par des expressions régulières. Nous avons donc travaillé afin d'offir à l'utilisateur une expérience agréable et intuitive (via notre système de suggestions) en plus d'une bonne réactivité (temps de recherche court). Par la suite, nous allons présenter avec précision notre architecture et détailler nos différents choix techniques faits ainsi que leurs implémentations. # Architecture Notre moteur de recherche s'appuie sur une architecture en trois couches : data, serveur et client. Elles vont resspectivement se charger de la gestion des documents en temps que tels, de la gestion des recherches et l'aspect affichage et le retour du résultat de la recherche. ## Couche data Dans cette couche nous allons nous charge de gérer tout ce qui concerne les documents en temps que tel. C'est à dire leur intégrations et leur stockage. ### Le stockage des documents : La base de donnée La base de donnée est une base de donnée relationnelle postgreSQL qui a l'architecture suivante : ![](https://i.imgur.com/fkt7zdX.png) Les tables qui représentent les propriétés de chaque livres sont : - **Books :** Cette table permet de stocker les propriétés propre d'un livre. C'est à dire son titre, son contenu et l'id de son auteur. L'objectif de cette table est de mettre a disposition les informations essentielles de chaque livre. - **Author :** Cette table permet de sotcker les informations des auteurs - **Tags :** Il s'agit d'une des deux tables de l'index inversé. On va stocker ici chaque mot qui apparait au moins une fois dans un des livres. - **Tagmaps :** Ici nous allons stocker l'existence d'un mot donné dans un livre donné. Il s'agit de l'index inversé car en faisant une recherche sur un id de mot on va retrouver l'ensemble des livres où il apparait. - **Subjects :** Il s'agit de métadonnées ajoutées sur chaque livre par le *projet Gutenberg* d'où proviennent l'ensemble des documents qui permet de connaitre le contenu du livre. - **SubjectMaps :** Ici nous allons stocker le lien qui existe entre chaque *"subject"* et un livre donné. Les tables liées aux besoins de stocker des informations par utilisateurs sont : - **User :** Il s'agit d'un simple moyen d'identifier un utilisateur de stocker son existence. La notion de mot de passe n'existe pas ici. Un utilisateur est seulement défini par son nom. - **ConsultedBooks :** Cette table sert à stocker l'ensemble des livres consultés pour chaque utilisateur. Ces tables sont très utilisées pour la suggestion. Et les tables restantes ne sont pas utilisées dans l'architecture mais ont été maintenu pour illustrer la progression de l'architecture : - **Historic :** Cette table devait servir a stocker les recherches que faisait chaque utilisateur - **SearchResult :** Cette table devait servir a stocker les résultats des recherches de chaque utilisateurs. Ces tables devaient servir pour la suggestion mais finalement suite a des évolutions dans la data servant de base à ces suggestions il a été décidé de les abandonnées. ### L'intégration des données La donnée provient du *Gutenberg Project* et est récupérée via l'API gutendex. Lorsqu'elle est envoyée à notre API elle est formatée comme suit : ```json [ { "title": "Titre du livre", "author_name": "Nom de l'auteur", "full_text_pointer": "Lien permettant de télécharger le texte du livre", "subjects": [ "Sujet 0", "Sujet 1", "Sujet 2", "Liste des sujets" ] } ] ``` On va servir de cela pour populer la base de donnée et surtout notre index inversé en suivant ce processus : ``` Tokenisation des textes: Entrée : full_text (texte complet) -> String Sortie : tokensList -> List[String] ft_min -> Mise en minuscule de full_text ft_onlyChar -> Retrait des signes de ponctuation et des chiffres de ft_min ft_longWords -> Retrait de tous les mots n'étant pas entre 4 et 26 caractères de ft_onlyChar res -> On divise le texte a chaque espace de ft_longWords Retourner res ``` Ensuite une fois cette liste de tokens créée il est possible d'intéger les nouveaux dans la base de donnée et de créer les liens s'imposant permettant de savoir quel mot se trouve dans quel livre sans avoir recourt au texte complet. Ce processus permet de n'avoir dans notre base de donnée une table "*Tags*" d'a peu près la taille du dictionnaire de la langue utilisée pour les livres. Cette table va évidemment grossir de manière importante si on ajoute de nouvelles langues. Un processus similaire est utilisé pour les subjects mais ces derniers sont nettement moins nombreux. Il a été ici choisis une approche **ETL**. Un *data warehouse* est constitué avec de la donnée déjà préparée et prête à l'emploi de façon a gagner du temps lors de la recherche. La logique ici est de faire porter la plus grosse partie du calcul lors de l'intégration de donnée pour offrir à l'utilisateur une rapidité d'exécution plus rapide lors de ses recherches. ## Couche serveur La couche serveur est la couche où vont avoir lieux l'ensembe des calculs permettant d'offrir des fonctionnalités à l'utilisateur. ### La recherche #### La recherche simple La recherche dites "simple" s'appuie sur un mot ou un ensemble de mot dont on veut faire la recherche dans les livres préalablement indexés. Pour trouver les livres dans lesquels il y'a la chaine de caractères recherchées on va simplement faire une requête SQL s'appuyant sur les tables : *Tags*, *TagMaps* et *Books*. La première table va être utilisée pour récupérer l'ID qui va nous permettre de trouver l'ensemble des ID de livre utilisant ce mot en utilisant la seconde table. La dernière permet de récupérer les informations des livres associés à ces ID. Une recherche simple permettant la recherche de plusieurs mots a aussi été implémentée. Elle se contente de tokenizer son entrée de l'exact même façon que pour lors de la tokenisation spécifiée plus haut puis uitilise le mot clef "*in*" du SQL. Son retour peut être traduit par : $$ search\_multiple\_words("A \ B \ C") \equiv \\ search\_one\_word("A") \cup search\_one\_word("B") \cup search\_one\_word("C") $$ #### La recherche avancée La recherche dites "avancée" s'appuie quand à elle sur une regex. Cela permet à l'utilisateur de faire des recherches couvrant plus de cas et de variante qu'un simple mot. De la même façon que pour la recherche simple la recherche avancée va s'appuyer sur la puissance offerte par le moteur PostgreSQL. Une recherche avancée avec regex permettant la recherche sur les textes complets des livres a elle aussi été implémentée. Elle permet de faire des recherches retournant des phrases entières car au contraire des autres recherches cette dernière a accès à l'intégralité du texte en un bloc. #### Le classement des résultats Les résultats de chacune des ces recherches doivent être classé pour l'utilisateur pour lui permettre de voir en premier lieu le livre correspondant au mieux à sa recherche. Pour cela nous créons un graphe de Jaccard, dont l'algorithme sera décrit plus bas, avec un seuil de 0.1 en utilisant les "*subjects*" des livres retournés par la recherche. Puis une fois ce graphe créer la "*closeness centrality*" de chaque point du graphe, de chaque livre, est calculée et va permettre de classer les livres. En d'autre terme, pour déterminer la pertinence des résultats nous les classons de celui partageant le plus de "*subject*" avec les autres à celui qui en partage le moins. Par exemple si l'on prend les quatre premiers résultats retournés par l'API à la recherche du mot "whales" : ```json [ { "id": "988de489-f05b-4da6-9be2-a527ddb14f1b", "title": "The Works of Rudyard Kipling: One Volume Edition", "author_name": "Kipling, Rudyard", "centrality": 3.8544516274053273 }, { "id": "7fbc26d8-21c1-4df2-b0ce-d6f1f5407b0d", "title": "Hazlitt on English Literature: An Introduction to the Appreciation of Literature", "author_name": "Hazlitt, William", "centrality": 3.625767755479648 }, { "id": "12c09120-d397-4f81-ba82-a53dd46b201f", "title": "The Man That Corrupted Hadleyburg, and Other Stories", "author_name": "Twain, Mark", "centrality": 3.588742644076034 }, { "id": "700c5c94-1116-4509-be08-db1169c7f714", "title": "The Best Short Stories of 1919, and the Yearbook of the American Short Story", "author_name": "unknow", "centrality": 3.5807352750225654 } ] ``` On peut observer que le livre placer le plus en haut est *The Works of Rudyard Kipling: One Volume Edition*. La liste des sujets auxquels il est lié est : *fiction*, *stories*, *english*, *short* et *poetry*. Si l'on fait pareil pour les trois livres restants ont obtient : | Hazlitt on English Literature: An Introduction to the Appreciation of Literature | The Man That Corrupted Hadleyburg, and Other Stories | The Best Short Stories of 1919, and the Yearbook of the American Short Story | |:--------------------------------------------------------------------------------:|:-------------------------------------------------------------------------------------------------------------------------------------------------------:|:----------------------------------------------------------------------------:| | english<br/>literature<br/>history<br/>criticism | humorous<br/>customs<br/>city<br/>honesty<br/>states<br/>life<br/>social<br/>fiction<br/>stories<br/>century<br/>town<br/>short<br/>american<br/>united | fiction<br/>stories<br/>century<br/>short<br/>american | On observe que de nombreux sujets se retrouvent. Alors que si l'on consulte la même liste pour le dernier livre de la liste, *New Zealand Moths and Butterflies (Macro-Lepidoptera)*, qui a un score de 0. On a : *lepidoptera* et *zealand*. ### La suggestion Nous avons mis au point un système de suggestions pour l'utilisateur afin de lui permettre de découvrir des livres qu'il n'a pas lu. Pour cela, nous utilisons les 5 derniers livres consultés par l'utilisateur et nous nous basons sur eux pour trouver des livres similaires. Parlons maintenant de la technique. Une fois les 5 derniers livres consultés identifiés, nous formons un ensemble qui est l'union de tous les *subjects* de chacun de ces livres. Notre ensemble de référence est donc formé et l'idée est de trouver, parmi tous les autres livres, les 10 livres les plus similaires. Nous formons un graphe de Jaccard avec tous les autres livres et nous allons renvoyer les 10 voisins du noeud, formé par notre ensemble, les plus proches. La notion de proximité est faite via l'utilisation de l'indice de Jaccard que nous détaillerons plus tard dans le rapport. ## Couche client Dans l'idée de proposer une grande simplicité d'utilisation à l'utilisateur, nous avons opté pour une interface graphique générique et intuitive. ### Maquette Lors d'une première phase de conception (quelques mois avant la phase de développement), nous avons imaginé une première maquette de l'application présentée ci-contre. ![](https://i.imgur.com/nPA8IAA.jpg) Comme nous pouvons le voir, l'interface proposée est très minimaliste et très épurée. ### Interface finale En ce qui concerne l'implémentation finale, nous nous sommes grandement inspiré de notre maquette, en la revoyant un petit peu. L'interface a été réalisée sur Angular 13 avec l'utilisation de Angular Material. ![](https://i.imgur.com/g708Eqf.jpg) Nous avons donc une barre de recherche pour faire les recherches. Lorsqu'il s'agit d'une recherche avec expression régulière, il suffit d'activer le slider button et de choisir via les boutons radios qui apparaissent, sur quoi la recherche va être effectuée. En-dessous de la barre de recherche se trouve un espace réservé aux suggestions. Ainsi, dès que l'utilisateur a des suggestions, elles apparaîtront ici et l'utilisateur pourra cliquer dessus pour accéder directement à la page du livre. # Algorithmes utilisés ## Closeness centrality Dans un graphe connecté, la centralité de proximité (ou *closeness centrality*) d'un noeud est une mesure de la centralité dans un réseau, calculée comme la somme de la longueur des chemins les plus courts entre le nœud et tous les autres nœuds du graphe. Ainsi, plus un noeud est central, plus il est proche de tous les autres noeuds. La centralité est ici utilisée pour permettre la classification des livres en fonction de leur placement dans le graphe de Jaccard. ``` closenessCentrality Entrée: Graphe non-orienté et pondéré G Sortie: Liste de paires <ID du noeud, Entier représentant la centralité du noeud> res = Liste de paires <ID du noeud, Entier représentant la centralité du noeud> Pour chaque noeud N dans G: res[N.id] = sum(distance du plus court chemin entre N et tous les autres sommets) retourner res ``` La complexité de cet algorithme sera de $O(n) = n*PCC$ avec $PCC$ la complexité de l'algorithme du plus court chemin choisis. Si l'on prend l'algorithme de Dijkstra (ce qui est le cas ici) nous arrivons donc a une complexité de : $$ O(n) = n*((a*n)\log n) $$ avec $a$ le nombre d'arrêtes. ### Comparaison La *closeness centrality* était en concurrence avec deux autres types de centralité très présentes dans la littérature : page rank et betweenness. **Page rank :** Page rank est l'algorithme utilisé par Google pour classer les résultats de leur pages en fonction de la popularité de chaque page. Plus une page va être mentionnée sur une page populaire plus cette dernière sera considérée comme populaire. **Betweenness :** Il s'agit ici de compter le nombre de fois où un noeud agit comme un point de passage le long du plus court chemin entre deux autres noeuds. La raison pour lauqelle nous avons choisis la centralité par proximité est principalement le manque de sens dans leur utilisation ici. Par exemple *Page Rank* n'est pas adapté à notre sujet car ce dernier mesure la popularité de pages. Mais ici il n'est pas sujet de popularité car les livres ne font pas référence les uns aux autres et leur *subjects* sur lesquels nous nous basons n'ont pas vocation a être des pointeurs. Le score dans ce cas là aurait eu une pertinence moindre. Le cas de la *Betweeness* est sembable: appliqué à un graphe de Jaccard cette centralité nous aurait retournée en premier lieu les livres ayant le plus en commun avec certains autres livres de l'ensemble plutôt que tous les livres liés à la recherche. La centralité par proximité nous permet de classer en premier les livres ayant un grand nombre de *subjects* en commun avec l'ensemble des livres retournés par la recherche et donc d'assurer une pertinence importante dans notre recherche. ### Tests Nous allons observer le temps d'exécution pour une série de 4 mots recherchés ayant différents retour de recherches. | whales | france | irradiant | enfourme | | ------ | ------ | --------- | -------- | | 206 | 1169 | 1 | 2 | Et on va observer une augmentation proportionnelle du résultat : ![](https://i.imgur.com/Y2vWFdE.png) ### Conclusion En conclusion, la notion de centralité est une notion particulièrement importante dans un moteur de recherche, sinon le classement des résultats, chose primordiale, n'a aucun sens. Mais son temps de calcul est un frein important aux performances de l'application et dans un cadre d'amélioration devras être changé de place dans le process. ## Création du graphe de Jaccard Le graphe de Jaccard est utilisé pour la classification des résultats des recherches. Ce genre de graphe est basé sur la notion d'**Indice de Jaccard**. L'indice de Jaccard, également connu sous le nom de coefficient de similitude de Jaccard, est une statistique utilisée dans la compréhension des similarités entre les ensembles d'échantillons. Cette mesure met l'accent sur la similarité entre des ensembles d'échantillons finis, et est formellement définie comme la taille de l'intersection divisée par la taille de l'union des ensembles d'échantillons. $$ J(A, B) = \frac{|A \cap B|}{|A \cup B|} $$ Ici les deux ensembles choisis sont : les listes des *subjects* de deux livres. Si leur indice de Jaccard atteint ou excède une valeur donnée définie expérimentalement alors on créer une arrête entre les deux livres. ``` createJaccardGraph: Entrée: Liste de Paires "SM_input" de forme <ID du livre, liste des ids des subjects de ce livre>, Entier "seuil" Sortie: Un graphe non-orienté pondéré représentant un graphe de Jaccard res -> Graphe vide Pour chaque bookID dans SM_input: Créer un sommet de label bookID dans res computed -> Liste vide Pour chaque nodeA correspondant à un ID de livre dans SM_input: Si nodeA n'est pas dans computed: Pour chaque nodeB correspondant à un ID de livre dans SM_input: valueJ -> J(SM_input[A], SM_input[B]) Si J >= seul: Création de l'arrête de nodeA à nodeB dans res retourner res ``` Cet algorithme a une complexité de $O(n)=n^2$ avec $n=|SM\_input|$. ### Méthode de selection du seuil Le seuil a été fixé a $0.1$ dans le code livré. Cette valeur a été choisie suit à l'expérimentation de plusieurs autres valeurs. En effet une valeur plus haute aurait eu tendance a réduire de manière importante le nombre d'arrêtes et donc le calcul de centralité qui suivait n'aurait eu aucun sens. Lors du développement 3 valeurs ont été comparées : $0.5$, $0.3$ et $0.1$. Cette dernière permettait d'avoir un nombre satisfaisant d'arrêtes dans le graphe tout en évitant celle n'ayant aucun sens car en dessous de 10% de ressemblance entre deux ensembles de *subjects* est anodine. En faisant une recherche par mot simple *whales* on obtient 206 résultats. Avec un seuil de 0.5 le graphe de Jaccard généré est celui-ci : ![](https://i.imgur.com/20pCX7y.png) On observe donc une extrême majorité de livres sans lien entre eux (il s'agit de la "couronne" de sommets). Cela pose un problème car la classification se fait entre une petite quantité de livres avec un score supérieur à 0 (le score maximum de centralité est alors de $0.04878048780487805$). Avec un seuil de 0.3 le graphe de Jaccard généré est celui-ci : ![](https://i.imgur.com/hTaupig.png) On observe de la même façon que pour un seuil de 0.5 une extrême majorité de sommets sans liens entre eux. Avec un seuil de 0.1 le graphe de Jaccard généré est celui-ci: ![](https://i.imgur.com/6jzGYCP.png) Il est le seul où l'on peut observer une majorité de sommet liés entre eux. La classification prend alors tout son sens avec une amplitude allant de $3.854$ à $0$ évidement et avec $1.466$ comme dernière valeur supérieure a $0$. ### Tests de performance Pour tester les performances de cet algorithme qui s'exécute a chaque recherche nous avons fait des relever avec différents mots correspondant donc a des nombres différents de retour. En nombre de livres retournés lors de la recherche nous avons : | whales | france | irradiant | enfourme | something | | ------ | ------ | --------- | -------- | --------- | | 206 | 1169 | 1 | 2 | 1858 | Et en terme de temps en secondes nous avons : ![](https://i.imgur.com/geWAR4B.png) ### Conclusion De la même façon que pour la centralité, le graphe de Jaccard est un point primordiale du moteur de recherche mais dans un soucis d'amélioration de performance il faudra le placer en amont de façon a ce que la recherche n'est pas a porter ce calcul fastidieux. # Tests généraux L'analyse de perforamnce d'un moteur de recherche se fait sur le temps de réponse offert pour des recherches en fonction du nombre de réponse. Nous allons donc ici procéder a ces relevés en utilisant la liste de mots utilisée précédement (whales, france, irradiant, attractive et enfourme). **Temps d'exécution d'une recherche en fonction du nombre de livres dans le retour avec une recherche simple d'un mot** ![](https://i.imgur.com/2N71Q5q.png) On observe que le temps augmente de manière importante avec le nombre de livres dans le retour mais de façon proportionnelle. En effet on observe a peu près la même augmentation entre 206 - 969 livres et 969 - 1169 livres. On effectue le même genre de mesure mais avec la recherche avancée en recherchant (`^j`, `(whale)` et `s$`) **Temps d'exécution d'une recherche en fonction du nombre de livres dans le retour avec une recherche avancée sur les tokens** ![](https://i.imgur.com/YWaV17w.png) On observe le même genre de coubre que pour la recherche simple. Les cas avec baucoups de résultats prennent baucoup de temps. ## Profils de la consommation de temps **Pour la recherche simple :** ![](https://i.imgur.com/LGQRyOF.png) **Pour la recherche avancée :** ![](https://i.imgur.com/LzYIgJA.png) Ce qu'on observe grâce à ces deux profilages de temps c'est que c'est le calcul de la centralité qui prend le plus de temps. On comprend alors que le nombre de retour ne pose pas problème en soi, ni même la recherche dans la base de donnée (qui prend un très petit pourcentage du temps totale) mais bien le nombre d'interconection créer entre les livres. Si l'on augmentait le seuil de création dans le graphe de Jaccard on pourrait déjà voir une amélioration mais nous perdrions en pertinence dans la classification des résultats. # Problèmes rencontrés et améliorations futures ## Problèmes rencontrés Lors de la réalisation de ce projet, nous avons été confronté à plusieurs problèmes que nous avons dû surmonter. Tout d'abord nous avons eu des problèmes pour l'ajout des livres dans la base de données. En effet, lorsque nous récupérions des livres en utilisant l'API Gutendex, certains livres avaient leur texte dans une archive ZIP. Ainsi, notre Base De Données essayait d'enregistrer une archive ZIP au format texte, ce qui résultait en un enregistrement de Tag et de TagMaps de chaînes de caractères ne voulant rien dire. Pour contourner cela, nous avons modifié notre script de récupéération de livres pour qu'il ignore ce genre de livres. Egalement, l'ajout dans la base de livres mettait beaucoup trop de temps. Nous nous sommes rendus compte que cela provenait de la tokenization et nous avons donc amélioré notre filtre (par exemple, nous ne tokenizons pas des mots de moins de 4 caractères) pour réduire le temps d'exécution de ce procédé. Enfin, nous avons eu des problèmes de performance causée par le calcul de la centralité au sein du graphe de Jaccard. La solution ici a été de déplacer des calculs plus en amont dans le processus. ## Améliorations possibles Au fur et à mesure de notre avancement dans le projet, nous nous sommes rendus compte que certaines améliorations pourraient être apportées afin de parfaire notre application. Dans un premier temps, il serait intéressant d'apporter un système de pagination sur les résultats des recherches pour améliorer les performances de la recherche. Ensuite, il nous faudrait travailler d'avantage les fonctionnalités de recherche simple et avancée, toujours dans l'optique de l'amélioration de performances. Enfin, il serait intéressant de travailler d'avantage l'interface graphique pour améliorer l'expérience utilisateur. # Conclusion Nous avons donc fourni une application web de moteur de recherche de livre dans une bibliothèque respectant le cahier des charges, à savoir les fonctionnalités de recherche par mot(s) clef(s) et recherche avancée via l'utilisation d'expressions régulières. L'utilisation de l'approche ETL (Extract-Load-Transform) nous permet d'obtenir des temps de recherche convaincant pout le plus grand plaisir de l'utilisateur final.