Packing of Feature Structures for Efficient Unification of Disjunctive Feature Structures

Packing of Feature Structures for Efficient Unification of Disjunctive Feature Structures Yusuke Miyao Department of Information Science, University of Tokyo 7-3-1 Hongo, Bunkyo-ku, Tokyo 113-0033 Japan E-mail: yusuke~is, s.u-tokyo, ac. jp Abstract This paper proposes a method for packing fea- ture structures, which automatically collapses equivalent parts of lexical/phrasal feature struc- tures of HPSG into a single packed feature struc- ture. This method avoids redundant repetition of unification of those parts. Preliminary exper- iments show that this method can significantly improve a unification speed in parsing. 1 Introduction Efficient treatment of syntactic/semantic ambi- guity is a key to making efficient parsers for wide-coverage grammars. In feature-structure- based grammars 1, such as HPSG (Pollard and Sag, 1994), ambiguity is expressed not only by manually-tailored disjunctive feature struc- tures, but also by enumerating non-disjunctive feature structures. In addition, there is ambigu- ity caused by non-determinism when applying lexical/grammar rules. As a result, a large num- ber of lexical/phrasal feature structures are re- quired to express ambiguous syntactic/semantic structures. Without efficient processing of these feature structures, a sufficient parsing speed is unattainable. This paper proposes a method for packing feature structures, which is an automatic op- timization method for parsers based on feature structure unification. This method automati- cally extracts equivalent parts of feature struc- tures and collapses them into a single packed feature structure. A packed feature structure can be processed more efficiently because we can avoid redundant repetition of unification of the equivalent parts of original feature structures. There have been many studies on efficient 1In this paper we consider typed feature structures described in (Carpenter, 1992). unification of disjunctive feature structures (Kasper and Rounds, 1986; Hasida, 1986; DSrre and Eisele, 1990; Nakano, 1991; Blache, 1997; Blache, 1998). All of them suppose that dis- junctive feature structures should be given by grammar writers or lexicographers. However, it is not practical to specify all ambiguity us- ing only manually-tailored disjunctive feature structures in grammar development. Where dis- junctive feature structures cannot be given ex- plicitly those algorithms lose their advantages. Hence, an automatic conversion method, such as the packing method described hereafter, is re- quired for further optimization of those systems. In addition, this packing method converts gen- eral feature structures to a suitable form for a simple and efficient unification algorithm which is also described in this paper. Griffith (Griffith, 1995; Griffith, 1996) points out the same problem and proposes a compila- tion method for feature structures called mod- ularization. However, modularization is very time-consuming, and is not suitable for opti- mizing feature structures produced during pars- ing. An earlier paper of myself (Miyao et al., 1998) also discusses the same problem and pro- poses another packing method. However, that method can pack only pre-specified parts of input feature structures, and this characteris- tic limits the overall efficient gain. The new method in this paper can pack any kind of fea- ture structures as far as possible, and is more general than the previous method. 2 Data Structure and Algorithms This …

Content truncated to 500 words