Efficient finite-state algorithms for the application of local grammars

Résumé : Notre travail porte sur le développement d'algorithmes performants d'application de grammaires locales, en prenant comme référence ceux des logiciels libres existants : l'analyseur syntaxique descendant d'Unitex et l'analyseur syntaxique à la Earley d'Outilex. Les grammaires locales sont un formalisme de représentation de la syntaxe des langues naturelles basé sur les automates finis. Les grammaires locales sont un modèle de construction de descriptions précises et à grande échelle de la syntaxe des langues naturelles par le biais de l'observation systématique et l'accumulation méthodique de données. L'adéquation des grammaires locales pour cette tâche a été testée à l'occasion de nombreux travaux. À cause de la nature ambiguë des langues naturelles et des propriétés des grammaires locales, les algorithmes classiques d'analyse syntaxique tels que LR, CYK et ne peuvent pas être utilisés dans le contexte de ce travail. Les analyseurs top-down et Earley sont des alternatives possibles ; cependant, ils ont des coûts asymptotiques exponentiels pour le cas des grammaires locales. Nous avons d'abord conçu un algorithme d'application de grammaires locales avec un coût polynomial dans le pire des cas. Ensuite, nous avons conçu des structures de donnés performantes pour la représentation d'ensembles d'éléments et de séquences. Elles ont permis d'améliorer la vitesse de notre algorithme dans le cas général. Nous avons mis en œuvre notre algorithme et ceux des systèmes Unitex et Outilex avec les mêmes outils afin de les tester dans les mêmes conditions. En outre, nous avons mis en œuvre différents versions de chaque algorithme en utilisant nos structures de données et algorithmes pour la représentation d'ensembles et ceux fournis par la Standard Template Library (STL) de GNU. Nous avons comparé les performances des différents algorithmes et de leurs variantes dans le cadre d'un projet industriel proposé par l'entreprise Telefónica I+D : augmenter la capacité de compréhension d'un agent conversationnel qui fournit des services en ligne, voire l'envoi de SMS à des téléphones portables ainsi que des jeux et d'autres contenus numériques. Les conversations avec l'agent sont en espagnol et passent par Windows Live Messenger. En dépit du domaine limité et de la simplicité des grammaires appliquées, les temps d'exécution de notre algorithme, couplé avec nos structures de données et algorithmes pour la représentation d'ensembles, ont été plus courts. Grâce au coût asymptotique amélioré, on peut s'attendre à des temps d'exécution significativement inférieurs par rapport aux algorithmes utilisés dans les systèmes Unitex et Outilex, pour le cas des grammaires complexes et à large couverture
Type de document :
Thèse
Other [cs.OH]. Université Paris-Est, 2011. English. <NNT : 2011PEST1047>
Liste complète des métadonnées

https://pastel.archives-ouvertes.fr/tel-00621249
Contributeur : Abes Star <>
Soumis le : mercredi 8 février 2012 - 12:22:12
Dernière modification le : jeudi 22 juin 2017 - 14:13:49
Document(s) archivé(s) le : mercredi 9 mai 2012 - 02:35:51

Fichier

TH2011PEST1047_complete.pdf
Version validée par le jury (STAR)

Identifiants

  • HAL Id : tel-00621249, version 2

Citation

Javier Miguel Sastre Martinez. Efficient finite-state algorithms for the application of local grammars. Other [cs.OH]. Université Paris-Est, 2011. English. <NNT : 2011PEST1047>. <tel-00621249v2>

Partager

Métriques

Consultations de
la notice

576

Téléchargements du document

96