| 摘要: |
| 句法分析的研究是自然语言处理领域的一个重要组成部分.该文提出并实现了一种有效的概率上下文无关文法SCFG（stochastic context-free grammar）的分析算法.首先对原有的GLR分析表加以改造，以便能够利用分析过程的控制结构来计算有关的概率；然后对分析过程中的每个状态增设了下标,以区分不同的归约路径.通过上述手段，成功地引入了状态的前向(Forward)概率和内(Inner)概率.利用这两个概率可以计算输入句子的所有可能分析树的概率，用于选择最佳的分析结果.通过对大规模真实文本进行实 |
| 关键词: SCFG(stochastic context-free grammar)，分析算法，GLR算法，Earley算法，自然语言处理. |
| DOI： |
| 分类号: |
| 基金项目:本文研究得到国家自然科学基金和航天预研基金资助. |
|
| An Efficient Stochastic Context-Free Parsing Algorithm |
|
ZHU Sheng-huo,ZHOU Ming,LIU Xin,HUANG Chang-ning
|
| Abstract: |
| 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. |
| Key words: Stochastic context-free grammar, parsing algorithm, GLR algorithm, Earley algorithm, natural language processing. |
