X
- the node class for the left input.Y
- the node class for the right input.public class TreeEditScoreAlgorithm<X,Y> extends AbstractTreeEditAlgorithm<X,Y,Double>
Constructor and Description |
---|
TreeEditScoreAlgorithm(Comparator<Tree<X>,Tree<Y>> comparator) |
Modifier and Type | Method and Description |
---|---|
Double |
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<Double> |
getResultClass()
This method shall return the class of the edit distance result.
|
static double |
treeEditDistance(double[][] rep,
double[] del,
double[] ins,
int[] X_r,
int[] Y_r,
int[] X_kr,
int[] Y_kr)
Computes the tree edit distance for the 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 TreeEditScoreAlgorithm(Comparator<Tree<X>,Tree<Y>> comparator)
public Double 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 double treeEditDistance(@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<Double> 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/