Packed Forest Chart Parser

Abstract

Packed forest chart parser, like the traditional chart parsing algorithm, uses charts to store all the information produced while parsing to avoid redundant works. Its advantage over the traditional chart parser was the packed forest representation. The algorithm not only shares the non-terminal categories as what was done in the shared parse forest, but also shares the leftmost common elements. The number of active edges in packed forest chart parser was decreased, so memory requirement was reduced and parsing was speeded up. The effectiveness of our approach has been evaluated on Chinese parsing. Results show that packed forest chart parser significantly outperforms packed chart parser, with the former 10 times faster than the latter.