X
- the node class for the left input.Y
- the node class for the right input.public class TreeEditFullAlgorithm<X,Y> extends AbstractTreeEditAlgorithm<X,Y,Alignment>
Constructor and Description |
---|
TreeEditFullAlgorithm(Comparator<Tree<X>,Tree<Y>> comparator) |
Modifier and Type | Method and Description |
---|---|
Alignment<Tree<X>,Tree<Y>> |
calculateAlignment(Tree<X> X,
Tree<Y> Y)
This calculates the tree edit distance D between the trees x ∈ T(X) and y ∈
T(Y) and returns it as an instance of the result class for this algorithm.
|
Class<Alignment> |
getResultClass()
This method shall return the class of the edit distance result.
|
static List<Operation<Integer,Integer>> |
treeEditAlignment(double[][] rep,
double[] del,
double[] ins,
int[] X_r,
int[] Y_r,
int[] X_kr,
int[] Y_kr)
Computes the Alignment between two trees which corresponds to the tree edit distance
given pairwise replacement costs between all nodes in both trees, the given deletion costs
for all nodes in the left tree, the insertion costs for all nodes in the right tree, the
outermost right descendant indices for both trees and the key root indices for both trees.
|
getComparator, min, min, requires, setComparator, worstCaseDistance, worstCaseDistance
public TreeEditFullAlgorithm(Comparator<Tree<X>,Tree<Y>> comparator)
public Alignment<Tree<X>,Tree<Y>> calculateAlignment(Tree<X> X, Tree<Y> Y)
TreeEditAlgorithm
X
- The left input tree (may be null if the tree is empty).Y
- The right input tree (may be null if the tree is empty).public static List<Operation<Integer,Integer>> treeEditAlignment(@NonNull double[][] rep, @NonNull double[] del, @NonNull double[] ins, @NonNull int[] X_r, @NonNull int[] Y_r, @NonNull int[] X_kr, @NonNull int[] Y_kr)
rep
- an m x n matrix of pairwise replacement costs, where rep[i][j] contains
d(xi, yj) where xi is the i-th node in X according to
the pre-order sequence and yj is the j-th node in Y according to the pre-order
sequence.del
- an m x 1 array of deletion costs for all nodes in X, where del[i] contains
d(xi, -) where xi is the i-th node in X according to
the pre-order sequence.ins
- an n x 1 array of insertion costs, where ins[j] contains
d(-, yj) where yj is the j-th node in Y according to the pre-order
sequence.X_r
- an m x 1 array of outermost right descendant indices, where X_r[i] is the
index of the outermost right descendant of node xi in X according to the pre-order
sequence.Y_r
- an n x 1 array of outermost right descendant indices, where Y_r[j] is the
index of the outermost right descendant of node yj in Y according to the pre-order
sequence.X_kr
- an m_l x 1 array of key-root indices for each leaf in X, sorted in
descending orderY_kr
- an m_r x 1 array of key-roots for each leaf in Y, sorted in
descending orderpublic Class<Alignment> getResultClass()
TreeEditAlgorithm
Copyright (C) 2016-2018 Benjamin Paaßen, AG Theoretical Computer Science, Centre of Excellence Cognitive Interaction Technology (CITEC), University of Bielefeld, licensed under the AGPL v. 3: http://openresearch.cit-ec.de/projects/tcs . This documentation is licensed under the conditions of CC-BY-SA 4.0: https://creativecommons.org/licenses/by-sa/4.0/