Treediff: Approximate Tree Matching for Ordered Trees

Dennis Shasha
Courant Institute of Mathematical Sciences
Department of Computer Science
New York University
shasha@cs.nyu.edu
http://cs.nyu.edu/cs/faculty/shasha/index.html

Jason Wang
Department of Computer Science
New Jersey Institute of Technology
jason@cis.njit.edu

Kaizhong Zhang
Department of Computer Science
University of Western Ontario
kzhang@csd.uwo.ca

Motivation

Approximate tree and subtree matching is important in many applications. We have worked out algorithms for these problems that are extremely efficient both practically and theoretically. The main algorithms used in the accompanying software are presented in the chapter of Zhang and Shasha in the book Pattern Matching in Strings, Trees, and Arrays edited by Alberto Apostolico and Zvi Galil. This web page describes the installation, use, and semantics of this software which you may use for research purposes.

If you have many trees or you are concerned about matching trees that are unordered (where the order among the children of a node does not matter), please see our software that allows a large database of trees to be searched fast (time proportional to the number of paths in the query tree, on the average).

If trees are not quite general enough, then we also have an efficient, heuristic package for graph comparison.

You can find our project home page here .

Installation

The approximate tree matcher runs in a high performance interpreted environment called K.

To begin with, therefore, please download trial K from kx.com . The license is good for a limited duration, but is renewable an unlimited number of times. K and our program run equally well on linux and windows. The tree matcher, our sample file, and all the K files fit comfortably in 0.5 megabytes of disk space.
Send email to shasha@cs.nyu.edu. If you care to describe your application, we'd be glad to hear about it. In any case, we will send you instructions for downloading two files:
- tree.k -- the software
- treein -- a sample database of trees
- You can then run the program by typing
  k tree
- Each row of the output will give you: a pair of trees and a distance which is the number of modifications to convert one tree to another.
```
treea | treec | 4
```
  means that the edit distance from treea to treec is 4.

Semantics of the Result and of the Input

The edit distance is defined as the minimum number of label modifications, node deletes, and node inserts required to transform one tree to another. A label modification is simply a change of the label and entails no modification to the structure. For example, the following two trees (represented in outline format) differ by a single label modification:

a
 b
   d 
   e
 c

and

a
 x
   d
   e
 c

A delete of a node N removes node N and makes the children (if any) of N become the children of the parent of N (if any). Deleting node x in the example above gives:

a
 d
 e
 c

An insertion is some possible inverse of a deletion, so for example, an insertion of y below k in the following tree

 k
   b
   c
   d
   e
   f
   c

may yield

or it may yield

or any other configuration in which y is the parent of a consecutive subsequence of the children of k of length zero or greater.

The trees this software handles are ordered: meaning that the order among siblings matters. Thus, the following

a
  b
  c

and

a
  c
  b

are two different trees. In fact the transformation from the first to the second entails one deletion and one insertion. If you are interested in unordered trees, then please contact Professor Jason Wang for software at jason@cis.njit.edu.

A tree-to-subtree match is an asymmetric distance calculation in which the question is "What is the smallest distance between T1 and some subtree of T2?" For example, a tree-to-subtree match from treec to treef yields a distance of 0, but that does not hold for a tree-to-subtree match from treef to treec.

Tree: treec
xray
  15
  z
    w
    v
    xray
      15
  q
  15
Tree: treef
newroot
  xray
    15
    z
      w
      v
      xray
        15
    q
    15
  newsibling1
  newsibling2
    nephew1
    nephew2

Input

As you can see by looking at treein, trees are described in two tables. The first one, having the schema
tree(treeid, parentid, childrenid)
describes the parent-child relationships using any self-consistent numbering of the nodes. Rows of the table are separated by a newline character. Here are the first few rows of that table:

#tree| treeid| parentid| childrenid
treea |0 |1 3 5 6 8
treea |3 |2 4
treea |6 |7
treeb |0 |1 2 5 6 8
treeb |2 |3 4
treeb |6 |7
treeb |7 |9
treec |0 |1 2 5 8
treec |2 |3 4 6

The table whose schema is
treelabel(treeid, nodeid, label)
gives the label associated with each node of the tree. Here are the first few rows of that table in treein:

# treelabel|treeid|nodeid|label
treea |0 |xray
treea |1 |15
treea |3 |z
treea |2 |w
treea |4 |v
treea |5 |q
treea |6 |xray
treea |7 |15
treea |8 |15
treeb |0 |xray
treeb |1 |15
treeb |2 |z
treeb |3 |w
treeb |4 |v
treeb |5 |q
treeb |6 |xray
treeb |7 |15

Labels can be characters, numbers, or strings and can be mixed. For example, treeb in the file treein has the format (see file treelayout after you run k tree ).

Tree: treeb
xray
  15
  z
    w
    v
  q
  xray
    15
      15
  15

Options

The program has a few command line options: k tree [+f filename] [+n num] [+s] [+b]

With no options, input comes from the file treein and is a full tree to full tree match of all pairs of trees in that file.
+f foobar -- specifies that input comes from the file foobar instead of treein .
+n 3 -- specifies that the first three trees in the two tables of the input file are to be compared with all the other trees in the input file. Thus the order of trees in that file is important.
+b -- specifies that best (least distance) matchings are the only ones of interest.
+s -- specifies that each comparison is a tree-to-subtree comparison where the subtree is the one that gives the least distance.

Support

This material is based upon work partly supported by the United States National Science Foundation under grant IIS-9988636 Any opinions, findings, and conclusions or recommendations expressed in this material are those of the authors and do not necessarily reflect the views of the National Science Foundation. This support is greatly appreciated.