This is an implementation of the APTED algorithm, the state-of-the-art solution for computing the tree edit distance [1,2], which supersedes the RTED algorithm [3].

You can find more information on our Tree Edit Distance website http://tree-edit-distance.dbresearch.uni-salzburg.at/

As we've been pointed, our API had incorrect packaging causing some troubles (especially, the util package). We've fixed the packaging. For the sake of current users, we've left also the old one that we've annotated as deprecated in both, source code and javadoc. We're planning on removing it from the repository at some point.

If you want to refer to APTED in a publication, please cite [1] and [2].

The source code is published under the MIT licence found in the root directory of the project and in the header of each source file.

Currently, we support only the so-called bracket notation for the input trees, for example, encoding {A{B{X}{Y}{F}}{C}} corresponds to the following tree:

    A
   / \
  B   C
 /|\
X Y F

Our tool computes two outputs:

• tree edit distance value - the minimum cost of transforming the source tree into the destination tree.
• tree edit mapping - a mapping between nodes that corresponds to the tree edit distance value. Nodes that are not mapped are deleted (source tree) or inserted (destination tree).

If the nodes of your trees have labels different from simple strings and you need a more sophisticated cost model than unit cost, you can customise that. There are three elements that you have to consider. See Javadoc documentation for further details.

Our current parser BracketStringInputParser takes the bracket-encoded input tree as a string and transforms it to tree structure composed of Node objects. If you'd like to use other encoding, you have to write a custom class that implements InputParser interface.

The parser creates nodes and stores the corresponding information in Node.nodeData. We use StringNodeData to store simple string labels. If you need anything else, you have to implement your own class. It can be anything, we don't provide any interface.

The cost model decides on the costs of edit operations for every node (insertion and deletion) and every node pair (rename). We've implemented a simple StringUnitCostModel that returns 1 for deleting and inserting any node. The rename cost depends on label (StringNodeData) equality.

Write a class that implements CostModel interface if you need a more sophisticated cost model. See PerEditOperationStringNodeDataCostModel which allows different costs for each edit operation.

When you have all the bricks ready (MyInputParser, MyNodeData, MyCostModel), execute APTED as follows for sourceTree and destinationTree:

// Parse the input and transform to Node objects storing node information in MyNodeData.
MyInputParser parser = new MyInputParser();
Node<MyNodeData> t1 = parser.fromString(sourceTree);
Node<MyNodeData> t2 = parser.fromString(destinationTree);
// Initialise APTED.
APTED<MyCostModel, MyNodeData> apted = new APTED<>(new MyCostModel());
// Execute APTED.
float result = apted.computeEditDistance(t1, t2);

Execute java -jar apted.jar -h for manual and help.

You can clone the code, compile, and build the JAR file the regular command-line way.

We use Gradle for convenience.

• install Gradle
• run gradle test for unit tests (currently correctness tests)
• run gradle build to find the apted.jar file in build/libs/

We intentionally do not put automatically generated Gradle wrapper files in the repository. We don't like that. However, if it helps, we've added wrapper task section to build.gradle file.

Run gradle javadoc to generate documentation. Then, open in your browser build/docs/javadoc/index.html.

The current and future documentation should cover all classes and their members, including private. The internals of the algorithms and methods are documented within the source code. If anything is missing or unclear, please send us a feedback.

1. M. Pawlik and N. Augsten. Tree edit distance: Robust and memory- efficient. Information Systems 56. 2016.

2. M. Pawlik and N. Augsten. Efficient Computation of the Tree Edit Distance. ACM Transactions on Database Systems (TODS) 40(1). 2015.

3. M. Pawlik and N. Augsten. RTED: A Robust Algorithm for the Tree Edit Distance. PVLDB 5(4). 2011.