Paper: Linear Complexity Context-Free Parsing Pipelines via Chart Constraints

ACL ID N09-1073
Title Linear Complexity Context-Free Parsing Pipelines via Chart Constraints
Venue Human Language Technologies
Session Main Conference
Year 2009
Authors

In this paper, we extend methods from Roark and Hollingshead (2008) for reducing the worst-case complexity of a context-free pars- ing pipeline via hard constraints derived from finite-state tagging pre-processing. Methods from our previous paper achieved quadratic worst-case complexity. We prove here that al- ternate methods for choosing constraints can achieve either linear orO(Nlog2N) complex- ity. These worst-case bounds on processing are demonstrated to be achieved without re- ducing the parsing accuracy, in fact in some cases improving the accuracy. The new meth- ods achieve observed performance compara- ble to the previously published quadratic com- plexity method. Finally, we demonstrate im- provedperformancebycombiningcomplexity bounding methods with additional high preci- sion co...