For Full-Text PDF, please login, if you are a member of IEICE,|
or go to Pay Per View on menu list, if you are a nonmember of IEICE.
Unification-Failure Filter for Natural Language
Alfredo M. MAEDA Hideto TOMABECHI Jun-ichi AOE
IEICE TRANSACTIONS on Information and Systems
Publication Date: 1995/01/25
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>>
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.