Abstract
In this paper we present one of the algorithms used to parse probabilistic context-free grammars: the A* parsing algorithm, which is based on the A* graph search method. We show an example of application of the algorithm in an existing machine translation system. The existing CYK-based parser used in the Translatica system was modified by applying the A* parsing algorithm in order to examine the possibilities of improving its performance. This paper presents the results of applying the A* algorithm with different heuristic functions and their impact on the performance of the parser.References
Caraballo, S.A., Charniak, E.: New Figures of Merit for Best-First Probabilistic Chart Parsing. Computational Linguistics 24, pp. 275-298 (1998)
Charniak, E., Goldwater, S., Johnson, M.: Edge-Based Best-First Chart Parsing. In Proceedings of the Sixth Workshop on Very Large Corpora, pp. 127-133 (1998)
Klein, D., Manning, C.D.: A* Parsing: Fast Exact Viterbi Parse Selection. In Proceedings of the Human Language Technology Conference and the North American Association for Computational Linguistics (HLT-NAACL), pp. 119-126 (2003)
Manning, C.D., Sch¨utze, H.: Foundations of Statistical Natural Language Processing. Prentice Hall, New Jersey (2000)
Ratnaparkhi, A: Learning to Parse Natural Language with Maximum Entropy Models. Machine Learning 34, pp. 151-175 (1999)
Roark, B.: Probabilistic Top-Down Parsing and Language Modeling. Computational Linguistics 27, pp. 249-276 (2001)
Skórzewski, P.: Efektywny parsing je¸zyka naturalnego przy u˙zyciu gramatyk probabilistycznych (Efficient Natural Language Parsing Using Probabilistic Grammars). Master Thesis on Adam Mickiewicz University, Pozna´n (2010)
Skórzewski, P.: Effective Natural Language Parsing With Probabilistic Grammars). In Proceedings of Computational Linguistics – Applications, pp. 175-178. Wisła (2010)