La notion de graphe de dépendance

Spécifications et organisation du système

Le système que nous proposons est un système client-serveur distribué. Le serveur dispose d’une base de données relationnelle formée principalement de grammaires locales et autres informations (utilisateurs, etc.). Il comporte également un module traitant les requêtes arrivant du client. Le client est constituéd’une interface au moyen de laquelle l’utilisateur envoie ses requêtes au serveur. L’interface permet à l’utilisateur de visionner les résultats de ses requêtes. Les requêtes sont essentiellement de deux ordres : mise à jour des données et accès aux données.
Cette bibliothèque en-ligne où seront accumulées l’ensemble des grammaires locales servira de plate-forme d’échange de données pour la communautéRELEX. L’accès des utilisateurs au catalogue des grammaires locales existantes permettra d’éviter de la redondance dans les travaux. Par ailleurs, le formalisme des grammaires locales encourage la réutilisation de grammaires déjà existantes : chaque chercheur peut incorporer dans ses graphes les briques des autres. Ainsi, il est nécessaire que chaque utilisateur puisse accéder à l’information et télécharger les graphes de la bibliothèque le plus facilement possible.

Spécifications

Mise à jour des données

Chaque utilisateur du système peut insérer de nouvelles grammaires dans la bibliothèque. Cette procédure est simple. Pour cela, le nombre de champs à remplir est limitéafin de ne pas rendre la tâ che pénible. Des procédures d’analyse automatique des grammaires ont également étémises en place (ex : calcul de la liste des graphes présents dans une grammaire donnée). Chaque utilisateur est responsable de ses propres grammaires, qu’il modifie ou supprime à sa discrétion. Les autres utilisateurs n’ont pas accès en écriture à ces graphes. Un utilisateur possède un compte personnel auquel il accède au moyen d’un nom d’utilisateur et d’un mot de passe. Il l’organise au moyen d’une arborescence de répertoires. Dans le futur, nous souhaiterions autoriser le fait que plusieurs utilisateurs puissent partager l’accès en écriture à un même graphe.
La politique adoptée pour le stockage des graphes est la suivante. L’utilisateur a le choix entre insérer ou supprimer un graphe seul (c’est-à -dire sans ses sous-graphes) ou une grammaire complète (un graphe principal et récursivement tous ses sous-graphes). Il est nécessaire de tenir compte de la dépendance entre les graphes : quel graphe utilise quel graphe ? Par exemple, on décide que l’on ne peut supprimer un graphe s’ il est utilisédans un graphe que l’on ne veut pas supprimer. Par ailleurs, nous avons une politique de duplication des graphes qui peut être coûteuse en espace mémoire mais qui nous semble indispensable. Supposons que la bibliothèque comporte un graphe GA construit par un utilisateur U1. Supposons maintenant qu’un utilisateur U2 veuille insérer sur son compte un graphe GB dont GA est un sous-graphe. Une première solution consisterait à stocker physiquement GB et l’appel à GA serait symbolisé par un pointeur vers le graphe GA dans le compte de U1. Cette solution paraît à première vue idéale car elle permet une forte économie de mémoire. Cependant, selon le contexte de la grammaire locale, les deux graphes GA peuvent évoluer différemment. Nous citons par exemple le cas des grammaires du discours boursier de T. Nakamura (à paraître) qui utilise les graphes généraux de dates de M. Gross mais les a adaptés à son contexte de travail. Le système de pointeurs n’autorise pas des évolutions divergentes des grammaires. Nous décidons donc de dupliquer les graphes du type GA. Cette stratégie a plusieurs inconvénients. D’abord, elle est coûteuse en mémoire. Ensuite, elle supprime le lien qui existait entre les deux graphes de type GA. Ainsi, lorsque l’un des deux est modifié, l’autre ne l’est pas automatiquement. Un bon moyen de résorber les effets néfastes de la duplication des graphes est d’avertir les auteurs lors de la modification d’un graphe qui les intéresse.

Accès aux données

