Tech Report CS-98-04

Edge-Based Best-First Chart Parsing

Sharon Goldwater

May 1998


Natural language grammars are often very large and full of ambiguities, making standard computer parsers too slow to be practical for many tasks. Best-first parsing attempts to address this problem by preferentially working to expand subparses that are judged ``good'' by some probabilistic figure of merit. We explain the standard non-probabilistic and best-first chart parsing paradigms, then describe a new method of best-first parsing which improves upon previous work by ranking subparses at a more fine-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.

(complete text in pdf or gzipped postscript)