Hierarchical Bracketing Encodings for Dependency Parsing as Tagging

2025/05/16 by Ezquerro, Ana, Vilares, David, Yli-Jyrä, Anssi +1 · 1 citation
#Computation and Language (cs.CL) #FOS: Computer and information sciences

paper · doi:10.48550/arxiv.2505.11693

Abstract

We present a family of encodings for sequence labeling dependency parsing, based on the concept of hierarchical bracketing. We prove that the existing 4-bit projective encoding belongs to this family, but it is suboptimal in the number of labels used to encode a tree. We derive an optimal hierarchical bracketing, which minimizes the number of symbols used and encodes projective trees using only 12 distinct labels (vs. 16 for the 4-bit encoding). We also extend optimal hierarchical bracketing to support arbitrary non-projectivity in a more compact way than previous encodings. Our new encodings yield competitive accuracy on a diverse set of treebanks.

Cited by

• Hierarchical Bracketing Encodings Work for Dependency Graphs

Related

• 4 and 7-bit Labeling for Projective and Non-Projective Dependency Trees
• Hierarchical Bracketing Encodings Work for Dependency Graphs
• Bracketing Encodings for 2-Planar Dependency Parsing
• Viable Dependency Parsing as Sequence Labeling
• Hexatagging: Projective Dependency Parsing as Tagging