Efficient Implementation of Beam-Search Incremental Parsers

Yoav Goldberg, Kai Zhao and Liang Huang

The 51st Annual Meeting of the Association for Computational Linguistics - Short Papers (ACL Short Papers 2013)
Sofia, Bulgaria, August 4-9, 2013

---

Abstract

Beam search incremental parsers are accurate, but not as fast as they could be. We demonstrate that, contrary to popular belief, most current implementations of beam parsers in fact run in O(n^2) time, rather than linear time, because each state-transition is actually implemented as an O(n) operation. We present an improved implementation, based on Tree Structured Stack, in which a transition is performed in O(1), resulting in a real linear-time algorithm, which is verified empirically. We further improve parsing speed by sharing feature-extraction and dot-product across beam items. Practically, our methods combined offer a speedup of ∼2x in parsing over strong baselines.

---

START Conference Manager (V2.61.0 - Rev. 2792M)