Unification-Failure Filter for Natural Language

Alfredo M. MAEDA  Hideto TOMABECHI  Jun-ichi AOE  

IEICE TRANSACTIONS on Information and Systems   Vol.E78-D   No.1   pp.19-26
Publication Date: 1995/01/25
Online ISSN: 
Print ISSN: 0916-8532
Type of Manuscript: PAPER
Category: Software Systems
software systems,  software theory,  speech processing,  artificial intelligence and cognitive science,  algorithm and computational complexity,  computer applications,  natural language processing and understanding,  unification,  

Full Text: PDF>>
Buy this Article

Graph unification is doubtlessly the most expensive process in unification-based grammar parsing since it takes the vast majority of the total parsing time of natural language sentences. A parsing time overload in unification consists in that, in general, no less than 60% of the graph unifications performed actually fail. Thus one way to achieve unification time speed-up is focusing on an efficient, fast way to deal with such unification failures. In this paper, a process, prior to unification itself, capable of filtering or stopping a considerably high percentage of graphs that would fail unification is proposed. This unification-filtering process consists of comparison of signatures that correspond to each one of the graphs to be unified. Unification-filter (hereafter UF) is capable of stopping around 87% of the non-unifiable graphs before unification itself takes place. UF takes significantly less time to detect graphs that do not unify and discard them than it would take to unification to fail the attempt to unify the same graphs. As a result of using UF, unification is performed in an around 71% of the time for the fastest known unification algorithm.