Research Article Open Access

Packed Forest Chart Parser

Qi Haoliang1, Li Sheng1, Yang Muyun1 and Zhao Tiejun1
  • 1 ,
Journal of Computer Science
Volume 3 No. 1, 2007, 9-13

DOI: https://doi.org/10.3844/jcssp.2007.9.13

Submitted On: 17 July 2006 Published On: 31 January 2007

How to Cite: Haoliang, Q., Sheng, L., Muyun, Y. & Tiejun, Z. (2007). Packed Forest Chart Parser. Journal of Computer Science, 3(1), 9-13. https://doi.org/10.3844/jcssp.2007.9.13

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.

  • 1,078 Views
  • 1,923 Downloads
  • 0 Citations

Download

Keywords

  • Parsing algorithm
  • packed forest chart parser
  • active edge