Research Article Open Access

Packed Forest Chart Parser

Qi Haoliang, Li Sheng, Yang Muyun and Zhao Tiejun

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.

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

  • 3,133 Views
  • 2,955 Downloads
  • 0 Citations

Download

Keywords

  • Parsing algorithm
  • packed forest chart parser
  • active edge