Signature‐check based unification filter
Alfredo M. Maeda, Jun‐ichi Aoe, Hideto Tomabechi · Software Practice and Experience · 1994
Abstract Among the different processes that entail unification‐based grammar parsing, the unification of feature structures is by far the most expensive one in terms of execution time. Unification of the feature structures of a given sentence typically takes between 85 and 98 per cent of the total elapsed time during parsing, thus the need to develop faster unification methods. The approach presented in this paper is based on the fact that, in general, between 60 and 85 per cent of unifications attempted in a typical parse result in failure. Our claim is that the efficient treatment of such unification failures reduces unification time significantly. In this paper we present what we call a unification filter or U‐filter, that preprocesses the feature structures to be unified. If the U‐filter succeeds, unification is then skipped because the attempt to unify the involved structures would result in failure. On the other hand, when the U‐filter does not succeed it is not possible to determine at that moment whether or not the structures unify, so unification is performed. The U‐filter stops around 87 per cent of unification failures, and speeds up unification time by an average of around 29 per cent over quasi‐destructive graph unification, the fastest unification method known so far.