[ Skip to the content ]

Institute of Formal and Applied Linguistics Wiki

[ Back to the navigation ]

Table of Contents

A Fast, Accurate, Non-Projective, Semantically-Enriched Parser

written by Stephen Tratz and Eduard Hovy (Information Sciences Institute, University of Southern Carolina)

presented by Martin Popel

reported by Michal Novák


The paper describes a high-quality conversion of Penn Treebank to dependency trees. The authors introduce an improved labeled dependency scheme based on the Stanford's one. In addition, they extend the non-directional easy-first first algorithm of Goldberg and Elhadad to support non-projective trees by adding “move” actions inspired by Nivre's swap-based reordering for shift-reduce parsing. Their parser is capable of producing shallow semantic annotations for prepositions, possesives and noun compounds.


Dependency conversion structure

Conversion process


MST parser <latex>\mathop O(n2)</latex>
MALT parser <latex>\mathop O(n)</latex> in fact slower
this parser <latex>\mathop O(n\log(n))</latex> <latex>\mathop O(n2)</latex> - naive implementation
this parser - non-projective <latex>\mathop O(n2\log(n))</latex> <latex>\mathop O(n3)</latex> - naive implementation




Shallow semantic annotation


[ Back to the navigation ] [ Back to the content ]