Brevet FR2847049A1 — publié le 20040514

La présente invention concerne un système d'aide à la recherche d'informations dans une base de connaissances structurée sous la forme d'un graphe. Elle concerne également un procédé mis en oeuvre par ce système. Plus précisément, l'invention concerne un système d'aide à la recherche d'informations, la recherche s'effectuant par déplacement dans le graphe en empruntant les liens de voisinage et en sélectionnant des n u̇ds du graphe, ce système comprenant des moyens de sélection d'un n u̇d parmi les n u̇ds voisins d'un n u̇d déjà sélectionné pour effectuer la recherche. On connaît des systèmes d'aide à la recherche d'informations de ce type notamment dans le domaine du logiciel. Par exemple, certains outils d'aide à l'utilisation d'un logiciel comportent un index d'accès à des rubriques, chaque rubrique renvoyant à une ou plusieurs autres rubriques de l'index. Ces rubriques reliées entre elles forment un graphe dans lequel un utilisateur peut se déplacer pour rechercher la rubrique comportant les informations qui l'intéressent. Pour visualiser les déplacements, ces systèmes comportent des moyens de visualisation d'une page affichant un n u̇d sélectionné du graphe, c'està-dire une rubrique sélectionnée, et ses n u̇ds voisins que l'utilisateur peut sélectionner. Par contre, dès que l'utilisateur sélectionne un n u̇d voisin, les systèmes d'aide classiques présentent une nouvelle page d'affichage du nouveau n u̇d sélectionné et de ses n u̇ds voisins. Le n u̇d sélectionné précédemment disparaît, de sorte que l'utilisateur n'a pas réellement la possibilité de suivre son parcours dans le graphe. En général, ces systèmes comprennent des moyens de mémorisation permettant de revenir aux pages précédemment affichées, mais cela n'est pas suffisant pour empêcher l'utilisateur de se perdre dans le graphe. L'invention vise à remédier à ces inconvénients, en fournissant un système d'aide à la recherche d'informations qui fournisse à un utilisateur des moyens pour se déplacer dans une base de connaissances structurée sous la forme d'un graphe, sans se perdre, et notamment sans revenir à des n u̇ds déjà explorés. A cet effet, l'invention a pour objet un système d'aide à la recherche d'informations du type précité, caractérisé en ce qu'il comporte : des moyens de génération d'un arbre de navigation, chaque n u̇d non terminal de cet arbre de navigation correspondant à un n u̇d du graphe sélectionné lors de la recherche et ayant pour n u̇d fils l'ensemble de ses n u̇ds voisins dans le graphe ; et des moyens d'accroissement de l'arbre de navigation par l'ajout systématique de n u̇ds fils à un n u̇d terminal de l'arbre de navigation, dès que ce n u̇d terminal est sélectionné, les n u̇ds fils ajoutés correspondant chacun à l'un des noeuds voisins dans le graphe du n u̇d terminal sélectionné. L'arbre de navigation généré par le système conserve ainsi en mémoire les déplacements de l'utilisateur dans le graphe. Par exemple, si l'utilisateur sélectionne plusieurs fois un même n u̇d du graphe, celui-ci sera représenté par des n u̇ds différents dans l'arbre de navigation, puisque l'arbre de navigation croît à chaque nouvelle sélection. La mise en évidence par l'arbre de navigation du chemin parcouru dans le graphe de la base de connaissances permet d'éviter à l'utilisateur d'emprunter inutilement deux fois le même chemin. Un système d'aide à la recherche d'informations selon l'invention peut en outre comporter l'une ou plusieurs des caractéristiques suivantes : il comporte des moyens d'affichage de l'arbre de navigation ; il comporte des moyens d'affichage d'un historique d'un chemin parcouru dans le graphe entre le premier n u̇d sélectionné du graphe et le dernier n u̇d sélectionné du graphe ; les moyens d'affichage comportant des moyens de sélection ou de mise en valeur de n u̇ds du graphe, l'historique comporte une branche de l'arbre reliant le premier n u̇d sélectionné dans le graphe et le dernier n u̇d du graphe sélectionné ou mis en valeur. L'invention a également pour objet un procédé d'aide à la recherche d'informations dans une base de connaissances structurée sous la forme d'un graphe comportant des n u̇ds et des liens de voisinage reliant certains n u̇ds entre eux, la recherche s'effectuant par déplacement dans le graphe en empruntant les liens de voisinage et en sélectionnant des n u̇ds du graphe, ce procédé comprenant la sélection d'un n u̇d parmi les n u̇ds voisins d'un n u̇d déjà sélectionné pour effectuer la recherche, caractérisé en ce qu'il comporte en outre les étapes suivantes : la génération d'un arbre de navigation, chaque n u̇d non terminal de cet arbre de navigation correspondant à un n u̇d du graphe sélectionné lors de la recherche et ayant pour n u̇ds fils l'ensemble de ses n u̇ds voisins dans le graphe ; et l'accroissement de l'arbre de navigation par l'ajout systématique de n u̇ds fils à un n u̇d terminal de l'arbre de navigation, dès que ce n u̇d terminal est sélectionné, les n u̇ds fils ajoutés correspondant chacun à l'un des n u̇ds voisins dans le graphe du n u̇d terminal sélectionné. Un procédé d'aide à la recherche d'informations selon l'invention peut en outre comporter la caractéristique selon laquelle il comporte l'affichage de l'arbre de navigation. L'invention sera mieux comprise à la lecture de la description qui va suivre, donnée uniquement à titre d'exemple et faite en se référant aux dessins annexés dans lesquels : la figure 1 représente schématiquement la structure générale d'un système d'aide à la recherche d'informations selon l'invention ; la figure 2 représente une base de connaissance structurée sous la forme d'un graphe ; la figure 3 illustre une fenêtre de présentation d'un arbre de navigation généré par le système de la figure 1. Le système d'aide à la recherche d'informations représenté sur la figure 1 comporte des moyens 10 de stockage pour le stockage d'une base de connaissances structurée sous la forme d'un graphe. Cette base de connaissances sera détaillée en référence à la figure 2. Elle comporte des noeuds et des liens de voisinage reliant certains d'entre eux, toute recherche d'informations dans celle-ci s'effectue par déplacement dans le graphe en empruntant les liens de voisinage et en sélectionnant des n u̇ds du graphe par relations de voisinage. Pour effectuer cette recherche, le système comporte des moyens 12 de génération d'un arbre de navigation. Cet arbre de navigation sera détaillé en référence à la figure 3. On entend par "arbre" un cas particulier de graphe, dans lequel les n u̇ds ont une relation hiérarchique entre eux, chaque lien de l'arbre reliant un n u̇d père et un n u̇d fils. Ainsi, un arbre comporte un n u̇d racine à partir duquel il est construit. Ce n u̇d a un ou plusieurs n u̇ds fils, qui eux-mêmes peuvent avoir également un ou plusieurs n u̇ds fils. Par contre, seul le n u̇d racine n'a pas de n u̇d père. Tous les autres n u̇ds de l'arbre ont un unique n u̇d père. Les n u̇ds terminaux de l'arbre sont ceux qui n'ont pas de n u̇ds fils. Chaque n u̇d non terminal de l'arbre de navigation correspond à un n u̇d du graphe sélectionné lors de la recherche et a pour n u̇ds fils l'ensemble de ses n u̇ds voisins dans le graphe. Le n u̇d racine de l'arbre de navigation est le premier n u̇d du graphe sélectionné par l'utilisateur. Les moyens 12 de génération de l'arbre de navigation comprennent des moyens 14 de sélection d'un n u̇d parmi les n u̇ds voisins d'un n u̇d déjà sélectionné pour effectuer la recherche dans le graphe. Ils comprennent également des moyens 16 d'accroissement de l'arbre de navigation par l'ajout systématique de n u̇ds fils à un n u̇d terminal de l'arbre de navigation, dès que ce n u̇d terminal est sélectionné, les n u̇ds fils ajoutés correspondant chacun à l'un des n u̇ds voisins dans le graphe du n u̇d terminal sélectionné. Ces moyens d'accroissement 16 sont sollicités par les moyens 14, dès qu'une sélection est effectuée par l'utilisateur. Enfin, le système comprend des moyens d'affichage 18 de l'arbre de navigation, permettant à l'utilisateur de visualiser le trajet qu'il a parcouru dans le graphe au cours de la recherche. Il s'agit par exemple de l'écran d'un micro-ordinateur dont l'unité centrale comporte le système d'aide à la recherche d'informations décrit précédemment, sous forme de moyens logiciels. Un exemple de base de connaissances structurée sous la forme d'un graphe 19 est donné sur la figure 2. Il s'agit par exemple d'un dictionnaire de synonymes, les mots du dictionnaire étant représentés par des noeuds 20, notés Ni à N17, deux mots synonymes étant reliés entre eux par un lien de voisinage (22). Ainsi, dans l'exemple représenté sur la figure 12, le n u̇d N1 a pour voisins les n u̇ds N2, N3, N4 et N5 ; le n u̇d N2 a pour voisins les n u̇ds N1, N6 et N7 ; etc. Un exemple de navigation dans le graphe 19 représenté sur la figure 2 est illustré par la fenêtre de navigation 24 représentée sur la figure 3. L'utilisateur interagit avec le graphe 19 représenté dans la fenêtre de navigation 24 au moyen d'un curseur 26 qu'il déplace à l'aide d'une souris. La sélection d'un n u̇d 20 du graphe 19 se fait en double-cliquant sur la souris, lorsque le curseur 26 est positionné sur un n u̇d de l'arbre correspondant au n u̇d 20. De façon classique, il est également possible de mettre en valeur un n u̇d du graphe 19, en cliquant une seule fois sur la souris lorsque le curseur 26 est positionné sur un n u̇d correspondant de l'arbre. Quand un n u̇d est mis en valeur, les autres occurrences de ce n u̇d dans l'arbre de navigation sont elles aussi mises en valeur. La fenêtre de navigation 24 comporte trois parties. Une première partie supérieure 28 retrace un historique de n u̇ds sélectionnés, depuis le n u̇d racine de l'arbre jusqu'au dernier n u̇d sélectionné, ou bien jusqu'au dernier n u̇d mis en valeur. Cet historique correspond à une branche de l'arbre de navigation réalisant le plus court chemin dans l'arbre entre le n u̇d racine de l'arbre et le dernier n u̇d sélectionné ou mis en valeur. Une deuxième partie 30 de la fenêtre de navigation 24 comporte une représentation de l'arbre de navigation en plusieurs colonnes. Une première colonne 32 comporte le premier n u̇d sélectionné dans le graphe 19, c'est-à-dire le n u̇d racine 34 de l'arbre. Dans l'exemple choisi, ce n u̇d racine est le n u̇d Ni. Une deuxième colonne 36 de l'arbre de navigation comporte les n u̇ds voisins du n u̇d racine 34. Ces n u̇ds sont les n u̇ds N2, N3, N4 et N5. De façon récursive, à chaque fois qu'un n u̇d est sélectionné, ses n u̇ds voisins apparaissent sur une colonne suivante de l'arbre de navigation. Lorsqu'un n u̇d est sélectionné dans l'arbre de navigation, un symbole "-" apparaît devant ce n u̇d. Par contre, lorsqu'un n u̇d de l'arbre de navigation n'est pas sélectionné, un symbole "+" apparaît devant ce n u̇d. Dans l'exemple choisi, le n u̇d N1 ayant tout d'abord été sélectionné par l'utilisateur, ses n u̇ds voisins N2, N3, N4 et N5 apparaissent sur la deuxième colonne 36. Sur la deuxième colonne 36, le n u̇d N2 est sélectionné, ce qui a pour effet de faire apparaître ses n u̇ds voisins N1, N6, N7 sur une troisième colonne 38. Sur cette troisième colonne 38, le n u̇d N6 est sélectionné, ce qui a pour effet de faire apparaître ses n u̇ds voisins N2, N8, N13, N14 et N15 sur une quatrième colonne 40. Sur cette quatrième colonne, le n u̇d N13 est sélectionné, ce qui a pour effet de faire apparaître ses n u̇ds voisins N6 et NB sur une cinquième colonne 42. Enfin, sur la cinquième colonne 42, le n u̇d N6 est mis en valeur par l'utilisateur en cliquant une seule fois sur le curseur 26, ce qui a pour effet de faire apparaître ses n u̇ds voisins N2, N8, N13, N14 et N15 dans une troisième fenêtre 32 de la fenêtre de navigation 24, cette troisième fenêtre étant séparée de la fenêtre de présentation 30 de l'arbre de navigation. Les n u̇ds N1, N2, N6, N13, des première, deuxième, troisième et quatrième colonnes respectivement, ayant été sélectionnés, un symbole "-" apparaît devant chacun d'eux. Le n u̇d N6 de la cinquième colonne ayant été mis en valeur, celui-ci est par exemple surligné ainsi que ses occurrences dans l'arbre de navigation (n u̇d N6 dans la troisième colonne). Il en résulte que l'historique affiché dans la première partie 28 de la fenêtre de navigation 24 retrace le chemin parcouru dans l'arbre de navigation entre le premier n u̇d sélectionné N1 et le n u̇d mis en valeur N6. Le procédé d'aide à la recherche mis en u̇vre par le système décrit précédemment comporte ainsi une première étape d'affichage du n u̇d père de l'arbre de navigation précédé du symbole "-", lorsque celui-ci est sélectionné par l'utilisateur. Ensuite, l'arbre de navigation est déployé, en fonction des sélections de n u̇ds du graphe effectuées par l'utilisateur. Dès que l'utilisateur double clique sur un n u̇d terminal de l'arbre de navigation, c'est-à-dire un n u̇d précédé du symbole "+", ceci a pour effet l'affichage dans la deuxième partie 30 de la fenêtre de navigation 24 des n u̇ds voisins du n u̇d sélectionné, sur une colonne supplémentaire. Dans notre exemple, l'utilisateur sait que le n u̇d N6 présenté sur la cinquième colonne 42, a déjà été sélectionné précédemment, puisqu'il apparaît également sur la colonne 38, précédé du symbole "-". Ainsi, l'utilisateur peut éviter de sélectionner une nouvelle fois ce n u̇d pour éviter de tourner en rond dans le graphe. Il apparaît clairement que la génération de l'arbre de navigation et son affichage dans la fenêtre de navigation 24 permettent à l'utilisateur de visualiser les différentes étapes de sa recherche dans le graphe 19. Ainsi, l'utilisateur qui a effectué sa recherche de proche en proche, en commençant par le n u̇d N1, puis en sélectionnant les n u̇ds N2, N6, et N13 peut continuer cette recherche de proche en proche en déployant une branche de l'arbre de navigation, ou bien reprendre sa recherche à partir d'un autre n u̇d de l'arbre de navigation, par exemple, le n u̇d N4 situé dans la deuxième colonne 36. La visualisation au moyen de l'arbre de navigation de l'ensemble des chemins parcourus dans le graphe au cours de sa recherche, permet à l'utilisateur d'éviter de suivre deux fois le même. REVENDICATIONS 1. Système d'aide à la recherche d'informations dans une base de connaissances structurée sous la forme d'un graphe (19) comportant des noeuds (20) et des liens de voisinage (22) reliant certains noeuds entre eux, la recherche s'effectuant par déplacement dans le graphe en empruntant les liens de voisinage et en sélectionnant des noeuds du graphe, ce système comprenant des moyens (14) de sélection d'un n u̇d parmi les n u̇ds voisins d'un n u̇d déjà sélectionné pour effectuer la recherche, caractérisé en ce qu'il comporte : des moyens (12) de génération d'un arbre de navigation, chaque n u̇d non terminal de cet arbre de navigation correspondant à un n u̇d du graphe sélectionné lors de la recherche et ayant pour n u̇ds fils l'ensemble de ses n u̇ds voisins dans le graphe ; et des moyens (16) d'accroissement de l'arbre de navigation par l'ajout systématique de n u̇ds fils à un n u̇d terminal de l'arbre de navigation, dès que ce n u̇d terminal est sélectionné, les n u̇ds fils ajoutés correspondant chacun à l'un des n u̇ds voisins dans le graphe du n u̇d terminal sélectionné. 2. Système d'aide à la recherche d'informations selon la revendication 1, caractérisé en ce qu'il comporte des moyens (18) d'affichage de l'arbre de navigation. 3. Système d'aide à la recherche d'informations selon la revendication 1 ou 2, caractérisé en ce qu'il comporte des moyens d'affichage d'un historique d'un chemin parcouru dans le graphe entre le premier n u̇d sélectionné du graphe et le dernier n u̇d sélectionné du graphe. 4. Système d'aide à la recherche d'informations selon les revendications 2 et 3, caractérisé en ce que les moyens d'affichage comportant des moyens de sélection ou de mise en valeur de n u̇ds du graphe, l'historique comporte une branche de l'arbre reliant le premier n u̇d sélectionné dans le graphe et le dernier n u̇d du graphe sélectionné ou mis en valeur. 5. Procédé d'aide à la recherche d'informations dans une base de connaissances structurée sous la forme d'un graphe (19) comportant des n u̇ds (20) et des liens de voisinage (22) reliant certains n u̇ds entre eux, la recherche s'effectuant par déplacement dans le graphe en empruntant les liens de voisinage et en sélectionnant des n u̇ds du graphe, ce procédé comprenant la sélection d'un n u̇d parmi les n u̇ds voisins d'un n u̇d déjà sélectionné pour effectuer la recherche, caractérisé en ce qu'il comporte en outre les étapes suivantes : la génération d'un arbre de navigation, chaque n u̇d non terminal de cet arbre de navigation correspondant à un n u̇d du graphe sélectionné lors de la recherche et ayant pour n u̇ds fils l'ensemble de ses n u̇ds voisins dans le graphe ; et l'accroissement de l'arbre de navigation par l'ajout systématique de n u̇ds fils à un n u̇d terminal de l'arbre de navigation, dès que ce second terminal est sélectionné, les n u̇ds fils ajoutés correspondant chacun à l'un des n u̇ds voisins dans le graphe du n u̇d terminal sélectionné. 6. Procédé d'aide à la recherche d'informations selon la revendication 5, caractérisé en ce qu'il comporte l'affichage de l'arbre de navigation.