An Expressive Model for Comparing Tree-Structured Data
Sudarshan S. Chawathe, Héctor García-Molina · 1997
this paper we present a novel method to represent changes and to compare trees that avoids these and other problems. The intuitive idea is to apply edit operations "in parallel" as opposed to in sequence. That is, we apply a set of edit operations, called a transformation, to a tree by first disassembling the given tree into "chunks," then operating on each chunk independently, and finally reassembling the resulting chunks to get the final tree. (In Section 2 we describe our model in detail.) Our model is free from the the unintuitive artifacts resulting from the interdependencies between edit operations in the linear edit script model. Even more importantly, searching for a minimum-cost parallel transformation is simpler that searching for a minimum-cost edit script (when moves and copies are allowed). This simplicity is because the essential information in a transformation, including its cost, can be compactly represented in a signature. Thus, we can search for a minimum-cost signature and then map it back to the corresponding transformation. In this paper we show how signatures are constructed, and how they map to transformations. The mapping between signatures and transformation is independent of the cost model used, making our methods for detecting changes useful in diverse application domains. The idea of working with signatures is widely used in the literature of differencing algorithms, in various forms (such as "traces" or matchings) [WF74, Mye86, ZS89, Yan91, CGM97]. However, the introduction of move and copy operations makes it hard to recover a script from a signature, and this makes it difficult to detect changes using signatures. To illustrate some of these difficulties, Figure 1(b) shows the "traditional" signature of the edit script in Figure 1(a). The t...