CYK algorithm: Difference between revisions

Revision as of 06:17, 26 June 2006

Revision as of 06:18, 26 June 2006

Line 57:

It is also possible to extend the CYK algorithm to parse strings using [[weighted context-free grammar|weighted]] and [[stochastic context-free grammar]]s. Weights (probabilities) are then stored in the table P instead of booleans, so P[i,j,A] will contain the minimum weight (maximum probability) that the substring from i to j can be derived from A. Further extensions of the algorithm allow all parses of a string to be enumerated from lowest to highest weight (highest to lowest probability).

The CKY algorithm can be generalized from [[context-free grammarsgrammar]] to [[Hypergraphshypergraph]].

==References==