fr.orsay.lri.varna.models.treealign
Class TreeAlign.Aligner

java.lang.Object
  extended by fr.orsay.lri.varna.models.treealign.TreeAlign.Aligner
Enclosing class:
TreeAlign<ValueType1,ValueType2>

private class TreeAlign.Aligner
extends Object

For arrays that take at least O(|T1|*|T2|) we take care not to use too big data types.


Field Summary
private  float[] DEF1
          DEF1[i] is the distance between the empty forest and F1[i] (the forest of children of node i in the first tree).
private  float[] DEF2
          Same as DEF1, but for second tree.
private  float[] DET1
          DET1[i] is the distance between the empty tree and T1[i] (the subtree rooted at node i in the first tree).
private  float[] DET2
          Same as DET1, but for second tree.
private  float[][][][] DF1
          DF1[i][j_t] is DFL for (i,j,s,t) with s=0.
private  byte[][][][] DF1Decisions1
          This arrays have the same shape as respectively DF1.
private  short[][][][] DF1Decisions2
           
private  float[][][][] DF2
          DF2[j][i_s] is DFL for (i,j,s,t) with t=0.
private  byte[][][][] DF2Decisions1
          This arrays have the same shape as respectively DF2.
private  short[][][][] DF2Decisions2
           
private  float[][] DL
          Distances between labels.
private  float[][] DT
          Distances between subtrees.
private  byte[][] DTDecisions1
          This array has the same shape as DT, but is used to remember which case gave the minimum, so that we can later compute the alignment.
private  short[][] DTDecisions2
           
private  TreeAlign.TreeData<ValueType1> treeData1
          The first tree.
private  TreeAlign.TreeData<ValueType2> treeData2
          The second tree.
 
Constructor Summary
TreeAlign.Aligner(Tree<ValueType1> T1, Tree<ValueType2> T2)
           
 
Method Summary
 float align()
           
 Tree<AlignedNode<ValueType1,ValueType2>> computeAlignment()
           
private  void computeAlignmentP1(int i, int s, int m_i, int j, int t, int n_j, int DFx)
           
private  List<Tree<AlignedNode<ValueType1,ValueType2>>> computeForestAlignment(int i, int s, int p, int j, int t, int q)
          Align F1[i_s,i_p] with F2[j_t,j_q].
private  Tree<AlignedNode<ValueType1,ValueType2>> computeTreeAlignment(int i, int j)
           
private  Tree<AlignedNode<ValueType1,ValueType2>> treeDeleted(int i)
          Align T1[i] with the empty tree.
private  Tree<AlignedNode<ValueType1,ValueType2>> treeInserted(int j)
          Align the empty tree with T2[j].
 
Methods inherited from class java.lang.Object
clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait
 

Field Detail

treeData1

private TreeAlign.TreeData<ValueType1> treeData1
The first tree.


treeData2

private TreeAlign.TreeData<ValueType2> treeData2
The second tree.


DF1

private float[][][][] DF1
DF1[i][j_t] is DFL for (i,j,s,t) with s=0. See description of DFL in Aligner.computeAlignmentP1(). DF1 and DF2 are the "big" arrays, ie. those that may the space complexity what it is.


DF2

private float[][][][] DF2
DF2[j][i_s] is DFL for (i,j,s,t) with t=0. See description of DFL in Aligner.computeAlignmentP1().


DF1Decisions1

private byte[][][][] DF1Decisions1
This arrays have the same shape as respectively DF1. They are used to remember which term in the minimum won, so that we can compute the alignment. Decision1 is a case number (< 10) and Decision2 is a child index, hence the types.


DF1Decisions2

private short[][][][] DF1Decisions2

DF2Decisions1

private byte[][][][] DF2Decisions1
This arrays have the same shape as respectively DF2. They are used to remember which term in the minimum won, so that we can compute the alignment.


DF2Decisions2

private short[][][][] DF2Decisions2

DT

private float[][] DT
Distances between subtrees. DT[i][j] is the distance between the subtree rooted at i in the first tree and the subtree rooted at j in the second tree.


DTDecisions1

private byte[][] DTDecisions1
This array has the same shape as DT, but is used to remember which case gave the minimum, so that we can later compute the alignment.


DTDecisions2

private short[][] DTDecisions2

DL

private float[][] DL
Distances between labels. DL[i][j] is the distance labelDist.f(value(T1[i]), value(T2[i])). By convention, we say that value(T1[|T1|]) = null and value(T2[|T2|]) = null


DET1

private float[] DET1
DET1[i] is the distance between the empty tree and T1[i] (the subtree rooted at node i in the first tree).


DET2

private float[] DET2
Same as DET1, but for second tree.


DEF1

private float[] DEF1
DEF1[i] is the distance between the empty forest and F1[i] (the forest of children of node i in the first tree).


DEF2

private float[] DEF2
Same as DEF1, but for second tree.

Constructor Detail

TreeAlign.Aligner

public TreeAlign.Aligner(Tree<ValueType1> T1,
                         Tree<ValueType2> T2)
Method Detail

computeAlignmentP1

private void computeAlignmentP1(int i,
                                int s,
                                int m_i,
                                int j,
                                int t,
                                int n_j,
                                int DFx)
Parameters:
i - node in T1
s - number of first child of i to consider
m_i - degree of i
j - node in T2
t - number of first child of j to consider
n_j - degree of j
DFx - which array to fill (DF1 or DF2)

align

public float align()
            throws TreeAlignException
Throws:
TreeAlignException

computeForestAlignment

private List<Tree<AlignedNode<ValueType1,ValueType2>>> computeForestAlignment(int i,
                                                                              int s,
                                                                              int p,
                                                                              int j,
                                                                              int t,
                                                                              int q)
Align F1[i_s,i_p] with F2[j_t,j_q]. If p = s-1, by convention it means F1[i_s,i_p] = empty forest. Idem for q=t-1.


treeDeleted

private Tree<AlignedNode<ValueType1,ValueType2>> treeDeleted(int i)
Align T1[i] with the empty tree.

Returns:
the alignment

treeInserted

private Tree<AlignedNode<ValueType1,ValueType2>> treeInserted(int j)
Align the empty tree with T2[j].

Returns:
the alignment

computeTreeAlignment

private Tree<AlignedNode<ValueType1,ValueType2>> computeTreeAlignment(int i,
                                                                      int j)

computeAlignment

public Tree<AlignedNode<ValueType1,ValueType2>> computeAlignment()