Awesome
APTED algorithm for the Tree Edit Distance
Information
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/
Deprecated API
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.
Citing APTED
If you want to refer to APTED in a publication, please cite [1] and [2].
Licence
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.
Input
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
Output
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).
Customising
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.
Parsing the input
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.
Node data
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.
Cost model
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.
Using customised APTED
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);
Execution manual
Execute java -jar apted.jar -h
for manual and help.
Building APTED
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 theapted.jar
file inbuild/libs/
Gradle wrapper
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.
Javadoc documentation
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.
References
-
M. Pawlik and N. Augsten. Tree edit distance: Robust and memory- efficient. Information Systems 56. 2016.
-
M. Pawlik and N. Augsten. Efficient Computation of the Tree Edit Distance. ACM Transactions on Database Systems (TODS) 40(1). 2015.
-
M. Pawlik and N. Augsten. RTED: A Robust Algorithm for the Tree Edit Distance. PVLDB 5(4). 2011.