Journal of Computer Science

Packed Forest Chart Parser

Qi Haoliang, Li Sheng, Yang Muyun and Zhao Tiejun

DOI : 10.3844/jcssp.2007.9.13

Journal of Computer Science

Volume 3, Issue 1

Pages 9-13


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.


© 2007 Qi Haoliang, Li Sheng, Yang Muyun and Zhao Tiejun. This is an open access article distributed under the terms of the Creative Commons Attribution License, which permits unrestricted use, distribution, and reproduction in any medium, provided the original author and source are credited.