Automates lexicaux

Les automates et transducteurs finis ont prouvé leur utilité dans une large va- riété d’applications en informatique linguistique. Ils permettent par exemple une représentation compacte et à accès rapide pour les lexiques à large cou- verture [Revuz, 1991] et sont à la base d’algorithmes efficaces à de nom- breuses étapes du traitement des langues naturelles, de l’analyse phonolo- gique et morphologique [Kaplan et Kay, 1994, Karttunen et al., 1992] et la reconnaissance de la parole [Mohri, 1997] jusqu’à l’analyse syntaxique de texte [Roche et Schabes, 1997]. Dans cette partie, nous nous intéressons plus particulièrement au modèle des grammaires locales tel que présenté dans [Gross, 1997]. Ce formalisme gram- matical permet de faire des descriptions sous forme de graphes de formes lin- guistiques complexes relevant d’un même domaine syntaxique [Fairon, 2000] ou sémantique [Constant, 2000] ; il a été adopté dans de nombreuses re- cherches en traitement automatique des langues par l’intermédiaire des logi- ciels INTEX [Silberztein, 1993] et Unitex [Paumier, 2003b]. Une grammaire locale est traditionnellement définie comme un automate à états finis. Cepen- dant, les deux modèles ne sont pas équivalents. En particulier, la définition formelle de certaines notions telle que le déterminisme diffère entre les deux modèles et certains algorithmes de la théorie des automates finis (tels que la déterminisation ou l’intersection de deux automates finis) n’ont pas un com- portement correct lorsqu’ils sont appliqués directement sur les grammaires locales. Nous présentons, dans ce chapitre, le modèle des automates lexicaux, qui consiste en une extension du modèle des automates finis, dans lequel les transitions sont étiquetées par des masques lexicaux. Les masques lexicaux sont des étiquettes ensemblistes permettant de représenter de manière uni- forme et structurée les différents symboles qui étiquettent les grammaires locales. Nous montrons comment nous sommes parvenus à implémenter di- verses opérations sur les automates lexicaux, telles que la déterminisation, l’intersection ou la complémentation.Les automates lexicaux permettent de représenter les grammaires locales mais nous nous en servons également pour la représentation des corpus de texte après la phase d’étiquetage morpho-syntaxique, la structure d’automate permettant de représenter les ambiguïtés d’étiquetage et de découpage. Ainsi, l’application d’une grammaire locale à un texte se résume à une opération sur deux automates lexicaux. Nous présentons certaines de ces opérations telles que la levée d’ambiguïtés lexicales par intersection d’automates ou l’annota- tion de texte par application d’un transducteur lexical.

Les logiciels INTEX et Unitex intègrent un éditeur de graphes permettant la construction de grammaires locales. Dans ces environnements, les états sont laissés implicites et les symboles de l’alphabet d’entrée sont représentés dans des boites connectées entre elles par des arcs non étiquetés. Ces grammaires sont ensuite traduites sous la forme d’automates pour faciliter les traitements informatiques. La figure 2.1, par exemple, présente un graphe simple qui décrit un verbe conjugué à l’un des 8 temps de l’indicatif. Les 4 temps simples sont indiqués par les codes P (présent), I (imparfait), J (passé simple) et F (futur) ; les 4 temps composés sont décrits dans le chemin du haut passant par l’auxiliaire être ou avoir conjugué suivi du verbe au participe passé (code K). La figure 2.2 présente la même grammaire dans sa représentation duale sous la forme d’un automate fini. Ainsi, les symboles qui étiquettent les transitions d’une grammaire locale sont de types hétérogènes. D’autre part, ce sont des symboles ensemblistes, dans le sens où une étiquette peut reconnaître un ensemble d’unités lexicales. L’en- semble décrit par certains symboles, tels que <NB> ou < !DIC> par exemple, peut même être de cardinal non borné.

Du fait de ces caractéristiques, le mo- dèle diffère substantiellement du modèle des automates finis tel qu’il est tradi- tionnellement défini en théorie des langages (dans [Hopcroft et Ullman, 1979] par exemple). En effet, les définitions formelles de certaines notions fonda- mentales, telles que le déterminisme, sont modifiées. Formellement, un au- tomate fini est dit déterministe s’il a au plus un unique état initial et si pour chaque symbole de l’alphabet d’entrée, il a pour tout état au plus une transition sortante étiquetée par ce symbole. L’utilisation d’automates dé- terministes permet souvent d’obtenir des traitements optimaux puisque leur comportement est déterminé, à chaque étape du calcul, de façon unique pour toute entrée. Or, si nous prenons l’automate de la figure 2.2, même si ces propriétés sont vérifiées, l’automate ne peut pas pour autant être considéré comme déterministe puisque, lorsqu’il est positionné à l’état 0, la lecture du mot étiqueté {ai,avoir.V :P1s} peut positionner l’automate dans l’état.