2D Trie for Fast Parsing

Proceedings of the 23rd International Conference on Computational Linguistics (Coling 2010), pages 904–912, Beijing, August 2010 2D Trie for Fast Parsing Xian Qian, Qi Zhang, Xuanjing Huang, Lide Wu Institute of Media Computing School of Computer Science, Fudan University {xianqian, qz, xjhuang, ldwu}@fudan.edu.cn Abstract In practical applications, decoding speed is very important. Modern structured learning technique adopts template based method to extract millions of features. Complicated templates bring about abun- dant features which lead to higher accu- racy but more feature extraction time. We propose Two Dimensional Trie (2D Trie), a novel efficient feature indexing structure which takes advantage of relationship be- tween templates: feature strings generated by a template are prefixes of the features from its extended templates. We apply our technique to Maximum Spanning Tree dependency parsing. Experimental results on Chinese Tree Bank corpus show that our 2D Trie is about 5 times faster than traditional Trie structure, making parsing speed 4.3 times faster. 1 Introduction In practical applications, decoding speed is very important. Modern structured learning technique adopts template based method to generate mil- lions of features. Such as shallow parsing (Sha and Pereira, 2003), named entity recognition (Kazama and Torisawa, ), dependency parsing (McDonald et al., 2005), etc. The problem arises when the number of tem- plates increases, more features generated, mak- ing the extraction step time consuming. Espe- cially for maximum spanning tree (MST) depen- dency parsing, since feature extraction requires quadratic time even using a first order model. Ac- cording to Bohnet’s report (Bohnet, 2009), a fast Feature�Generation Template: p .word+p .pos 0 0 Feature: lucky/ADJ Index: 3228~3233 Feature Retrieval Parse Tree Build�lattice,�inference�etc. Figure 1: Flow chart of dependency parsing. p0.word, p0.pos denotes the word and POS tag of parent node respectively. Indexes correspond to the features conjoined with dependency types, e.g., lucky/ADJ/OBJ, lucky/ADJ/NMOD, etc. feature extraction beside of a fast parsing algo- rithm is important for the parsing and training speed. He takes 3 measures for a 40X speedup, despite the same inference algorithm. One impor- tant measure is to store the feature vectors in file to skip feature extraction, otherwise it will be the bottleneck. Now we quickly review the feature extraction stage of structured learning. Typically, it consists of 2 steps. First, features represented by strings are generated using templates. Then a feature in- dexing structure searches feature indexes to get corresponding feature weights. Figure 1 shows the flow chart of MST parsing, where p0.word, p0.pos denote the word and POS tag of parent node respectively. We conduct a simple experiment to investi- gate decoding time of MSTParser, a state-of-the- art java implementation of dependency parsing 1. Chinese Tree Bank 6 (CTB6) corpus (Palmer and 1http://sourceforge.net/projects/mstparser 904 Step Feature Index Other Total Generation Retrieval Time 300.27 61.66 59.48 421.41 Table 1: Time spent of each step (seconds) of MSTParser on CTB6 standard test data (2660 sen- tences). Details of the hardware and corpus are described in section 5 Xue, 2009) with standard train/development/test split is used for evaluation. Experimental results are …

Content truncated to 500 words