Tech Report CS-98-04
Edge-Based Best-First Chart Parsing
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.