Iterative CKY Parsing for Probabilistic Context-Free Grammars
Iterative CKY Parsing for Probabilistic Context-Free Grammars
复制标题
概率上下文无关文法的迭代 CKY 解析
DOI：
10.1007/978-3-540-30211-7_6
复制
发表时间：
2004
期刊：
影响因子：
--
通讯作者：
Junichi Tsujii
中科院分区：
文献类型：
--
作者：
Yoshimasa Tsuruoka;Junichi Tsujii
本文提出了一种概率上下文无关语法的迭代CKY解析算法。该算法使我们能够修剪解析过程中产生的不必要的边缘，从而提高解析效率。由于修剪是通过使用边缘的内部Viterbi概率和外部Viterbi概率的上界来完成的，因此该算法保证输出精确的Viterbi解析，而不像波束搜索或最佳优先策略。使用Penn Treebank II语料库的实验结果表明，迭代CKY算法比传统的CKY算法减少了60%以上的边缘，并且运行时开销很小。我们的算法足够通用，可以包含更复杂的估计函数，这将导致更有效的解析。
This paper presents an iterative CKY parsing algorithm for probabilistic context-free grammars (PCFG). This algorithm enables us to prune unnecessary edges produced during parsing, which results in more efficient parsing. Since pruning is done by using the edge’s inside Viterbi probability and the upper-bound of the outside Viterbi probability, this algorithm guarantees to output the exact Viterbi parse, unlike beam-search or best-first strategies. Experimental results using the Penn Treebank II corpus show that the iterative CKY achieved more than 60% reduction of edges compared with the conventional CKY algorithm and the run-time overhead is very small. Our algorithm is general enough to incorporate a more sophisticated estimation function, which should lead to more efficient parsing.
DOI：
--
发表时间：
2000
期刊：
--
影响因子：
--
作者：
Dan Jurafsky;James H. Martin
通讯作者：
Dan Jurafsky;James H. Martin