tailieunhanh - Báo cáo khoa học: "Memory-Efficient and Thread-Safe Quasi-Destructive Graph Unification"

In terms of both speed and memory consumption, graph unification remains the most expensive component of unification-based grammar parsing. We present a technique to reduce the memory usage of unification algorithms considerably, without increasing execution times. Also, the proposed algorithm is thread-safe, providing an efficient algorithm for parallel processing as well. | Memory-Efficient and Thread-Safe Quasi-Destructive Graph Unification Marcel P. van Lohuizen Department of Information Technology and Systems Delft University of Technology mpvl@ Abstract In terms of both speed and memory consumption graph unification remains the most expensive component of unification-based grammar parsing. We present a technique to reduce the memory usage of unification algorithms considerably without increasing execution times. Also the proposed algorithm is thread-safe providing an efficient algorithm for parallel processing as well. 1 Introduction Both in terms of speed and memory consumption graph unification remains the most expensive component in unification-based grammar parsing. Unification is a well known algorithm. Prolog for example makes extensive use of term unification. Graph unification is slightly different. Two different graph notations and an example unification are shown in Figure 1 and 2 respectively. In typical unification-based grammar parsers roughly 90 of the unifications fail. Any processing to create or copy the result graph before the point of failure is b A b C D e F Figure 1 Two ways to represent an identical graph. redundant. As copying is the most expensive part of unification a great deal of research has gone in eliminating superfluous copying. Examples of these approaches are given in Tomabechi 1991 and Wroblewski 1987 . In order to avoid superfluous copying these algorithms incorporate control data in the graphs. This has several drawbacks as we will discuss next. Memory Consumption To achieve the goal of eliminating superfluous copying the aforementioned algorithms include administrative fields which we will call scratch fields in the node structure. These fields do not attribute to the definition of the graph but are used to efficiently guide the unification and copying process. Before a graph is used in unification or after a result graph has been copied these fields just take up space. This is .