Graph Branch Algorithm : An Optimum Tree Search Method for Scored Dependency Graph with Arc Co-occurrence Constraints

この論文にアクセスする

この論文をさがす

著者

抄録

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.

収録刊行物

  • 自然言語処理 = Journal of natural language processing  

    自然言語処理 = Journal of natural language processing 13(4), 3-31, 2006-10-10 

    一般社団法人 言語処理学会

参考文献:  27件

参考文献を見るにはログインが必要です。ユーザIDをお持ちでない方は新規登録してください。

各種コード

  • NII論文ID(NAID)
    10018300462
  • NII書誌ID(NCID)
    AN10472659
  • 本文言語コード
    ENG
  • 資料種別
    ART
  • ISSN
    13407619
  • NDL 記事登録ID
    8548374
  • NDL 雑誌分類
    ZU8(書誌・図書館・一般年鑑--図書館・ドキュメンテーション・文書館)
  • NDL 請求記号
    Z21-B168
  • データ提供元
    CJP書誌  NDL  J-STAGE 
ページトップへ