Parsing based on A Algorithm Agenda Control

概要

論文の詳細を見る
In this study we propose a method of syntactic analysis which approaches parsing as a search problem, controls the agenda of the chart parser following the strategy of A algorithm and generates only the required number of syntactic structures, from the most adequate in descending order of goodness. Given a set of costed rules of syntactic analysis in CFG form, at the pre-processing stage, for A to become admissible, every sub-structure which can be generated by these rules receives an estimate of the cost from the present state, corresponding to the sub-structure itself, to the goal state, corresponding to a complete structure of which this sub-structure is a constituent part. Then, at the stage of syntactic analysis proper, all competing structures are processed in the order from the lowest-costing, where cost is the sum of the estimate and the actual cost of generating the structure, and thus the lowestcosting structure is guaranteed to be obtainable. This method allocates appropriate cost values to each parsing rule. This makes it possible to prioritize syntactic structures in great detail and also to modify priorities, if necessary, simply by altering the cost values. Costed CFG rules can be seen as extending the descriptive power of Probabilistic CFG rules.
言語処理学会の論文