An Efficient Chart-based Algorithm for Partial-Parsing of Unrestricted Texts

An Efficient Chart-based Algorithm for Partial-Parsing of Unrestricted Texts David D. McDonald 14 Brantwood Road, Arlington MA 02174-8004 USA MCDONALD @ BRANDEIS.EDU (617) 646-4124 Abstract In the rest of this section we will look at some of the We present an efficient algorithm for chart-based phrase structure parsing of natural language that is tai- lored to the problem of extracting specific information from unrestricted texts where many of the words are un- known and much of the text is irrelevant to the task. The parser gains algorithmic efficiency through a reduc- tion of its search space. As each new edge is added to the chart, the algorithm checks only the topmost of the edges adjacent to it, rather than all such edges as in con- ventional treatments. The resulting spanning edges are insured to be the correct ones by carefully controlling the order in which edges are introduced so that every final constituent covers the longest possible span. This is facilitated through the use of phrase boundary heuris- tics based on the placement of function words, and by heuristic rules that permit certain kinds of phrases to be deduced despite the presence of unknown words. A fur- ther reduction in the search space is achieved by using semantic rather than syntactic categories on the terminal and nonterminal edges, thereby reducing the amount of ambiguity and thus the number of edges, since only edges with a valid semantic interpretation are ever intro- daced. 1. Introduction Much of the research being done in parsing today is directed towards the problem of information extraction, sometimes referred to as "message processing" or "populating data-bases". The goal of this work is to develop systems that can robustly extract information from massive corpora of unrestricted ("open") texts. We have developed such a system and applied it to the task of extracting infor- mation about changes in employment found in articles from the "Who's News" column of the Wall Street Journal. We call the system "Sparser". There are many possible design goals for a parser. For Sparser we have three: • It must handle unrestricted texts, to be taken directly from online news services without human interven- tion or preprocessing. • It must operate efficiently and robustly, and be able to handle articles of arbitrary size using a fixed, rela- tively small set of resources. • Its purpose is the identification and extraction specifi- cally targeted, literal information in order to populate a database. Linguistically motivated structural descriptions of the text are a means to that end, not an end in themselves. consequences of these goals for the parser's design. The most important of these is how to cope with the fact that many of the words in the text will be unknown, which we will take up first. We then look at the consequences of designing the parser for the specific purpose of information extraction. In section two we will look at how well Sparser has been able to meet these goals after roughly fifteen months …

Content truncated to 500 words