TTP: A Fast and Robust Parser for Natural Language

TTP: A FAST AND ROBUST PARSER FOR NATURAL LANGUAGE TOMEK STRZALKOWSKI Courant Institute of Mathematical Sciences New York University 715 Broadway, rm 704 New York, NY 10003 tomek@cs.nyu.edu ABSTRACT In this paper we describe TI~, a fast and robust natural language parser which can analyze written text and generate regularized parse structures for sentences and phrases at the speed of approximately 0.5 sec/sentence, or 44 word per second. The parser is based on a wide coverage grammar for English, developed by the New York University's Linguistic String Project, and it uses the machine-readable ver- sion of the Oxford Advanced lw~arner's Dictionary as a source of its basic vocabulary. The parser operates on stochastically tagged text, and contains a powerful skip-and-fit recovery mechanism that allows it to deal with extra-grammatical input and to operate effec- tively under a severe time pressure. Empirical experi- ments, testing parser's speed and accuracy, were per- formed on several collections: a collection of technical abstracts (CACM-3204), a corpus of news messages (MUC-3), a selection from ACM Computer Library database, and a collection of Wall Street Journal arti- cles, approximately 50 million words in total. 1. INTRODUCTION Recently, there has been a growing demand for fast and reliable natural language processing tools, capable of performing reasonably accurate syntactic analysis of large volumes of text within an acceptable time. A full sentential parser that produces complete mmlysis of input, may be considered reasonably fast if the average parsing time per sentence falls anywhere between 2 and 10 seconds. A large volume of text, 7 perhaps a gigabyte or more, would contain as many as million sentences. At the speed of say, 6 sec/sentence, this much text would require well over a year to parse. While 7 million sentences is a lot of text, this much may easily he contained in a fair-sized text database. Therefore, the parsing speed would have to be increased by at least a factor of 10 to make such a task manageable. In this paper we describe a fast and robust natural language parser that can analyze written text and generate regularized parse structures at a speed of below 1 second per sentence. In the experiments con- ducted on variety of natural langauge texts, including technical prose, news messages, and newspaper arti- cles, the average parsing time varied between 0.4 sec/sentence and 0.7 see/sentence, or between 1600 and 2600 words per minute, as we tried to find an acceptable compromise between parser's speed and precision.l It has long been assumed that in order to gain speed, one may have to trade in some of the purser's accuracy. For example, we may have to settle for par- tial parsing that would recognize only selected gram- matical structures (e.g. noun phrases; Ruge et al., 1991), or would avoid making difficult decisions (e.g. pp-attachment; Hindle, 1983). Much of the overhead and inefficiency comes from the fact that the lexical and structural ambiguity of natmal language input can only be dealt with using limited context information available to …

Content truncated to 500 words