Abstract
Graph unification is a central operation in many linguistic formalisms, yet its destructive nature often necessitates costly data copying to preserve original structures. This paper introduces Lazy Incremental Copying (LIC), a method that integrates structure sharing with generation-based tracking to eliminate redundant copying. By distinguishing between "active" nodes created in the current computation and "non-active" nodes from previous states, LIC allows for safe destructive updates and efficient backtracking. Implementation results on HPSG grammars show a significant performance improvement, reducing total processing time by 60-70%.
Introduction: The Copying Problem
In computational linguistics, unification is the process of merging feature structures—represented as Directed Graphs (DGs)—to verify compatibility between linguistic attributes. A significant bottleneck arises because standard unification is destructive. To maintain the integrity of original structures (e.g., lexical entries reused across multiple parses), systems must either copy the entire graph beforehand (Early Copying) or copy nodes as they are modified (Incremental Copying). While incremental copying is more efficient, it still produces many redundant nodes that have not actually changed. Alternatively, structure sharing avoids copying but introduces complex "environments" that can degrade unification speed.
The Lazy Incremental Copying (LIC) Method
Martin Emele’s Lazy Incremental Copying (LIC) provides a middle ground, combining the benefits of incremental copying with a simplified structure-sharing mechanism. The core of LIC relies on two components: Generation Counters and Chronological Dereferencing.
Data Structures
Every node in the graph, defined as a CopyNode, includes a generation integer that acts as a timestamp. This allows the system to track when a node was created relative to the current unification environment.
Merging Logic
The efficiency of LIC stems from how it handles node merging based on their "active" status. A node is considered "active" if its generation matches the current environment.
- Destructive Merge (Case 1): If both nodes are active, they were created for the current task. A fast, destructive merge is performed without further copying.
- Forwarding (Case 2): If one node is active and the other is non-active, the system points the non-active node toward the active one.
- Incremental Copying (Case 3): Only when both nodes are non-active is a new "active" node created to represent their union.
This "lazy" approach ensures that new nodes are only allocated when a destructive change is unavoidable to preserve data integrity.
Key Results and Insights
The LIC algorithm was evaluated using an HPSG grammar and a set of test sentences for parsing and generation. Compared to standard incremental copying algorithms (e.g., Wroblewski’s), LIC achieved a 60% to 70% reduction in total processing time.
Beyond raw speed, LIC offers several architectural advantages:
- Efficient Backtracking: Because updates are tied to generation counters, "undoing" a failed unification path is nearly instantaneous—simply reverting the current generation ID effectively invalidates "future" pointers.
- Path Sharing: LIC allows resulting graphs to point directly back into original structures for unchanged sub-paths, significantly reducing memory footprint.
- Constant-Time Context Switching: The environment-based dereferencing makes moving between different branches of a search space highly efficient.
Limitations
While highly effective, LIC introduces a slight overhead during dereferencing, as every node access requires a generation check. Additionally, the algorithm's performance remains dependent on the efficiency of the underlying memory manager for CopyNode allocation. Future work may explore specialized optimizations for specific linguistic applications.
Summary updated