X
- the node class for the left input.Y
- the node class for the right input.public class TreeEditSoftAlgorithm<X,Y> extends AbstractTreeEditAlgorithm<X,Y,CooptimalMatrix>
Constructor and Description |
---|
TreeEditSoftAlgorithm(Comparator<Tree<X>,Tree<Y>> comparator) |
Modifier and Type | Method and Description |
---|---|
CooptimalMatrix<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<CooptimalMatrix> |
getResultClass()
This method shall return the class of the edit distance result.
|
static CooptimalMatrix<Integer,Integer> |
treeEditSoftMatrix(double[][] rep,
double[] del,
double[] ins,
int[] X_r,
int[] Y_r,
int[] X_kr,
int[] Y_kr,
boolean preventTrivialAlignments,
double crispness)
Computes the CooptimalMatrix for the given input trees in their index representation.
|
static double |
weight(double delta,
double crispness)
Computes exp(- β · δ).
|
getComparator, min, min, requires, setComparator, worstCaseDistance, worstCaseDistance
public TreeEditSoftAlgorithm(Comparator<Tree<X>,Tree<Y>> comparator)
public CooptimalMatrix<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 double weight(double delta, double crispness)
delta
- the difference between the optimal cost and the cost for this operation.crispness
- the crispness parameter β. If the crispness is zero, the output will
always be one. For high crispness, this approaches a Kronecker delta, that is, any delta
larger than zero will yield output zero, and only delta = 0 results in output 1.public static CooptimalMatrix<Integer,Integer> treeEditSoftMatrix(@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, boolean preventTrivialAlignments, double crispness)
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 orderpreventTrivialAlignments
- If this is set to true, alignments which delete the left
tree entirely and insert the right tree entirely will not be considered.crispness
- The crispness parameter β. A high value means that the result will be
almost indistinguishable from the TreeEditCooptimalAlgorithm. A value around 0 means that
all possible alignments between the input trees are weighed equally.public Class<CooptimalMatrix> 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/