A Fast Algorithm for Computing Prefix Probabilities
Fuente:
arXiv
Saved in:
| Main Authors: | , |
|---|---|
| Format: | Preprint |
| Published: |
2023
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866912364891209728 |
|---|---|
| author | Nowak, Franz Cotterell, Ryan |
| author_facet | Nowak, Franz Cotterell, Ryan |
| contents | 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 |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(n^2 |N|^3+n^3|N|^2)$. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2306_02303 |
| institution | arXiv |
| publishDate | 2023 |
| record_format | arxiv |
| spellingShingle | A Fast Algorithm for Computing Prefix Probabilities Nowak, Franz Cotterell, Ryan Formal Languages and Automata Theory Data Structures and Algorithms 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 |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(n^2 |N|^3+n^3|N|^2)$. |
| title | A Fast Algorithm for Computing Prefix Probabilities |
| topic | Formal Languages and Automata Theory Data Structures and Algorithms |
| url | https://arxiv.org/abs/2306.02303 |