Paper: Multilevel Coarse-To-Fine PCFG Parsing

ACL ID N06-1022
Title Multilevel Coarse-To-Fine PCFG Parsing
Venue Human Language Technologies
Session Main Conference
Year 2006

We present a PCFG parsing algorithm that uses a multilevel coarse-to-fine (mlctf) scheme to improve the effi- ciency of search for the best parse. Our approach requires the user to spec- ify a sequence of nested partitions or equivalence classes of the PCFG non- terminals. We define a sequence of PCFGs corresponding to each parti- tion, where the nonterminals of each PCFG are clusters of nonterminals of the original source PCFG. We use the results of parsing at a coarser level (i.e. , grammar defined in terms of a coarser partition) to prune the next finer level. We present experiments showing that with our algorithm the work load (as measured by the total number of constituents processed) is decreased by a factor of ten with no de- crease in parsing accuracy compared to standard CKY parsi...