Abstract
Graph unification is the most expensive part of unification-based grammar parsing. It often takes over 90% of the total parsing time of a sentence. We focus on two speed-up elements in the design of unification algorithms: 1) elimination of excessive copying by only copying successful unifications, 2) Finding unification failures as soon as possible. We have developed a scheme to attain these two criteria without expensive overhead through temporarily modifying graphs during unification to eliminate copying during unification. The temporary modification is invalidated in constant time and therefore, unification can continue looking for a failure without the overhead associated with copying. After a successful unification because the nodes are temporarily prepared for copying, a fast copying can be performed without overhead for handling reentrancy, loops and variables. We found that parsing relatively long sentences (requiring about 500 unifications during a parse) using our algorithm is 100 to 200 percent faster than parsing the same sentences using Wroblewski’s algorithm.- Anthology ID:
- 1991.iwpt-1.19
- Volume:
- Proceedings of the Second International Workshop on Parsing Technologies
- Month:
- February 13-25
- Year:
- 1991
- Address:
- Cancun, Mexico
- Editors:
- Masaru Tomita, Martin Kay, Robert Berwick, Eva Hajicova, Aravind Joshi, Ronald Kaplan, Makoto Nagao, Yorick Wilks
- Venue:
- IWPT
- SIG:
- SIGPARSE
- Publisher:
- Association for Computational Linguistics
- Note:
- Pages:
- 164–171
- Language:
- URL:
- https://aclanthology.org/1991.iwpt-1.19
- DOI:
- Cite (ACL):
- Hideto Tomabechi. 1991. Quasi-Destructive Graph Unification. In Proceedings of the Second International Workshop on Parsing Technologies, pages 164–171, Cancun, Mexico. Association for Computational Linguistics.
- Cite (Informal):
- Quasi-Destructive Graph Unification (Tomabechi, IWPT 1991)
- PDF:
- https://preview.aclanthology.org/nschneid-patch-4/1991.iwpt-1.19.pdf