Edge-Based Best-First Chart Parsing

Abstract

Natural language grammars are often very large and full of ambiguities, making standard computer parsers too slow to be practical for many tasks. Best-rst parsing attempts to address this problem by preferentially working to expand subparses that are judged \\good" by some probabilistic gure of merit. We explain the standard nonprobabilistic and best-rst chart parsing paradigms, then describe a new method of best-rst parsing which improves upon previous work by ranking subparses at a more ne-grained level, speeding up parsing by approximately a factor of 20 over the best previous results. Moreover, these results are achieved with a higher level of accuracy than is obtained by parsing to exhaustion. 1 Introduction Natural language processing is a subeld of articial intelligence which deals with trying to get computers to handle human language in a useful way. Having computers which could understand human language would simplify human-computer interaction and allow comp...