Abstract
Multiple algorithms are known for efficiently calculating the prefix probability of a string under a probabilistic context-free grammar (PCFG). Good algorithms for the problem have a runtime cubic in the length of the input string. However, some proposed algorithms are suboptimal with respect to the size of the grammar. This paper proposes a new speed-up of Jelinek and Lafferty’s (1991) algorithm, which runs in O(n3|N|3 + |N|4), where n is the input length and |N| is the number of non-terminals in the grammar. In contrast, our speed-up runs in O(n2|N|3 + n3|N|2).- Anthology ID:
- 2023.acl-short.6
- Volume:
- Proceedings of the 61st Annual Meeting of the Association for Computational Linguistics (Volume 2: Short Papers)
- Month:
- July
- Year:
- 2023
- Address:
- Toronto, Canada
- Editors:
- Anna Rogers, Jordan Boyd-Graber, Naoaki Okazaki
- Venue:
- ACL
- SIG:
- Publisher:
- Association for Computational Linguistics
- Note:
- Pages:
- 57–69
- Language:
- URL:
- https://aclanthology.org/2023.acl-short.6
- DOI:
- 10.18653/v1/2023.acl-short.6
- Cite (ACL):
- Franz Nowak and Ryan Cotterell. 2023. A Fast Algorithm for Computing Prefix Probabilities. In Proceedings of the 61st Annual Meeting of the Association for Computational Linguistics (Volume 2: Short Papers), pages 57–69, Toronto, Canada. Association for Computational Linguistics.
- Cite (Informal):
- A Fast Algorithm for Computing Prefix Probabilities (Nowak & Cotterell, ACL 2023)
- PDF:
- https://preview.aclanthology.org/nschneid-patch-2/2023.acl-short.6.pdf