DEVICE, METHOD AND PROGRAM OF STOCHASTIC CONTEXT-FREE GRAMMAR INQUIRY

摘要

PPROBLEM TO BE SOLVED: To provide a technique for reducing a calculation cost while maintaining the accuracy of an inquiry result in a stochastic context-free grammar inquiry. PSOLUTION: In the stochastic context-free grammar inquiry, it is assumed that grammar G to be defined by an aggregate of terminal symbols, non-terminal symbols (nodes) and generation rules with probabilities is given. Firstly, a method of a stochastic context-free grammar inquiry rearranges the grammar G at random (Step S101). Next, the method puts together all the nodes to calculate an approximate probability P2 (step S105), puts together the nodes for each height to calculate an approximate probability P1 while pruning (pruned parts are excluded from the objects of the inquiry) the nodes for the grammar G (Step S107), compares the result with a probability of a solution candidate (Steps S106, S108), and performs accurate probability calculation after a reduction in the number of grammars and nodes to be used for calculation of an accurate probability P while pruning the nodes (Step S109). PCOPYRIGHT: (C)2010,JPO&INPIT