A Bag of Useful Techniques for Efficient and Robust Parsing

A Bag of Useful Techniques for Efficient and Robust Parsing Bernd Kiefer t, Hans-Ulrich Kriegert, John Carroll $, and Rob Malouff IGerman Research Center for Artificial Intelligence (DFKI) Stuhlsatzenhausweg 3, D-66123 Saarbriicken $Cognitive and Computing Sciences, University of Sussex Falmer, Brighton BN1 9QH, UK *Center for the Study of Language and Information, Stanford University Ventura Hall, Stanford, CA 94305-4115, USA {kiefer, krieger}@dfki, de, j ohnca@cogs, susx. ac. uk, malouf@csli, stanford, edu Abstract This paper describes new and improved tech- niques which help a unification-based parser to process input efficiently and robustly. In com- bination these methods result in a speed-up in parsing time of more than an order of magni- tude. The methods are correct in the sense that none of them rule out legal rule applications. 1 Introduction This paper describes several generally- applicable techniques which help a unification- based parser to process input efficiently and robustly. As well as presenting a number of new methods, we also report significant improve- ments we have made to existing techniques. The methods preserve correctness in the sense they do not rule out legal rule applications. In particular, none of the techniques involve statistical or approximate processing. We also claim that these methods are independent of the concrete parser and neutral with re- spect to a given unification-based grammar theory/formalism. How can we gain reasonable efficiency in pars- ing when using large integrated grammars with several thousands of huge lexicon entries? Our belief is that there is no single method which achieves this goal alone. Instead, we have to develop and use a set of "cheap" filters which are correct in the above sense. As we indicate in section 10, combining these methods leads to a speed-up in parsing time (and reduction of space consumption) of more than an order of magnitude when applied to a mature, well en- gineered unification-based parsing system. We have implemented our methods as exten- sions to a HPSG grammar development environ- ment (Uszkoreit et al., 1994) which employs a sophisticated typed feature formalism (Krieger and Sch~ifer, 1994; Krieger and Sch~ifer, 1995) and an advanced agenda-based bottom-up chart parser (Kiefer and Scherf, 1996). A special- ized runtime version of this system is currently used in VERBMOBIL as the primary deep anal- ysis component. I In the next three sections, we report on trans- formations we have applied to the knowledge base (grammar/lexicon) and on modifications in the core formalism (unifier, type system). In Section 5-8, we describe how a given parser can be extended to filter out possible rule applica- tions efficiently before performing "expensive" unification. Section 9 shows how to compute best partial analyses in order to gain a certain level of robustness. Finally, we present empir- ical results to demonstrate the efficiency gains, and speculate on extensions we intend to work on in the near future. Within the different sec- tions, we refer to three corpora we have used to measure the effects of our methods. The refer- ence corpora for English, German, and Japanese …

Content truncated to 500 words