文章基本信息

标题：Dependency Parsing Schemata and Mildly Non-Projective Dependency Parsing
本地全文：下载
作者：Carlos Gómez-Rodríguez ; John Carroll ; David Weir 等
期刊名称：Computational Linguistics
印刷版ISSN：0891-2017
电子版ISSN：1530-9312
出版年度：2011
卷号：37
期号：3
页码：541-586
DOI：10.1162/COLI_a_00060
语种：English
出版社：MIT Press
摘要：We introduce dependency parsing schemata, a formal framework based on Sikkel's parsing schemata for constituency parsers, which can be used to describe, analyze, and compare dependency parsing algorithms. We use this framework to describe several well-known projective and non-projective dependency parsers, build correctness proofs, and establish formal relationships between them. We then use the framework to define new polynomial-time parsing algorithms for various mildly non-projective dependency formalisms, including well-nested structures with their gap degree bounded by a constant k in time O(n^5+2k) , and a new class that includes all gap degree k structures present in several natural language treebanks (which we call mildly ill-nested structures for gap degree k ) in time O(n^4+3k) . Finally, we illustrate how the parsing schema framework can be applied to Link Grammar, a dependency-related formalism.