L’un des buts de la bibliothèque est de donner aux utilisateurs l’accès au catalogue des grammaires locales stockées. Comme leur nombre risque d’exploser111, il a été nécessaire d’implanter un moteur de recherche. Les critères de recherche sont multiples. Nous partons du plus simple au plus complexe. Tout d’abord, il est possible de construire un filtre sur des caractéristiques simples des grammaires tels que l’auteur, la langue, le type (avec ou sans sorties, avec ou sans variables, … ), etc. Ce filtrage est une opération classique dans les bases de données relationnelles traditionnelles.
Nous avons également implémenté une procédure de recherche de graphes à partir d’une description par mots-clés de la grammaire recherchée. Pour cela, une documentation des graphes (du moins, des plus importants d’entre eux) est nécessaire. Pour éviter de rebuter les auteurs, nous avons mis en place un éditeur de documentation. La procédure de recherche revient alors à une procédure classique de recherche documentaire dans une base de données textuelles (cf. moteurs de recherche Google, Yahoo, etc. : recherche de pages Web).
Enfin, on peut effectuer des recherches de grammaires à partir de leur contenu lexical. Un utilisateur peut donner un ensemble de mots ou étiquettes qu’il souhaite voir apparaître dans la grammaire qu’il cherche. Il peut également trouver toutes les grammaires de la bibliothèque qui contiennent ou reconnaissent les séquences qu’il désire.
La visualisation du résultat des recherches est fondamentale. Il convenait de trouver une représentation simple mais qui contient des informations nécessaires. A partir de la liste trouvée, l’utilisateur peut télécharger les graphes qui l’intéressent.

Quelques perspectives

L’application d’une grammaire locale à un texte implique la consultation des dictionnaires lorsque ses étiquettes symbolisent un ensemble de mots (<N> pour tous les noms). Si le graphe utilise des mots techniques qui ne se trouvent pas dans le dictionnaire du système, alors il pourra être utile d’ajouter le dictionnaire associéà la grammaire lors de l’insertion de cette dernière dans la bibliothèque112. Par ailleurs, les grammaires servent aussi à appliquer le contenu de tables syntaxiques : il faudra donc donner la possibilité d’insérer des tables syntaxiques.
Nous pourrions également réaliser des recherches approximatives de séquences à l’aide des outils de l’équipe de F. Guenthner (CIS, Université de Munich). Par ailleurs, on pourrait imaginer qu’un utilisateur ayant entamé une description sous la forme d’un graphe veuille savoir s’il n’existe pas dans la bibliothèque un graphe similaire (cf. section sur l’intersection de grammaires).

Fonctionnement général

Notre système a une architecture distribuée client-serveur (cf. Gardarin, 1999) permettant d’accumuler dans un même lieu des grammaires locales, construites à divers endroits géographiques. Ce système permet par ailleurs aux chercheurs du domaine de récupérer les informations et données qui les intéressent. Il contient une base de données (des composants linguistiques), un moteur et un système de requêtes permettant de mettre à jour la base de données ou d’accéder aux informations contenues par celle-ci. Dans son aspect général, notre système ne diffère pas des autres systèmes d’information.
Le fonctionnement général de ce système est également très classique (cf. schéma ci-dessous). Un utilisateur situédu cô téclient montre son désir d’envoyer une requête via l’interface. Les données nécessaires au traitement de cette requête sont alors réunies et le client construit la requête désirée au bon format à l’aide d’un module de construction de requêtes. Puis, le client se charge d’envoyer cette requête au serveur via Internet. Là , un module de réception de requêtes gère le flux des requêtes entrantes en n’en laissant passer qu’une seule à la fois (les autres sont mises en attente). Le gestionnaire des requêtes pré-analyse la requête et la distribue à la procédure adéquate du moteur qui modifie ou extrait des informations de la base de données. Le résultat du traitement est ensuite envoyé au constructeur de réponses (sur le serveur). Celui-ci élabore une réponse formatée qui est envoyée via Internet au client. Ce dernier réceptionne la réponse et l’envoie au gestionnaire des réponses qui, en fonction de la requête, représente d’une certaine manière le résultat sur l’interface.

Base de données

