GRAAL, une bibliothèque de graphes : mode d’emploi
p. 315-323
Texte intégral
Introduction
1Les grammaires INTEX sous la forme de graphes sont en constante augmentation au sein de la communauté RELEX. Leur éparpillement géographique cause de multiples redondances. Nous décrivons dans cet article une première version d’un outil de gestion en-ligne d’une bibliothèque de graphes, permettant aux utilisateurs de stocker leurs graphes dans un même endroit, de rechercher des informations et de télécharger les grammaires qui les intéressent. D’abord, nous présentons l’organisation générale du système ; puis nous décrivons la représentation interne des données et des différents modules utilisés. Enfin, nous présentons un mode d’emploi sommaire de cette application.
1 - Organisation générale
2Le système que nous proposons a une architecture client-serveur. Le serveur contient une base de données et un certain nombre de modules. Côté client, une interface permet à l’utilisateur d’envoyer ses requêtes au serveur, via le réseau Internet. La base de données (BD) a deux principales entités : les graphes et les utilisateurs. L’entité « Utilisateurs » contient quelques données sur les utilisateurs du système : nom, prénom, mot de passe, organisation, etc. L’entité « Graphes » contient les grammaires sous forme de graphes (physiquement, un fichier « grf » pour chaque graphe), des informations techniques relatives aux graphes (langue, auteur, type, etc.) et de la documentation écrite sur les graphes. Chaque utilisateur a un compte personnel auquel il accède au moyen d’un nom d’utilisateur et d’un mot de passe. Il l’organise librement à l’aide d’un système d’arbre de répertoires comme dans tous les systèmes d’exploitation. Tous les utilisateurs ont accès en lecture à tous les graphes. Les auteurs ont accès en écriture à leurs propres graphes uniquement.
3Le système comporte trois modules :
- un module gérant les échanges sur le réseau comme les envois et les réceptions de requêtes
- un module d’analyse des grammaires
- un module gérant l’accès et la mise à jour des données
2 - Représentation des données
4Les grammaires que nous considérons ont la forme de réseaux récursifs de transitions (W. Woods, 1970 ; M. Silberztein, 1993). Chaque grammaire g possède un alphabet N d’éléments non terminaux, un alphabet T d’éléments terminaux (avec N∩T = Ø), un ensemble de règles G sous la forme de graphes (terme gauche : nom du graphe, soit un élément de N ; termes droits : factorisés sous la forme d’un graphe sur N∪T) et un axiome de départ (ou graphe principal) g0. Par exemple, prenons N = {X, Y, Z}, T = {a, b, c, d} et X correspondant au nom de g0. G est représenté par l’ensemble des graphes ci-dessous (fig. 1, 2 et 3) où chaque étiquette grisée est un élément non-terminal (donc un appel à un sous-graphe). Ainsi, notre grammaire reconnaît des expressions telles que aaccbb ou bcdab.
5Les graphes peuvent contenir des informations de sortie, comme les transducteurs à états finis (J. Berstel, 1979 ; M. Silberztein 1999). Il existe aussi des graphes à mémoire permettant d’élaborer des règles de réécriture (J. Senellart 1999 ; M. Silberztein 1999). Enfin, les graphes appelés graphes-patrons représentent des sur-ensembles de séquences et permettent de convertir des tables de lexique-grammaire (M.Gross 1975) en graphes ou transducteurs à états finis (E. Roche, 1993 ; M. Silberztein 1999). Ces trois différents types de graphes sont tous calculables formellement. Par ailleurs, nous considérons deux styles de typage qui nous serviront tout le long de cet article. Tout d’abord, le type de surface d’un graphe est le type du graphe si l’on n’entre pas dans les sous-graphes, c’est-à-dire si l’on considère que les éléments non-terminaux sont des éléments terminaux. Ensuite, le type profond d’une grammaire est le type de la grammaire si l’on entre dans tous les sous-graphes.
6La base de données est une base de données relationnelle classique contenant des entités et des relations entre ces entités (G. Gardarin, 2000). Chaque entité est une table : les lignes correspondent aux items et les colonnes correspondent aux champs. Les différentes entités peuvent être mises en relation les unes par rapport aux autres. Par exemple, notre bibliothèque contient deux entités : les graphes et les utilisateurs. Ces deux entités sont mises en relation ; par exemple, la relation appelée « est l’auteur de » indique quel utilisateur de la table « Utilisateurs » est l’auteur de tel graphe de la table « Graphes ». Il existe cependant une grosse différence avec les BDs classiques : l’entité « Graphes » contient un objet complexe. En effet, l’un des champs est un pointeur sur un fichier « grf », soit un graphe. Or un graphe INTEX est équivalent à un réseau récursif de transitions, c’est-à-dire un graphe pouvant faire appel à des sous-graphes. Ainsi, pour faciliter l’accès au contenu des graphes et notamment l’exploration des relations entre les graphes, nous construisons un graphe de dépendance pour chaque grammaire. Chaque sommet du graphe correspond à un graphe INTEX g (ou une ligne de la table « Graphes »). Les fils de ce sommet correspondent aux sous-graphes qui sont appelés dans g, comme montré dans la figure 4 qui représente le graphe de dépendance de notre précédent exemple. Si ce graphe est cyclique, la grammaire est strictement récursive. L’union des différents graphes de dépendance forme le graphe de dépendance de la bibliothèque, c’est-à-dire une vue de la base de données.
7Cette représentation sert par exemple pour la suppression de grammaires. En effet, lorsqu’un utilisateur veut supprimer une grammaire, il faut vérifier qu’elle ne soit pas utilisée comme sous-grammaire d’une autre grammaire. Par ailleurs, comme la bibliothèque risque de contenir des dizaines de milliers de graphes, il est nécessaire d’utiliser des méthodes qui accélèrent le temps de traitement des requêtes sur le contenu des grammaires. Une première méthode consiste à indexer les graphes selon le lexique employé. Ainsi, pour chaque élément x de l’alphabet T, on associe la liste des graphes qui le contiennent, comme montré dans le tableau 5 pour les symboles terminaux de notre exemple précédent.
8Une deuxième méthode consiste à filtrer les graphes selon les premières transitions des grammaires. Ainsi, pour chaque x de T, on associe une liste de couples (u, v) où v est un graphe INTEX qui contient x et u est une valeur booléenne (0 ou 1) qui indique s’il existe une transition du graphe v partant de l’état initial et contenant l’étiquette x. De même, dans le graphe de dépendance, sur chaque transition reliant le sommet w au sommet z, on ajoute une valeur booléenne (0 ou 1) indiquant si, dans le graphe INTEX correspondant à w, il existe une transition partant de l’état initial et contenant un appel au sous-graphe z, comme montré dans la table 6 et dans la figure 4.
3 - Les modules
9Le module de gestion des échanges sur le réseau est le régulateur de l’application. Il se trouve à la fois du côté serveur et du côté client. Coté client, il permet d’envoyer une requête au client, de recevoir la réponse du serveur et de faire appel à des fonctions FTP de téléchargement de fichiers. Coté serveur, il gère la réception des requêtes provenant du client, lance le module de gestion des données, gère les flux de requêtes et envoie les résultats des requêtes au client. Il gère aussi les erreurs qui peuvent survenir lors des échanges sur le réseau. Chaque requête a un protocole précis que gère le module. Par exemple, lors de la session d’ouverture d’une connexion, l’utilisateur rentre son nom d’utilisateur (u) et son mot de passe (p) dans deux champs de l’interface. Ces deux séquences sont capturées par le programme qui envoie alors au serveur une requête du type « je veux me connecter avec u pour nom d’utilisateur et p pour mot de passe ». A la réception, le serveur analyse la requête, et la traite, tout en interdisant le traitement d’autres requêtes. Il renvoie alors au client un résultat du type « l’utilisateur u peut se connecter », si les données envoyées sont correctes. Après réception et analyse, le client lance une fonction FTP qui permet de télécharger, du serveur sur le client, certains fichiers contenant des informations sur l’état de la bibliothèque (liste des graphes principaux présents, liste des langues utilisées, etc.). Une fois cette opération réussie, le client envoie un message au serveur avertissant que la procédure est terminée. Le serveur autorise alors le traitement d’autres requêtes. Il existe un protocole particulier pour chaque type de requêtes.
10Le module d’analyse des grammaires est utilisé des deux cotés de l’application. Il calcule certaines propriétés d’une grammaire g, de graphe principal g0. Etant donné g0, il construit automatiquement le graphe de dépendance de g ; ainsi, il est facile d’obtenir la liste des sous-graphes dépendants de g0. Les graphes de la grammaire sont aussi indexés, comme montré dans la section précédente. Il calcule aussi le type de surface de chaque graphe de g et le type profond de g.
11Le module de gestion des données est le véritable moteur de la bibliothèque. Il permet d’insérer, de supprimer et de rechercher des informations dans la base de données. La mise à jour de la BD se fait en général en deux étapes : une simulation sur les données chargées en mémoire puis une mise à jour réelle des fichiers sur le disque dur. Pour prévenir les problèmes d’intégrité des données physiques, nous utilisons un système de sauvegarde temporaire de l’état précédent de la BD et des différents fichiers manipulés. Contrairement aux BDs classiques, la mise à jour n’est pas triviale. Elle nécessite l’utilisation d’algorithmes manipulant le graphe de dépendance et notamment les composantes fortement connexes lors de la suppression d’une grammaire (N. Christofides, 1975). En effet, un graphe ne peut être supprimé s’il est dépendant d’un graphe que l’on ne veut pas supprimer. Cet algorithme n’est pas explicité en détail dans cet article. La recherche d’information dans la bibliothèque se fait actuellement sur des critères simples comme la langue, l’auteur ou le type d’un graphe. Mais il est prévu d’implémenter des algorithmes de recherche d’information sur le contenu des graphes : par exemple, rechercher toutes les grammaires contenant un mot ou une séquence de mots ; rechercher toutes les grammaires reconnaissant une séquence de mots ou rechercher si une grammaire donnée n’existe pas au moins partiellement dans la bibliothèque. Il conviendra d’utiliser au préalable des filtres par rapport au lexique afin de ne traiter qu’un petit nombre de graphes et ainsi améliorer les performances en temps.
4 - Mode d’emploi
12Dans cette section, nous détaillons certaines fonctionnalités implémentées et montrons leur mode d’emploi. Chaque utilisateur a un compte personnel auquel il accède avec un mot de passe et un nom d’utilisateur. Ainsi, avant toute chose, un utilisateur doit créer son compte personnel. Il peut alors se connecter au moyen d’une session d’ouverture. Chaque utilisateur dispose de son compte comme il l’entend, notamment en créant ou en supprimant des répertoires.
13L’interface client possède deux parties principales : une partie mise à jour de la bibliothèque et une partie recherche d’information. Pour insérer une grammaire dans la bibliothèque, l’auteur doit d’abord fournir de la documentation associée à celle-ci. Pour l’aider dans sa tâche, il existe un éditeur de documentation. Il suffit de sélectionner un graphe principal. Aussitôt, la liste des graphes de la grammaire est calculée et affichée à l’aide du module d’analyse des grammaires. La sélection d’un des graphes provoque l’apparition de la fiche signalétique associée à celui-ci. Cette fiche que doit remplir l’auteur comprend par exemple des informations comme la langue, le type, les mots-clés et la description linguistique du graphe. Afin de faciliter le travail de l’auteur, certains champs comme celui correspondant au type du graphe sont automatiquement calculés. Une fois la documentation faite, l’auteur choisit un répertoire de destination, puis indique le dictionnaire spécifique associé (si nécessaire) et/ou la table de lexique-grammaire associée (si graphe-patron) et, enfin, télécharge ses graphes sur le serveur. Un utilisateur a aussi la possibilité de rechercher des informations sur les graphes stockés dans la bibliothèque. Pour l’instant, un explorateur avancé lui permet de trier et filtrer des graphes selon des critères simples : langue, auteur, type du graphe, date de création, etc. L’utilisateur peut filtrer les graphes de la bibliothèque selon un nombre de critères qu’il choisit, et peut les trier selon l’ordre de critères qu’il préfère.
Conclusion et perspectives
14La première version de l’outil que nous avons présentée est relativement simple ; mais, c’est une base solide pour de futurs développements et donc pour de nombreuses améliorations aux services existants. En plus de l’implémentation d’outils de recherche complexe sur le contenu des grammaires, nous souhaitons construire un système d’information personnalisé qui permettrait aux utilisateurs de suivre l’évolution des graphes qui les intéressent et de formuler des suggestions et commentaires aux auteurs.
Bibliographie
Des DOI sont automatiquement ajoutés aux références bibliographiques par Bilbo, l’outil d’annotation bibliographique d’OpenEdition. Ces références bibliographiques peuvent être téléchargées dans les formats APA, Chicago et MLA.
Format
- APA
- Chicago
- MLA
Bibliographie :
Berstel Jean, (1979), Transductions and Context-free Languages, Teubner Verlag.
Christofides Nicos, (1975), Graph theory : an algorithmic approach, Academic press, New-York London San Francisco.
Gardarin Georges, (2000), Bases de Données, Objet et relationnel, Editions Eyrolles, Paris.
Gross Maurice, (1975), Méthodes en syntaxe, Hermann, Paris.
Roche Emmanuel, (1993), Analyse syntaxique transformationnelle du français par transducteurs et lexique-grammaire, Thèse de doctorat en informatique, Paris, Université Paris 7.
Senellart Jean, (1999), Localisation d’expressions linguistiques dans de gros corpus, Thèse de doctorat en informatique, Université Paris 7.
Silberztein Max, (1993), Dictionnaires électroniques et analyse automatique de textes : Le système INTEX, Masson, Paris.
Silberztein Max, (1999), Transducteurs pour le traitement automatique des textes, In : Lamiroy B. (Ed.), Le lexique-grammaire, Travaux de linguistique, Bruxelles, pp. 127-142.
10.1145/355598.362773 :Woods William, (1970), Transition Network Grammars for Natural Language Analysis, Communications of the ACM, Vol. 13 : 10.
Auteur
Université de Marne-la-Vallée
Mconstant@univ-mlv.fr
Http://ladl.univ-mlv.fr
Le texte seul est utilisable sous licence Licence OpenEdition Books. Les autres éléments (illustrations, fichiers annexes importés) sont « Tous droits réservés », sauf mention contraire.
La formation d’une opinion démocratique
Le cas du Jura, de la révolution de 1848 à la « république triomphante » (vers 1895)
Pierre Merlin
2017
Les mutations récentes du foncier et des agricultures en Europe
Gérard Chouquer et Marie-Claude Maurel (dir.)
2018
Deux frontières aux destins croisés ?
Étude interdisciplinaire et comparative des délimitations territoriales entre la France et la Suisse, entre la Bourgogne et la Franche-Comté (xive-xxie siècle)
Benjamin Castets Fontaine, Maxime Kaci, Jérôme Loiseau et al. (dir.)
2019
Un mousquetaire du journalisme : Alexandre Dumas
Sarah Mombert et Corinne Saminadayar-Perrin (dir.)
2019
Libertaire ! Essais sur l’écriture, la pensée et la vie de Joseph Déjacque (1821-1865)
Thomas Bouchet et Patrick Samzun (dir.)
2019
Les encyclopédismes en France à l'ère des révolutions (1789-1850)
Vincent Bourdeau, Jean-Luc Chappey et Julien Vincent (dir.)
2020
La petite entreprise au péril de la famille ?
L’exemple de l’Arc jurassien franco-suisse
Laurent Amiotte-Suchet, Yvan Droz et Fenneke Reysoo
2017
Une imagination républicaine, François-Vincent Raspail (1794-1878)
Jonathan Barbier et Ludovic Frobert (dir.)
2017
La désindustrialisation : une fatalité ?
Jean-Claude Daumas, Ivan Kharaba et Philippe Mioche (dir.)
2017