The English grammar developed within the Alvey Natural Language Tools [Grover et al.1993] is a wide-coverage morphosyntactic and semantic analyzer, based on a formalism similar to that of Generalized Phrase Structure Grammar [Gazdar et al.1985]. John Carroll's Prolog port of the Alvey English grammar was used for this experimental evaluation.
![\includegraphics[width=\textwidth]{alvey.eps}](img620.png)
|
The indexing strategy used for Alvey has the same general structure as that presented in Section 4.3.1: when searching for a matching edge for a daughter in the chart, only chart entries with an index key matching that daughter's index key are visited. The Prolog implementation of Alvey has feature structures encoded as terms. Since there is no typing in Alvey, and since the feature structures are small7.4 (compared to MERGE), the index key associated with each daughter and each edge is the functor of the Prolog term encoding the category. Since the successful unifications of the functors do not guarantee the successful unifications of the terms, this is far from a ``perfect'' indexing. Indeed, the improvements in parsing times are less than those recorded for the MERGE grammar. However, the cost of maintaining an indexing scheme even as simple as positional indexing would overshadow the improvements in parsing times, due to the small category size (and consequently, the small unification costs). There are 780 rules in Alvey, compared to only 17 in MERGE, leading to an unmanageable number of hash entries for positional indexing.
The evaluation set consisted of all test sentences included in the Prolog port of Alvey (182 sentences of lengths from 2 to 31 words). Even if the indexing scheme is very simple, on average the indexed parser performs 4% better than the non-indexed EFD parser, with a maximum improvement of 10% (Figure 7.7).