Please use this identifier to cite or link to this item: https://hdl.handle.net/10593/10874
Title: Wydajne algorytmy parsowania dla języków o szyku swobodnym
Other Titles: Efficient parsing algorithms for free word order languages
Authors: Skórzewski, Paweł
Advisor: Jassem, Krzysztof. Promotor
Keywords: parsowanie
parsing
algorytmy
algorithms
probabilistyczne gramatyki bezkontekstowe
probabilistic context-free grammars
języki o szyku swobodnym
free word order languages
optymalizacja
optimization
Issue Date: 30-May-2014
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.
Description: Wydział Matematyki i Informatyki
URI: http://hdl.handle.net/10593/10874
Appears in Collections:Doktoraty (WMiI)
Doktoraty 2010-2022 /dostęp otwarty/

Files in This Item:
File Description SizeFormat 
skorzewski301654dr.pdf1.47 MBAdobe PDFView/Open
Show full item record



Items in AMUR are protected by copyright, with all rights reserved, unless otherwise indicated.