Abstract
This paper presents an efficient and optimal parsing algorithm for probabilistic context-free grammars (PCFGs). To achieve faster parsing, our proposal employs a pruning technique to reduce unnecessary edges in the search space. The key is to conduct repetitively Viterbi inside and outside parsing, while gradually expanding the search space to efficiently compute heuristic bounds used for pruning. Our experimental results using the English Penn Treebank corpus show that the proposed algorithm is faster than the standard CKY parsing algorithm. In addition, we also show how to extend this algorithm to extract k-best Viterbi parse trees.- Anthology ID:
- E17-2049
- Volume:
- Proceedings of the 15th Conference of the European Chapter of the Association for Computational Linguistics: Volume 2, Short Papers
- Month:
- April
- Year:
- 2017
- Address:
- Valencia, Spain
- Venue:
- EACL
- SIG:
- Publisher:
- Association for Computational Linguistics
- Note:
- Pages:
- 305–310
- Language:
- URL:
- https://aclanthology.org/E17-2049
- DOI:
- Cite (ACL):
- Katsuhiko Hayashi and Masaaki Nagata. 2017. K-best Iterative Viterbi Parsing. In Proceedings of the 15th Conference of the European Chapter of the Association for Computational Linguistics: Volume 2, Short Papers, pages 305–310, Valencia, Spain. Association for Computational Linguistics.
- Cite (Informal):
- K-best Iterative Viterbi Parsing (Hayashi & Nagata, EACL 2017)
- PDF:
- https://preview.aclanthology.org/starsem-semeval-split/E17-2049.pdf