Graph Branch Algorithm: An Optimum Tree Search Method for Scored Dependency Graph with Arc Co-Occurrence Constraints
Graph Branch Algorithm: An Optimum Tree Search Method for Scored Dependency Graph with Arc Co-Occurrence Constraints
复制标题
图分支算法：一种带弧共现约束的评分依存图的最优树搜索方法
DOI：
10.5715/jnlp.13.4_3
复制
发表时间：
2006
影响因子：
--
通讯作者：
H. Hirakawa
中科院分区：
文献类型：
--
作者：
H. Hirakawa
偏好依存语法(PDG)是一种形态学框架，自然语言句子的句法和语义分析。PDG给出了打包的共享数据结构，用于包含句子分析的各个层次中的各种歧义和偏好分数，以及一种计算句子最合理解释的方法。本文提出了从已评分的依存森林计算最优依存树(句子的最可信解释)的图分支算法。图分支算法是包含句子的所有可能的依存树(解释)的打包共享数据结构。图分支算法采用分支和界限原则来管理任意弧形共现约束，包括单价占用约束，这是PDG中的一个基本语义约束本文还报告了用英文文本进行的实验，展示了图分支算法的计算复杂性和行为。
Preference Dependency Grammar (PDG) is a framework for the morphological, syntactic and semantic analysis of natural language sentences.PDG gives packed shared data structures for encompassing the various ambiguities in each levels of sentence analysis with preference scores and a method for calculating the most plausible interpretation of a sentence.This paper proposes the Graph Branch Algorithm for computing the optimum dependency tree (the most plausible interpretation of a sentence) from a scored dependency forest which is a packed shared data structure encompassing all possible dependency trees (interpretations) of a sentence.The graph branch algorithm adopts the branch and bound principle for managing arbitrary arc co-occurrence constraints including the single valence occupation constraint which is a basic semantic constraint in PDG.This paper also reports the experiment using English texts showing the computational complexity and behavior of the graph branch algorithm.