2023.acl-short.6@ACL

Total: 1

#1 A Fast Algorithm for Computing Prefix Probabilities [PDF4] [Copy] [Kimi8] [REL]

Authors: Franz Nowak, Ryan Cotterell

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).

Subject: ACL.2023 - Short Papers