Constructing parse forests that include exactly the n-best PCFG trees

Pierre Boullier, Alexis Nasr and Benoît Sagot

11th International Conference on Parsing Technology (IWPT 2009)
Paris, France, 7th-9th October, 2009

---

Summary

This paper describes and compares two algorithms that take as input a shared PCFG parse forest and produce shared forests that contain exactly the n most likely trees of the initial forest. Such forests are suitable for subsequent processing, such as (some types of) reranking or LFG f-structure computation, that can be performed ontop of a shared forest, but that may have a high (e.g., exponential) complexity w.r.t. the number of trees contained in the forest. We evaluate the performances of both algorithms on real-scale NLP forests generated with a PCFG extracted from the Penn Treebank.

---

START Conference Manager (V2.56.8 - Rev. 780)