Computer Science – Computation and Language
Scientific paper
1994-11-28
Computer Science
Computation and Language
45 pages. Slightly shortened version to appear in Computational Linguistics 21
Scientific paper
We describe an extension of Earley's parser for stochastic context-free grammars that computes the following quantities given a stochastic context-free grammar and an input string: a) probabilities of successive prefixes being generated by the grammar; b) probabilities of substrings being generated by the nonterminals, including the entire string being generated by the grammar; c) most likely (Viterbi) parse of the string; d) posterior expected number of applications of each grammar production, as required for reestimating rule probabilities. (a) and (b) are computed incrementally in a single left-to-right pass over the input. Our algorithm compares favorably to standard bottom-up parsing methods for SCFGs in that it works efficiently on sparse grammars by making use of Earley's top-down control structure. It can process any context-free rule format without conversion to some normal form, and combines computations for (a) through (d) in a single algorithm. Finally, the algorithm has simple extensions for processing partially bracketed inputs, and for finding partial parses and their likelihoods on ungrammatical inputs.
No associations
LandOfFree
An Efficient Probabilistic Context-Free Parsing Algorithm that Computes Prefix Probabilities does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with An Efficient Probabilistic Context-Free Parsing Algorithm that Computes Prefix Probabilities, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and An Efficient Probabilistic Context-Free Parsing Algorithm that Computes Prefix Probabilities will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-276421