Efficient finite-state algorithms for the application of local grammars
Résumé
Our work focuses on developing efficient algorithms for applying local grammars, by referring to those of existing free software: the parser and the descendant of Unitex parser to Earley of Outilex. The local grammars are a formalism to represent the syntax of natural languages based on finite automata. The local grammars are a model of building accurate descriptions and scale of the syntax of natural languages through systematic observation and systematic accumulation of data. The adequacy of local grammars for this task has been tested at many jobs. Because of the ambiguous nature of natural language grammars and properties of local, classical algorithms for parsing such as LR, and Tomita CYK can not be used in the context of this work. Down and Earley parsers are alternatives, however, they have cost exponential asymptotics for the case of local grammars. We first developed an algorithm for applying local grammars with a polynomial cost in the worst case. Next, we designed efficient data structures for representing sets of elements and sequences. They have improved the speed of our algorithm in the general case. We have implemented our algorithm and those systems and Unitex Outilex with the same tools to test them under the same conditions. In addition, we have implemented various versions of each algorithm using our data structures and algorithms for the representation of sets and those provided by the Standard Template Library (STL) from GNU. We compared the performance of different algorithms and their variants as part of an industrial project proposed by Telefónica I + D: increase the capacity of understanding of a conversational agent that provides online services or the SMS to mobile phones as well as games and other digital content. Conversations with the agent are in Spanish and go through Windows Live Messenger. Despite the limited range and simplicity of grammars applied, the execution time of our algorithm, coupled with our data structures and algorithms for the representation of sets, have been shorter. With the improved asymptotic cost, we can expect run times significantly lower compared to the algorithms used in the systems and Outilex Unitex, in the case of complex grammars and large coverage.
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 Tomita ne peuvent pas être utilisés dans le contexte de ce travail. Les analyseurs descendant 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ées 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 oeuvre 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 oeuvre différentes 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.
Mots clés
Efficient
optimization
algorithm
parsing
natural language processing
Earley
local grammar
finite-state
machine
hierarchy
recursive transition network
RTN
filtered-popping network
FPN
filtered-popping recursive transition network
FPRTN
blackboard set processing
top-ranked blackboard
double-linked red-black tree
trie string management