A Fundamental Algorithm for Dependency Parsing 论文

摘要

Abstract – This paper presents a fundamental algorithm for parsing natural language sentences into dependency trees. Unlike phrase-structure (constituency) parsers, this algorithm operates one word at a time, attaching each word as soon as it can be attached, corresponding to properties claimed for the parser in the human brain. Like phrasestructure parsing, its worst-case complexity is O(n 3), but in human language, the worst case occurs only for small n. 1 Overview. This paper develops, from first principles, several variations on a fundamental algorithm for parsing natural language into dependency trees. This is an exposition of an algorithm that has been known, in some form, since the 1960s but is not presented systematically in the extant literature. Unlike phrase-structure (constituency) parsers, this algorithm operates one word at a time, attaching each word as soon as it can be attached. There is good evidence that the parsing process used by the human mind has these properties [1]. 2 Dependency grammar. 2.1 The key concept. There are two ways to describe sentence structure in natural language: by breaking up the sentence into constituents (phrases), which are then broken into smaller constituents (Fig. 1), or by drawing links connecting