Notre base de données relationnelle113 représentée dans la figure ci-dessous contient cinq entités représentées par des ellipses :
• les dictionnaires
• les grammaires
• les tables
• les langues
• les utilisateurs
L’entité centrale est celle des grammaires qui contient un ensemble de graphes. Chaque graphe possède plusieurs champs : un nom pointant vers un fichier le représentant explicitement [extension « .grf »] et vers un fichier le documentant [extension « .gdoc »] plus des caractéristiques (si c’est un graphe à sorties, à variables, etc.). L’entité « utilisateurs » comprend l’ensemble des utilisateurs inscrits : les champs concernent des informations personnelles simples (nom d’utilisateur, mot de passe, nom, prénom, courriel, etc.). Les entités sont liées entre elles aux moyens de relations représentées par des rectangles :
• la relation LangueDeDico indique la langue associée à chaque dictionnaire ;
• la relation UtilEstAuteurDeDico indique les auteurs des dictionnaires ;
• la relation UtilEstAuteurDeGram indique les auteurs des graphes ;
• la relation UtilEstAuteurDeTable indique les auteurs des tables ;
• la relation TableUtiliseGram indique les tables utilisées par les grammaires ;
• la relation DicoUtiliseGram indique les dictionnaires utilisés par les grammaires ;
• la relation UtilEstInterresseParGram indique les utilisateurs intéressés par les
grammaires et qui souhaitent recevoir un courrier électronique quand elles sont modifiées.
Notons que la relation entre une grammaire et une langue est réalisée par transitivité car il existe toujours un dictionnaire associéà une grammaire. Les dictionnaires par défaut sont les dictionnaires du système (dictionnaires DELA).

Normalisation des grammaires locales

Représentation théorique des grammaires

Les grammaires locales sont théoriquement équivalentes à des réseaux récursifs de transitions (RTN)114 [W.A. Woods, 1970]. Les grammaires peuvent donc être définies comme des 4-uplets <N, T, aut, S> où N est un alphabet115 de symboles non-terminaux, T un alphabet de symboles terminaux, aut un ensemble de règle-automates sur NÈT, S l’axiome de départ (ou l’automate principal). Pour tout X Î N, il existe, dans l’ensemble des règles-automates aut, un automate116 aut(X) = <Q(X), q0(X), F(X), d(X), NÈT> où Q(X) est un ensemble d’états, q0(X) l’ensemble des états initiaux, F(X) l’ensemble des états finaux, d(X) Í Q(X)´(NÈT)*´Q(X) l’ensemble des transitions. Soit la grammaire G = <N, T, aut, S>. Etant donné G, chaque symbole non terminal X de N symbolise un sous-automate de G mais aussi une grammaire incluse dans G dont X est l’axiome de départ. Par facilité d’écriture, nous appelons X, l’automate aut(X) dans G. Pour tout automate X de G, si le symbole non terminal Y appartient
• son alphabet, c’est-à -dire si l’automate X contient le symbole non-terminal Y, alors l’automate Y est un sous-automate de X. Nous parlerons aussi de sous-automate direct. Notons qu’un symbole non terminal X de G peut être considéré comme inutile lorsque aut(X) n’est pas directement ou indirectement appeléà partir de S.
l’on note B) est l’union d’un ensemble de grammaires G1, … , Gn. Ainsi, comme les langages algébriques sont fermés par union, B est aussi un RTN. On peut considérer B comme le quadruplet <NB,TB, autB, SB> tel que :
• NB est l’union des alphabets de non terminaux Ni auxquels on adjoint un nouveau symbole SB, l’axiome de B;
• TB est l’union des alphabets de terminaux Ti ;
• AutB est l’union des ensemble Auti, plus la règle-automate associée à l’axiome SB.
La règle-automate autB(SB) reconnaît les axiomes Si avec i Î [1,n], ainsi, on a :
L(autB(SB)) = {Si | i Î [1,n]}
L(autB(SB)) est le langage reconnu par autB(SB). Nous appellerons autB(SB) l’automate d’union. Nous gardons le terme d’automates principaux de B pour S1, S2, … , Sn.
Remarque importante :
Jusqu’à ce chapitre, nous avions utilisé le mot « graphe » pour ce que nous appelons maintenant automate. Ces deux notions sont habituellement utilisées de faç on équivalente par les utilisateurs d’Intex et d’Unitex mais, dorénavant, nous ne parlerons plus que d’automates pour ce qui concerne les règles des grammaires locales car, un peu plus tard, nous utiliserons le terme de graphe pour dénoter d’autres types de données.

Normalisation des grammaires en pratique

