X
- The node class for the left input set.Y
- The node class for the right input set.R
- The result class for this AlignmentAlgorithm.public abstract class AbstractStrictSetAlignmentAlgorithm<X,Y,R> extends Object implements AlignmentAlgorithm<X,Y,R>
Constructor and Description |
---|
AbstractStrictSetAlignmentAlgorithm(Comparator<X,Y> comparator,
Class<R> resultClass) |
Modifier and Type | Method and Description |
---|---|
static int[] |
align(double[][] rep,
double[] del,
double[] ins)
Returns the optimal alignment of two sets in O((m+n)^3) where m and n are the sizes of both
sets.
|
R |
calculateAlignment(List<X> a,
List<Y> b)
This calculates the alignment dissimilarity D between the Sequences x ∈ X* and y ∈
Y* and returns it as an instance of the result class for this algorithm.
|
static double |
distance(double[][] rep,
double[] del,
double[] ins,
int[] assignment)
Returns the cost of an alignment of two sets.
|
Comparator<X,Y> |
getComparator()
This should return the Comparator used to compute local distances for this algorithm.
|
Class<R> |
getResultClass()
This method shall return the class of the alignment result.
|
static <X,Y> double |
normalizeDissimilarity(double d,
List<X> a,
List<Y> b)
Normalizes the given raw distance by the worst case that could occur in an alignment of the
two sequences: In the worst case, we replace all elements in a with elements in b and
delete/insert the remaining elements in the longer sequence.
|
boolean |
requires(OperationType type)
This method should return true if and only if this AlignmentAlgorithm uses the given
operation.
|
void |
setComparator(Comparator<X,Y> comparator)
This should set the Comparator used to compute local distances for this algorithm.
|
abstract R |
transformToResult(int[] assignment,
double[][] repCosts,
double[] delCosts,
double[] insCosts,
List<X> a,
List<Y> b)
This method has to be implemented by sub classes to transform a computed optimal assignment
of elements in the left set to elements in the right set to a valid result of the respective
implementation.
|
public AbstractStrictSetAlignmentAlgorithm(@NonNull Comparator<X,Y> comparator, @NonNull Class<R> resultClass)
public Class<R> getResultClass()
AlignmentAlgorithm
getResultClass
in interface AlignmentAlgorithm<X,Y,R>
public Comparator<X,Y> getComparator()
AlignmentAlgorithm
getComparator
in interface AlignmentAlgorithm<X,Y,R>
public void setComparator(@NonNull Comparator<X,Y> comparator)
AlignmentAlgorithm
setComparator
in interface AlignmentAlgorithm<X,Y,R>
comparator
- the comparator that is used to compute local distances for this Algorithm.public boolean requires(@NonNull OperationType type)
AlignmentAlgorithm
requires
in interface AlignmentAlgorithm<X,Y,R>
type
- an OperationType.public R calculateAlignment(@NonNull List<X> a, @NonNull List<Y> b)
AlignmentAlgorithm
calculateAlignment
in interface AlignmentAlgorithm<X,Y,R>
a
- The left input sequence.b
- The right input sequence.public abstract R transformToResult(@NonNull int[] assignment, @NonNull double[][] repCosts, @NonNull double[] delCosts, @NonNull double[] insCosts, @NonNull List<X> a, @NonNull List<Y> b)
assignment
- a vector of size m + n where the ith entry is the index j of the element in
the second set element i has been assigned to. If i is ≥ n then i has been assigned to
nothing. Furthermore, each element j in the second set where the entry m+j is j is assigned
to nothing.repCosts
- the matrix of pairwise REPLACEMENT costs for each pairwise combination of
elements in the input sets.delCosts
- the vector of DELETION costs for each element of the left input set.insCosts
- the vector of INSERTION costs for each element of the right input set.a
- the first input set.b
- the second input set.public static <X,Y> double normalizeDissimilarity(double d, @NonNull List<X> a, @NonNull List<Y> b)
X
- the class of elements in the first input sequence.Y
- the class of elements in the second input sequence.d
- the raw alignment distance between sequences a and b in the range [0,infinity)a
- the left-hand input sequence.b
- the right-hand input sequence.public static int[] align(@NonNull double[][] rep, @NonNull double[] del, @NonNull double[] ins)
rep
- a cost matrix where rep[i][j] is the cost of assigning element i in the first set
to element j in the second set.del
- a cost vector where del[i] is the cost of assigning element i in the first set
with nothing.ins
- a cost vector where ins[j] is the cost of assigning element j in the second set
with nothing.public static double distance(@NonNull double[][] rep, @NonNull double[] del, @NonNull double[] ins, @NonNull int[] assignment)
rep
- a cost matrix where rep[i][j] is the cost of assigning element i in the first set
to element j in the second set.del
- a cost vector where del[i] is the cost of assigning element i in the first set
with nothing.ins
- a cost vector where ins[j] is the cost of assigning element j in the second set
with nothing.assignment
- an m+n array specifying an alignment of both sets where the ith entry is
the index j of the element in the second set element i has been assigned to. If i is ≥ n
then i has been assigned to nothing. Furthermore, each element j in the second set where the
entry m+j is j is assigned to nothing.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/