CStoRM implements an extension of the CYK algorithm for
parsing a string by a stochastic context free grammar to allow parsing of
general hidden Markov models. More precisely, given an HMM M and an SCFG G
cstorm computes maxπ ∈ M, D ∈ G{ ∑s P(s | &pi, M)P(s | D, G)}, i.e. the maximum
over all strings of the probability that M and
G independently generate that string. The
program allows grouping of structurally equivalent grammar productions, or
equivalently covarying state emissions, as e.g. covariance models. It
is available as C source code in a
tar archive.
Preliminary work on the algorithm was presented at WABI 2001. Overheads from a more recent presentation of the work are also available.