Les grammaires locales susceptibles d’être stockées dans la bibliothèque sont construites à l’aide des éditeurs de graphes d’Intex et d’Unitex. Les deux formats sont très proches mais leur système de codage des caractères est différent : Unitex utilise le codage Unicode 3.0 standard UTF-16 Little Indian (1 caractère = 2 octets) et Intex utilise un codage ASCII (1 caractère = 1 octet). On peut aussi imaginer que l’on veuille utiliser des grammaires d’un autre type telles que les grammaires algébriques (dans un format de fichier particulier).
Afin d’avoir des procédures de traitement les plus efficaces possibles, nous décidons de représenter les grammaires de manière standard dans notre système. Nous gardons une copie de chaque grammaire dans sa version d’origine pour que cette dernière puisse être utilisée dans le logiciel pour lequel elle a étéconstruite. Cela étant dit, il est nécessaire de normaliser les grammaires en se ramenant à une représentation la plus proche possible de la théorie et en supprimant les informations inutiles. Les formats choisis sont les plus puissants. Ainsi, nous décidons de coder les caractères en Unicode afin de pouvoir traiter toutes les langues. Le processus de conversion d’une grammaire ASCII en une grammaire Unicode ne pose pas de problème majeur car il existe des procédures établies. Les grammaires sont représentées sous la forme de RTN118 . Dans le cas où l’on veuille utiliser des grammaires algébriques, il conviendra de convertir ces dernières dans le bon formalisme : par exemple, au moyen de l’algorithme de Nederhof (2000).
La normalisation des grammaires dépend entièrement de ce que nous voulons en faire. Notre système doit contenir des outils de recherche d’information dans ces grammaires et plus exactement sur leur contenu linguistique. La représentation graphique n’a aucune utilitépour ces outils. Elle peut donc être supprimée. Par ailleurs, les grammaires que nous traitons sont des grammaires d’analyse linguistique dont les automates n’ont pas de sortie. Ainsi, nous décidons d’enlever toutes les informations de sortie des grammaires qui en contiendraient. L’information de l’existence de telles sorties est extraite automatiquement à partir de l’analyse automatique des grammaires à insérer et placées dans des champs spéciaux de la table contenant les informations sur les grammaires.
Les éditeurs d’automates offrent une grande libertéaux auteurs des automates. Par exemple, les auteurs peuvent construire des transitions dont l’étiquette comprend plusieurs symboles consécutivement. Pour faciliter les traitements informatiques, chaque transition comprenant une séquence de n symboles simples est découpée en n transitions d’éléments simples. Il existe de multiples opérations de normalisation des transitions. Certaines étiquettes apportent peu d’informations par rapport à la complexité qu’elles génèrent dans les opérations. Elles sont alors modifiées. Par exemple, l’étiquette # qui interdit l’espace entre deux symboles est remplacée par l’étiquette vide119. On perd dans ce cas des informations mais elles ne sont pas indispensables.
Des procédures classiques de synchronisation des automates permettent de supprimer les transitions étiquetées par le mot vide des règles-automates. L’émondation supprime les états inutiles et la minimisation rend notre représentation optimale (cf. T. Sudkamp, 1997).
Pour se rapprocher de la représentation théorique, il convient d’extraire des automates les deux alphabets. La distinction entre les symboles non terminaux et les symboles terminaux est immédiate : le symbole « : » sert de préfixe à chaque symbole non terminal (c’est-à -dire une chaîne de caractère qui désigne le nom d’un sous-automate).
Un point cependant pose problème. L’alphabet des éléments terminaux ne comporte pas que des symboles élémentaires. En effet, si l’on se place au niveau linguistique, on constate que la grande majorité des étiquettes employées ne sont pas atomiques, c’est-à -dire qu’elles représentent un ensemble de symboles élémentaires. Nous examinons chaque type d’étiquettes au cas par cas.
• les chiffres et les caractères non-alphabétiques
Ces symboles sont par définition minimaux, donc ils ne posent pas de problèmes. Exemples : «1»,«2»,… ,«+»,«-».
• les séquences de lettres :
Une séquence de lettres délimitée par deux séparateurs forme un mot graphique. D’un point de vue non linguistique, une telle séquence peut former une unitéatomique. Cependant, d’un point de vue linguistique, un mot sous sa forme graphique peut être considéré comme un ensemble de mots (ou d’étiquettes lexicales) ayant la même forme graphique (fléchie) dans les dictionnaires. Par exemple, si l’on prend le mot donne, il y a deux analyses possibles : soit c’est un nom qui a pour forme canonique donne, soit c’est un verbe qui a pour forme canonique donner. Le nombre d’éléments (ou cardinal) de cet ensemble dépend de la finesse de codage du dictionnaire. Dans un dictionnaire où chaque entrée n’est associée qu’à une catégorie grammaticale, le cardinal du mot danse [notécard(danse)] serait égal à 2.