Efficient feature structure operations without compilation
Efficient feature structure operations without compilation
复制标题
无需编译即可高效进行特征结构运算
DOI：
10.1017/s1351324900002382
复制
发表时间：
2000
影响因子：
2.5
通讯作者：
Ann A. Copestake
中科院分区：
文献类型：
--
作者：
Robert Malouf;John Millar Carroll;Ann A. Copestake
在HPSG等基于统一的语法框架中，有效处理大范围覆盖的文法的一个主要障碍是统一操作本身的时间和空间成本。在语法开发系统中，使用涉及长时间编译的技术来解决此问题是不合适的，因为这会减慢编辑-测试-调试周期。从根本上重组语法也是不可能的。在本文中，我们描述了对现有高效统一算法的新扩展，该算法通过大幅增加发生的结构共享量来改善其空间和时间行为(而不影响其正确性)。我们还描述了一种快速且自动可调的统一前过滤器(快速检查)，它在实践中检测到如果执行将失败的很大比例的统一。最后，我们给出了一个有效的算法来检查两个特征结构之间的包含关系；这个算法的一个特例给出了一个快速的相等性检验。包含检查在解析器中使用(在本期的其他地方描述)，该解析器‘打包’局部歧义以避免执行冗余子计算。
One major obstacle to the efficient processing of large wide coverage grammars in unification-based grammatical frameworks such as HPSG is the time and space cost of the unification operation itself. In a grammar development system it is not appropriate to address this problem with techniques which involve lengthy compilation, since this slows down the edit-test-debug cycle. Nor is it possible to radically restructure the grammar. In this paper, we describe novel extensions to an existing efficient unification algorithm which improve its space and time behaviour (without affecting its correctness) by substantially increasing the amount of structure sharing that takes place. We also describe a fast and automatically tunable pre-unification filter (the ‘quick check’) which in practice detects a large proportion of unifications that if performed would fail. Finally, we present an efficient algorithm for checking for subsumption relationships between two feature structures; a special case of this gives a fast equality test. The subsumption check is used in a parser (described elsewhere in this issue) which ‘packs’ local ambiguities to avoid performing redundant sub-computations.