| This resource is not discoverable in the library. If the resource was recently submitted, it may require some time before it becomes discoverable through this search service. | | Resource Title: | A generalized CYK algorithm for parsing stochastic CFG
|
|---|
| Description: | We present a bottom-up parsing algorithm for stochastic context-free grammars that is able (1) to deal with multiple interpretations of sentences containing compound words; (2) to extract N-most probable parses in O(n 3 ) and compute at the same time all possible parses of any portion of the input sequence with their probabilities; (3) to deal with #out of vocabulary# words. Explicitly extracting all the parse trees associated to a given input sentence depends on the complexity of the grammar, but even in the case where this number is exponential in n, the chart used by the algorithm for the representation is of O(n 2 ) space complexity. 1 Introduction This article presents CYK+, a bottom-up parsing algorithm for stochastic context-free grammars that is able: 1. to deal multiple interpretations of sentences containing compound words; 2. to extract N-most probable parses in O(n 3 ) and compute at the same time all possible parses of any portion of the input sequence with their p... |
|---|
|
