K-Best A* Parsing
K-Best A* Parsing
复制标题
K-Best A* 解析
DOI：
--
复制
发表时间：
2009
期刊：
影响因子：
--
通讯作者：
D. Klein
中科院分区：
文献类型：
--
作者：
Adam Pauls;D. Klein
A*分析通过抑制不太可能的1-Best项来提高1-Best搜索的效率。现有的k-Best提取方法可以有效地搜索顶级派生，但只能在穷举1-Best通过之后才能找到。我们提出了一种统一的k-Best A*句法分析算法，该算法在保持K-Best抽取效率的同时，给出了A*方法的加速。我们的算法在相同的条件下产生了最优的k-Best语法分析，这与1-Best A*语法分析器中的最优条件相同。根据经验，在一系列语法类型上，提取最佳k-Best列表的速度比使用其他方法快得多。
A* parsing makes 1-best search efficient by suppressing unlikely 1-best items. Existing k-best extraction methods can efficiently search for top derivations, but only after an exhaustive 1-best pass. We present a unified algorithm for k-best A* parsing which preserves the efficiency of k-best extraction while giving the speed-ups of A* methods. Our algorithm produces optimal k-best parses under the same conditions required for optimality in a 1-best A* parser. Empirically, optimal k-best lists can be extracted significantly faster than with other approaches, over a range of grammar types.