Wydajne algorytmy parsowania dla języków o szyku swobodnym

Abstract

Niniejsza rozprawa stawia sobie za cel zbadanie pewnego problemu teoretycznego z zakresu gramatyk probabilistycznych oraz optymalizację związanego z nim problemu implementacyjnego. Część teoretyczna poświęcona jest zagadnieniom formalnego opisu języków o szyku swobodnym i algorytmom ich analizy składniowej. Rozważam w niej sposoby wykorzystywania gramatyk probabilistycznych do opisu języków swobodnego szyku. Definiuję autorski formalizm probabilistycznych gramatyk binarnych generujących drzewa (PTgBG), który stanowi probabilistyczne rozszerzenie formalizmu TgBG (gramatyk binarnych generujących drzewa). Prezentuję również parser wykorzystujący ten formalizm. Z drugiej strony celem niniejszej pracy jest zbadanie, w jaki sposób implementacja algorytmu parsowania wpływa na jego wydajność. W szczególności, przedstawiam proces adaptacji parsera do systemu przetwarzania języka naturalnego. Analizuję napotkane trudności i ewaluuję wydajność na poszczególnych etapach optymalizacji. Przedstawiam też wnioski płynące z tego procesu.

This thesis aims to investigate a theoretical problem in the field of probabilistic grammars and to optimize the associated implementation issue. The theoretical part is devoted to the issues of formal description of the free word order languages and their parsing algorithms. I consider methods of using probabilistic grammars to describe free order languages. I define the original formalism of probabilistic tree-generating binary grammars (PTgBG) that is a probabilistic extension of the TgBG formalism (tree-generating binary grammars). I present a parser that uses this formalism. On the other hand, the objective of this thesis is to examine how the implementation of the parsing algorithm affect its performance. In particular, I present the process of adapting the parser to the natural language processing system. I analyze any difficulties encountered and evaluate the performance of the system at various stages of optimization. Finally, I present the conclusions.