Repository files navigation

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

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

As we've been pointed, our API had incorrect packaging causing some troubles(especially, theutil package).We've fixed the packaging. For the sake of current users, we've left also theold 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 theMIT licence found in the rootdirectory 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 editdistance value - the minimum cost of transforming the sourcetree into the destination tree.
• tree editmapping - a mapping between nodes that corresponds to thetree 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 youneed a more sophisticated cost model than unit cost, you can customise that.There are three elements that you have to consider.SeeJavadoc documentation for further details.

Our current parserBracketStringInputParser takes the bracket-encoded inputtree as a string and transforms it to tree structure composed ofNode objects.If you'd like to use other encoding, you have to write a custom class thatimplementsInputParser interface.

The parser creates nodes and stores the corresponding information inNode.nodeData. We useStringNodeData to store simple string labels. Ifyou need anything else, you have to implement your own class. It can beanything, 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 asimpleStringUnitCostModel that returns1 for deleting and inserting anynode. The rename cost depends on label (StringNodeData) equality.

Write a class that implementsCostModel interface if you need a moresophisticated cost model. SeePerEditOperationStringNodeDataCostModel whichallows different costs for each edit operation.

When you have all the bricks ready (MyInputParser,MyNodeData,MyCostModel),execute APTED as follows forsourceTree anddestinationTree:

// Parse the input and transform to Node objects storing node information in MyNodeData.MyInputParserparser =newMyInputParser();Node<MyNodeData>t1 =parser.fromString(sourceTree);Node<MyNodeData>t2 =parser.fromString(destinationTree);// Initialise APTED.APTED<MyCostModel,MyNodeData>apted =newAPTED<>(newMyCostModel());// Execute APTED.floatresult =apted.computeEditDistance(t1,t2);

Executejava -jar apted.jar -h for manual and help.

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

We useGradle for convenience.

• install Gradle
• rungradle test for unit tests (currently correctness tests)
• rungradle build to find theapted.jar file inbuild/libs/

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

Rungradle javadoc to generate documentation. Then, open in your browserbuild/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 documentedwithin the source code. If anything is missing or unclear, please send usa 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 EditDistance. ACM Transactions on Database Systems (TODS) 40(1). 2015.

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