[ Skip to the content ]

Institute of Formal and Applied Linguistics

at Faculty of Mathematics and Physics, Charles University, Prague, Czech Republic


[ Back to the navigation ]

Publication


Year 2005
Type in proceedings
Status published
Language English
Author(s) McDonald, Ryan Pereira, Fernando Ribarov, Kiril Hajič, Jan
Title Non-Projective Dependency Parsing using Spanning Tree Algorithms
Czech title Neprojektivní závislostní syntaktická analýza s použitím algoritmů kostry
Proceedings 2005: Vancouver, BC, Canada: HLT-EMNLP 2005: Proceedings of Human Langauge Technology Conference and Conference on Empirical Methods in Natural Language Processing
Pages range 523-530
URL http://www.aclweb.org/anthology/H/H05/H05-1066.pdf
Supported by 2005-2009 LC536 (Centrum komputační lingvistiky) 2005-2009 1ET100300517 (Metody inteligentních systémů a jejich aplikace při dobývání znalostí a zpracování přirozeného jazyka)
Czech abstract Závislostní syntaktickou analýzu (parsing) formalizujeme jako hledání maximální kostry v orientovaném grafu. Při této reprezentaci lze použít Eisnerův (1996) algoritmus pro prohledání všech projektivních stromů v čase O(n3). Překvapivě lze tuto reprezentaci přirozeně rozšířit na neprojektivní analýzu pomocí algoritmu Chu-Liu-Edmonds (1965, 1967). Výsledný algoritmus má složitost O(n2).
English abstract We formalize weighted dependency parsing as searching for maximum spanning trees (MSTs) in directed graphs. Using this representation, the parsing algorithm of Eisner (1996) is sufficient for searching over all projective trees in O(n3) time. More surprisingly, the representation is extended naturally to non-projective parsing using Chu-Liu-Edmonds (1965, 1967) MST algorithm, yielding an O(n2) parsing algorithm.
Specialization linguistics ("jazykověda")
Confidentiality default – not confidential
Open access no
ISBN* 1-932432-55-8
Address* Vancouver, BC, Canada
Month* October
Venue* Westin Hotel
Institution* Association for Computational Linguistics
Creator: Common Account
Created: 9/14/09 9:35 PM
Modifier: Almighty Admin
Modified: 5/9/10 3:39 PM
***

From the ACL AnthologypublicH05-1066.pdfapplication/pdf
Content, Design & Functionality: ÚFAL, 2006–2016. Page generated: Sun Nov 18 03:57:42 CET 2018

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

100% OpenAIRE compliant