A Fast Algorithm for Computing Prefix Probabilities

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 novel speed-up of Jelinek and Lafferty’s (1991) algorithm, whose original runtime is $O(n^3\mathrm{\mid }N{\mathrm{\mid }}^3+\mathrm{\mid }N{\mathrm{\mid }}^4)$, where $n$ is the input length and $\mathrm{\mid }N\mathrm{\mid }$ is the number of non-terminals in the grammar. In contrast, our speed-up runs in $O(n^2\mathrm{\mid }N{\mathrm{\mid }}^3+n^3\mathrm{\mid }N{\mathrm{\mid }}^2)$.