Span-based discontinuous constituency parsing: a family of exact chart-based algorithms with time complexities from O(nˆ6) down to O(nˆ3)
Caio Corro · 2020
We introduce a novel chart-based algorithm for span-based parsing of discontinuous constituency trees of block degree two, including ill-nested structures.In particular, we show that we can build variants of our parser with smaller search spaces and time complexities ranging from O(n 6 ) down to O(n 3 ).The cubic time variant covers 98% of constituents observed in linguistic treebanks while having the same complexity as continuous constituency parsers.We evaluate our approach on German and English treebanks (Negra, Tiger, and DPTB) and report state-of-the-art results in the fully supervised setting.We also experiment with pre-trained word embeddings and Bertbased neural networks.⇤ Work partially done while the author was a postdoc at University of Amsterdam with Ivan Titov. 1 The set of words that a node dominates is the set of leaf nodes in the subtree for which this node is the root.