一种有效的概率上下文无关文法分析算法  

An Efficient Stochastic Context Free Parsing Algorithm

作　　者：朱胜火[1] 周明[1] 刘昕 黄昌宁[1] 

机构地区：[1]清华大学计算机科学与技术系智能技术与系统国家重点实验室

出　　处：《软件学报》1998年第8期592-597,共6页Journal of Software

基　　金：国家自然科学基金;航天预研基金

摘　　要：句法分析的研究是自然语言处理领域的一个重要组成部分．该文提出并实现了一种有效的概率上下文无关文法ＳＣＦＧ（ｓｔｏｃｈａｓｔｉｃｃｏｎｔｅｘｔ－ｆｒｅｅｇｒａｍｍａｒ）的分析算法．首先对原有的ＧＬＲ分析表加以改造，以便能够利用分析过程的控制结构来计算有关的概率；然后对分析过程中的每个状态增设了下标，以区分不同的归约路径．通过上述手段，成功地引入了状态的前向（Ｆｏｒｗａｒｄ）概率和内（Ｉｎｎｅｒ）概率．利用这两个概率可以计算输入句子的所有可能分析树的概率，用于选择最佳的分析结果．通过对大规模真实文本进行实验，结果表明，这种算法具有较高的分析效率．The research of parsing is important in the field of natural language processing. An efficient stochastic context free parsing algorithm is described in this paper. In order to implement a stochastic context free parser, the authors rebuild a GLR algorithm like parsing table so that derivation probabilities can be computed efficiently by making use of the parsing control structure, and add indices to each state in parsing period as identifiers of different parsing paths. Based on the techniques above, the forward and inner probabilities of states are introduced in this paper. With these two probabilities, the probabilities of all parsing trees of the input sentence can be computed to select an optimal parsing result. The experiment shows that the proposed algorithm is efficient.

关 键 词：SCFG 分析算法 自然语言处理 句法分析 

分 类 号：TP391[自动化与计算机技术—计算机应用技术]