基于双向策略标记上下文无关文法的图算法

BSCFG-Based Bi-directional Parsing

一、引言句法分析是自然语言处理的重要基础,相应的研究很多,但是由于速度问题,句法分析很难大规模运用,因此提高分析速度一直是句法分析的重要研究方向。我们知道,句法分析的过程实际上是一个在句法成分树的空间中寻找最优分析树的过程,因此可以把分析过程看成是个搜索最佳路径的过程。在搜索的过程中给些“启发”将提高效率。双向图算法,是个最佳的例证,由于每条规则都有触发类来规定它的使用时机,使得它无论是时间还是空间上都比传统的图算法有更高的效率。

Bi-directional strategy-marked context free grammar (BSCFG) is a more flexible grammar,but it is not always complete. This paper proposes an algorithm to make any incomplete BSCFG complete, and proves its correctness. Then we develop a BSCFG-based bi-directional chart parser. Experiment indicates a promotion of 23.4% at speed.