2D Trie for Fast Parsing

Xian Qian, Qi Zhang, Xuanjing Huang, Lide WuCOLING 2010 · OpenReview

Abstract

Modern dependency parsing relies on complex feature templates, often making feature extraction the primary computational bottleneck. This paper proposes the 2D Trie, a specialized data structure that organizes feature templates into a hierarchical "Template Tree." By leveraging prefix sharing and virtual vertices, the 2D Trie enables aggressive pruning of the search space. Evaluation on the Chinese Tree Bank 6.0 demonstrates a 5x improvement in feature extraction speed and a 4.3x overall speedup in parsing, maintaining state-of-the-art accuracy.

Introduction: The Feature Extraction Bottleneck

In modern structured learning, particularly Maximum Spanning Tree (MST) dependency parsing, high accuracy is achieved through the use of sophisticated feature templates. These templates combine various attributes—such as words, POS tags, and relative distances—to generate millions of unique features.

The standard NLP pipeline where feature generation often becomes a bottleneck.

However, as templates grow in complexity, the time required for feature extraction increases dramatically. In standard implementations, feature extraction can take nearly five times longer than the actual inference process. Traditional indexing methods like Hash maps or standard Tries treat each feature as an independent entity, failing to exploit the fact that many features share common prefixes (e.g., a word is a prefix of the 'word + POS tag' feature).

Methodology: The 2D Trie Architecture

The core innovation presented is the 2D Trie, which implements "template-aware" indexing. This approach moves beyond simple string matching by organizing manually designed templates into a hierarchical structure.

The Template Tree and Virtual Vertexes

The authors organize templates into a tree where a parent template is a subset (prefix) of its children. To ensure efficient pruning, complex templates are decomposed into "virtual" steps. Each transition in the tree represents exactly one unit, such as a single word or tag.

Transformation of flat feature templates into a hierarchical Template Tree with virtual vertices.

Structural Implementation

Unlike a standard Trie that branches based on characters, the 2D Trie branches based on these template units. It functions as a matrix-like structure where rows represent template units and columns represent the "alphabet" (the vocabulary of words or POS tags). To manage memory efficiently, the authors utilize a Double Array Trie implementation, providing $O(1)$ lookup time while compressing the sparse matrix.

Experimental Evaluation

The approach was evaluated using the Chinese Tree Bank 6.0 (CTB6), with constituency structures converted to dependency trees via the Penn2Malt toolkit. The dataset was split into training (23,316 sentences), development (2,060), and testing (2,660) sets.

Results and Discussion

The 2D Trie significantly outperformed traditional indexing methods across several metrics:

  • Extraction Speed: Feature extraction was approximately 5x faster than a traditional Trie implementation.
  • Overall Parsing Speed: Total parsing time, including inference, improved by 4.3x. On the largest feature set, the 2D Trie processed 13.41 sentences per second, compared to 3.11 for the standard Trie.
  • Accuracy: These speed gains were achieved without any degradation in Labeled Attachment Score (LAS), which remained consistent at approximately 82.44%.
  • Pruning Efficiency: The primary driver of performance is the "fail-fast" mechanism. If a prefix template (e.g., a specific word) is not present in the model, the system immediately skips all descendant features, saving substantial computation.

Trade-offs

The 2D Trie is memory-intensive. For the largest models, it required 8.6 GB of RAM, nearly double the 4.9 GB required by a standard Trie. Additionally, the construction phase is more complex due to the large "alphabet" size, making it harder to find empty slots in the double array structure.

Conclusion

The 2D Trie offers a powerful solution for the feature extraction bottleneck in dependency parsing. By making the indexing structure "aware" of the underlying template grammar, it achieves significant speedups suitable for real-time applications. Future work may explore reducing the memory footprint and applying this structure to other NLP tasks such as Named Entity Recognition (NER).

Summary updated

BibTeX
@inproceedings{qian2010d,
  author = {Xian Qian and Qi Zhang and Xuanjing Huang and Lide Wu},
  title = {{2D Trie for Fast Parsing}},
  booktitle = {International Conference on Computational Linguistics},
  year = {2010},
  url = {https://openreview.net/forum?id=QJKk7cdcxb},
}
Figure