Hierarchical Bracketing Encodings for Dependency Parsing as Tagging

2025/05/16 by Ana Ezquerro, David Vilares, Ezquerro, Ana +5 · 1 citation
Computer Science · #Algorithms and Data Compression #Bracketing (phenomenology) #Computation and Language (cs.CL) #Dependency (UML) #ENCODE #Encoding (memory) #FOS: Computer and information sciences #Natural Language Processing Techniques #Parsing #Projective test #Sequence (biology) #Set (abstract data type) #semigroups and automata theory

paper · pdf · doi:10.48550/arxiv.2505.11693

published in arXiv (Cornell University) (Cornell University)

openalex publication_date 2025/05/16 · openalex created_date 2025/10/10 · openalex updated_date 2026/08/05

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.

Citations

• 4 and 7-bit Labeling for Projective and Non-Projective Dependency Trees
• Not All Linearizations Are Equally Data-Hungry in Sequence Labeling Parsing
• Bracketing Encodings for 2-Planar Dependency Parsing
• A Unifying Theory of Transition-based and Sequence Labeling Parsing
• Universal Dependencies v2: An Evergrowing Multilingual Treebank Collection
• Unsupervised Cross-lingual Representation Learning at Scale
• XLNet: Generalized Autoregressive Pretraining for Language Understanding
• Viable Dependency Parsing as Sequence Labeling
• Generic Axiomatization of Families of Noncrossing Graphs in Dependency Parsing
• Deep Biaffine Attention for Neural Dependency Parsing
• Empirical Evaluation of Rectified Activations in Convolutional Network

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