Hostname: page-component-7c8c6479df-8mjnm Total loading time: 0 Render date: 2024-03-28T11:21:03.120Z Has data issue: false hasContentIssue false

Efficient feature structure operations without compilation

Published online by Cambridge University Press:  02 November 2000

ROBERT MALOUF
Affiliation:
Alfa Informatica, University of Groningen, Postbus 716, 9700 AS Groningen, The Netherlands; e-mail: malouf@let.rug.nl
JOHN CARROLL
Affiliation:
Cognitive and Computing Sciences, University of Sussex, Brighton BN1 9QH, UK; e-mail: johnca@cogs.susx.ac.uk
ANN COPESTAKE
Affiliation:
Center for the Study of Language and Information, Stanford University, Stanford, CA 94305, USA; e-mail: aac@csli.stanford.edu

Abstract

One major obstacle to the efficient processing of large wide coverage grammars in unification-based grammatical frameworks such as HPSG is the time and space cost of the unification operation itself. In a grammar development system it is not appropriate to address this problem with techniques which involve lengthy compilation, since this slows down the edit-test-debug cycle. Nor is it possible to radically restructure the grammar. In this paper, we describe novel extensions to an existing efficient unification algorithm which improve its space and time behaviour (without affecting its correctness) by substantially increasing the amount of structure sharing that takes place. We also describe a fast and automatically tunable pre-unification filter (the ‘quick check’) which in practice detects a large proportion of unifications that if performed would fail. Finally, we present an efficient algorithm for checking for subsumption relationships between two feature structures; a special case of this gives a fast equality test. The subsumption check is used in a parser (described elsewhere in this issue) which ‘packs’ local ambiguities to avoid performing redundant sub-computations.

Type
Research Article
Copyright
2000 Cambridge University Press

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)