A Fundamental Algorithm for Dependency Parsing (With Corrections)
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 phrase-structure parsing, its worst-case complexity is $O(n^3)$, but in human language, the worst case occurs only for small $n$.
Code (0)
등록된 구현이 없습니다.
Tasks
Dependency ParsingSimilar Papers 제목 키워드 기반
Making Ellipses Explicit in Dependency Conversion for a German Treebank
We present a carefully designed dependency conversion of the German phrase-structure treebank TiGer that explicitly represents verb ellipses by introducing empty nodes into the tree. Although the conversion process uses …
A Graph-based Model for Joint Chinese Word Segmentation and Dependency Parsing
Chinese word segmentation and dependency parsing are two fundamental tasks for Chinese natural language processing. The dependency parsing is defined on word-level. Therefore word segmentation is the precondition of depe…
Chinese Word SegmentationDependency ParsingFeature EngineeringLanguage Modeling+2Dependency Parsing with the Structuralized Prompt Template
Dependency parsing is a fundamental task in natural language processing (NLP), aiming to identify syntactic dependencies and construct a syntactic tree for a given sentence. Traditional dependency parsing models typicall…
Dependency ParsingSentenceLock-Free Parallel Perceptron for Graph-based Dependency Parsing
Dependency parsing is an important NLP task. A popular approach for dependency parsing is structured perceptron. Still, graph-based dependency parsing has the time complexity of $O(n^3)$, and it suffers from slow trainin…
Dependency ParsingParsing to Noncrossing Dependency Graphs
We study the generalization of maximum spanning tree dependency parsing to maximum acyclic subgraphs. Because the underlying optimization problem is intractable even under an arc-factored model, we consider the restricti…
ARCDependency ParsingSemantic Dependency Parsing