Package com.crawljax.stateabstractions.dom.apted.distance

Class APTED<C extends CostModel,D>

java.lang.Object

com.crawljax.stateabstractions.dom.apted.distance.APTED<C,D>

Type Parameters:

C - type of cost model.

D - type of node data.

public class APTED<C extends CostModel,D>
extends Object

Implements APTED algorithm [1,2].

• Optimal strategy with all paths.
• Single-node single path function supports currently only unit cost.
• Two-node single path function not included.
• \Delta^L and \Delta^R based on Zhang and Shasha's algorithm for executing left and right paths (as in [3]). If only left and right paths are used in the strategy, the memory usage is reduced by one quadratic array.
• For any other path \Delta^A from [1] is used.

References:

• [1] M. Pawlik and N. Augsten. Efficient Computation of the Tree Edit Distance. ACM Transactions on Database Systems (TODS) 40(1). 2015.
• [2] M. Pawlik and N. Augsten. Tree edit distance: Robust and memory- efficient. Information Systems 56. 2016.
• [3] M. Pawlik and N. Augsten. RTED: A Robust Algorithm for the Tree Edit Distance. PVLDB 5(4). 2011.

Field Summary

Fields

Modifier and Type	Field	Description
private C	costModel	Cost model to be used for calculating costs of edit operations.
private long	counter	Stores the number of subproblems encountered while computing the distance [1, Section 10].
private float[][]	delta	The distance matrix [1, Sections 3.4,8.2,8.3].
private int[]	fn	Array used in the algorithm before [1].
private int[]	ft	Array used in the algorithm before [1].
private static byte	INNER	Identifier of inner path type = 2;
private NodeIndexer	it1	Indexer of the source tree.
private NodeIndexer	it2	Indexer of the destination tree.
private static byte	LEFT	Identifier of left path type = 0;
private float[]	q	One of distance arrays to store intermediate distances in spfA.
private static byte	RIGHT	Identifier of right path type = 1;
private int	size1	The size of the source input tree.
private int	size2	The size of the destination tree.

Constructor Summary

Constructors

Constructor	Description
APTED(C costModel)	Constructs the APTED algorithm object with the specified cost model.

Method Summary

Modifier and Type	Method	Description
float	computeEditDistance(AptedNode<D> t1, AptedNode<D> t2)	Compute tree edit distance between source and destination trees using APTED algorithm [1,2].
float	computeEditDistance_spfTest(AptedNode<D> t1, AptedNode<D> t2, int spfType)	This method is only for testing purspose.
List<int[]>	computeEditMapping()	Compute the edit mapping between two trees.
private int	computeKeyRoots(NodeIndexer it2, int subtreeRootNode, int pathID, int[] keyRoots, int index)	Calculates and stores keyroot nodes for left paths of the given subtree recursively.
float[][]	computeOptStrategy_postL(NodeIndexer it1, NodeIndexer it2)	Compute the optimal strategy using left-to-right postorder traversal of the nodes [2, Algorithm 1].
float[][]	computeOptStrategy_postR(NodeIndexer it1, NodeIndexer it2)	Compute the optimal strategy using right-to-left postorder traversal of the nodes [2, Algorithm 1].
private int	computeRevKeyRoots(NodeIndexer it2, int subtreeRootNode, int pathID, int[] revKeyRoots, int index)	Calculates and stores keyroot nodes for right paths of the given subtree recursively.
private void	forestDist(NodeIndexer ted1, NodeIndexer ted2, int i, int j, float[][] forestdist)	Recalculates distances between subforests of two subtrees.
private byte	getStrategyPathType(int pathIDWithPathIDOffset, int pathIDOffset, NodeIndexer it, int currentRootNodePreL, int currentSubtreeSize)	Decodes the path from the optimal strategy to its type.
private float	gted(NodeIndexer it1, NodeIndexer it2)	Implements GTED algorithm [1, Section 3.4].
void	init(AptedNode<D> t1, AptedNode<D> t2)	Initialises node indexers and stores input tree sizes.
float	mappingCost(List<int[]> mapping)	Calculates the cost of an edit mapping.
private void	revTreeEditDist(NodeIndexer it1, NodeIndexer it2, int it1subtree, int it2subtree, float[][] forestdist, boolean treesSwapped)	Implements the core of spfR.
private float	spf1(NodeIndexer ni1, int subtreeRootNode1, NodeIndexer ni2, int subtreeRootNode2)	Implements spf1 single path function for the case when one of the subtrees is a single node [2, Section 6.1, Algorithm 2].
private float	spfA(NodeIndexer it1, NodeIndexer it2, int pathID, byte pathType, boolean treesSwapped)	Implements the single-path function spfA.
private float	spfL(NodeIndexer it1, NodeIndexer it2, boolean treesSwapped)	Implements single-path function for left paths [1, Sections 3.3,3.4,3.5].
private float	spfR(NodeIndexer it1, NodeIndexer it2, boolean treesSwapped)	Implements single-path function for right paths [1, Sections 3.3,3.4,3.5].
private void	tedInit()	After the optimal strategy is computed, initialises distances of deleting and inserting subtrees without their root nodes.
private void	treeEditDist(NodeIndexer it1, NodeIndexer it2, int it1subtree, int it2subtree, float[][] forestdist, boolean treesSwapped)	Implements the core of spfL.
private void	updateFnArray(int lnForNode, int node, int currentSubtreePreL)	fn array used in the algorithm before [1].
private void	updateFtArray(int lnForNode, int node)	ft array used in the algorithm before [1].

Methods inherited from class java.lang.Object

clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

Field Detail

LEFT

private static final byte LEFT

Identifier of left path type = 0;

See Also:

Constant Field Values

RIGHT

private static final byte RIGHT

Identifier of right path type = 1;

See Also:

Constant Field Values

INNER

private static final byte INNER

Identifier of inner path type = 2;

See Also:

Constant Field Values

it1

private NodeIndexer it1

Indexer of the source tree.

it2

private NodeIndexer it2

Indexer of the destination tree.

size1

private int size1

The size of the source input tree.

size2

private int size2

The size of the destination tree.

delta

private float[][] delta

The distance matrix [1, Sections 3.4,8.2,8.3]. Used to store intermediate distances between pairs of subtrees.

q

private float[] q

One of distance arrays to store intermediate distances in spfA.

fn

private int[] fn

Array used in the algorithm before [1]. Using it does not change the complexity.

TODO: Do not use it [1, Section 8.4].

ft

private int[] ft

Array used in the algorithm before [1]. Using it does not change the complexity.

TODO: Do not use it [1, Section 8.4].

counter

private long counter

Stores the number of subproblems encountered while computing the distance [1, Section 10].

costModel

private final C extends CostModel costModel

Cost model to be used for calculating costs of edit operations.

Constructor Detail

APTED

public APTED(C costModel)

Constructs the APTED algorithm object with the specified cost model.

Parameters:

costModel - cost model for edit operations.

Method Detail

computeEditDistance

public float computeEditDistance(AptedNode<D> t1,
                                 AptedNode<D> t2)

Compute tree edit distance between source and destination trees using APTED algorithm [1,2].

Parameters:

t1 - source tree.

t2 - destination tree.

Returns:

tree edit distance.

computeEditDistance_spfTest

public float computeEditDistance_spfTest(AptedNode<D> t1,
                                         AptedNode<D> t2,
                                         int spfType)

This method is only for testing purspose. It computes TED with a fixed path type in the strategy to trigger execution of a specific single-path function.

Parameters:

t1 - source tree.

t2 - destination tree.

spfType - single-path function to trigger (LEFT or RIGHT).

Returns:

tree edit distance.

init

public void init(AptedNode<D> t1,
                 AptedNode<D> t2)

Initialises node indexers and stores input tree sizes.

Parameters:

t1 - source input tree.

t2 - destination input tree.

tedInit

private void tedInit()

After the optimal strategy is computed, initialises distances of deleting and inserting subtrees without their root nodes.

computeOptStrategy_postL

public float[][] computeOptStrategy_postL(NodeIndexer it1,
                                          NodeIndexer it2)

Compute the optimal strategy using left-to-right postorder traversal of the nodes [2, Algorithm 1].

Parameters:

it1 - node indexer of the source input tree.

it2 - node indexer of the destination input tree.

Returns:

array with the optimal strategy.

computeOptStrategy_postR

public float[][] computeOptStrategy_postR(NodeIndexer it1,
                                          NodeIndexer it2)

Compute the optimal strategy using right-to-left postorder traversal of the nodes [2, Algorithm 1].

Parameters:

it1 - node indexer of the source input tree.

it2 - node indexer of the destination input tree.

Returns:

array with the optimal strategy.

spf1

private float spf1(NodeIndexer ni1,
                   int subtreeRootNode1,
                   NodeIndexer ni2,
                   int subtreeRootNode2)

Implements spf1 single path function for the case when one of the subtrees is a single node [2, Section 6.1, Algorithm 2].

We allow an arbitrary cost model which in principle may allow renames to have a lower cost than the respective deletion plus insertion. Thus, Formula 4 in [2] has to be modified to account for that case.

In this method we don't have to verify if input subtrees have been swapped because they're always passed in the original input order.

Parameters:

ni1 - node indexer for the source input subtree.

ni2 - node indexer for the destination input subtree.

subtreeRootNode1 - root node of a subtree in the source input tree.

subtreeRootNode2 - root node of a subtree in the destination input tree.

Returns:

the tree edit distance between two subtrees of the source and destination input subtrees.

gted

private float gted(NodeIndexer it1,
                   NodeIndexer it2)

Implements GTED algorithm [1, Section 3.4].

Parameters:

it1 - node indexer for the source input tree.

it2 - node indexer for the destination input tree.

Returns:

the tree edit distance between the source and destination trees.

spfA

private float spfA(NodeIndexer it1,
                   NodeIndexer it2,
                   int pathID,
                   byte pathType,
                   boolean treesSwapped)

Implements the single-path function spfA. Here, we use it strictly for inner paths (spfL and spfR have better performance for leaft and right paths, respectively) [1, Sections 7 and 8]. However, in this stage it also executes correctly for left and right paths.

Parameters:

it1 - node indexer of the left-hand input subtree.

it2 - node indexer of the right-hand input subtree.

pathID - the left-to-right preorder id of the strategy path's leaf node.

pathType - type of the strategy path (LEFT, RIGHT, INNER).

treesSwapped - says if the order of input subtrees has been swapped compared to the order of the initial input trees. Used for accessing delta array and deciding on the edit operation.

Returns:

tree edit distance between left-hand and right-hand input subtrees.

spfL

private float spfL(NodeIndexer it1,
                   NodeIndexer it2,
                   boolean treesSwapped)

Implements single-path function for left paths [1, Sections 3.3,3.4,3.5]. The parameters represent input subtrees for the single-path function. The order of the parameters is important. We use this single-path function due to better performance compared to spfA.

Parameters:

it1 - node indexer of the left-hand input subtree.

it2 - node indexer of the right-hand input subtree.

treesSwapped - says if the order of input subtrees has been swapped compared to the order of the initial input trees. Used for accessing delta array and deciding on the edit operation.

Returns:

tree edit distance between left-hand and right-hand input subtrees.

computeKeyRoots

private int computeKeyRoots(NodeIndexer it2,
                            int subtreeRootNode,
                            int pathID,
                            int[] keyRoots,
                            int index)

Calculates and stores keyroot nodes for left paths of the given subtree recursively.

Parameters:

it2 - node indexer.

subtreeRootNode - keyroot node - recursion point.

pathID - left-to-right preorder id of the leftmost leaf node of subtreeRootNode.

keyRoots - array that stores all key roots in the order of their left-to-right preorder ids.

index - the index of keyRoots array where to store the next keyroot node.

Returns:

the index of the first keyroot node to process.

treeEditDist

private void treeEditDist(NodeIndexer it1,
                          NodeIndexer it2,
                          int it1subtree,
                          int it2subtree,
                          float[][] forestdist,
                          boolean treesSwapped)

Implements the core of spfL. Fills in forestdist array with intermediate distances of subforest pairs in dynamic-programming fashion.

Parameters:

it1 - node indexer of the left-hand input subtree.

it2 - node indexer of the right-hand input subtree.

it1subtree - left-to-right preorder id of the root node of the left-hand input subtree.

it2subtree - left-to-right preorder id of the root node of the right-hand input subtree.

forestdist - the array to be filled in with intermediate distances of subforest pairs.

treesSwapped - says if the order of input subtrees has been swapped compared to the order of the initial input trees. Used for accessing delta array and deciding on the edit operation.

spfR

private float spfR(NodeIndexer it1,
                   NodeIndexer it2,
                   boolean treesSwapped)

Implements single-path function for right paths [1, Sections 3.3,3.4,3.5]. The parameters represent input subtrees for the single-path function. The order of the parameters is important. We use this single-path function due to better performance compared to spfA.

Parameters:

it1 - node indexer of the left-hand input subtree.

it2 - node indexer of the right-hand input subtree.

treesSwapped - says if the order of input subtrees has been swapped compared to the order of the initial input trees. Used for accessing delta array and deciding on the edit operation.

Returns:

tree edit distance between left-hand and right-hand input subtrees.

computeRevKeyRoots

private int computeRevKeyRoots(NodeIndexer it2,
                               int subtreeRootNode,
                               int pathID,
                               int[] revKeyRoots,
                               int index)

Calculates and stores keyroot nodes for right paths of the given subtree recursively.

Parameters:

it2 - node indexer.

subtreeRootNode - keyroot node - recursion point.

pathID - left-to-right preorder id of the rightmost leaf node of subtreeRootNode.

revKeyRoots - array that stores all key roots in the order of their left-to-right preorder ids.

index - the index of keyRoots array where to store the next keyroot node.

Returns:

the index of the first keyroot node to process.

revTreeEditDist

private void revTreeEditDist(NodeIndexer it1,
                             NodeIndexer it2,
                             int it1subtree,
                             int it2subtree,
                             float[][] forestdist,
                             boolean treesSwapped)

Implements the core of spfR. Fills in forestdist array with intermediate distances of subforest pairs in dynamic-programming fashion.

Parameters:

it1 - node indexer of the left-hand input subtree.

it2 - node indexer of the right-hand input subtree.

it1subtree - left-to-right preorder id of the root node of the left-hand input subtree.

it2subtree - left-to-right preorder id of the root node of the right-hand input subtree.

forestdist - the array to be filled in with intermediate distances of subforest pairs.

treesSwapped - says if the order of input subtrees has been swapped compared to the order of the initial input trees. Used for accessing delta array and deciding on the edit operation.

getStrategyPathType

private byte getStrategyPathType(int pathIDWithPathIDOffset,
                                 int pathIDOffset,
                                 NodeIndexer it,
                                 int currentRootNodePreL,
                                 int currentSubtreeSize)

Decodes the path from the optimal strategy to its type.

Parameters:

pathIDWithPathIDOffset - raw path id from strategy array.

pathIDOffset - offset used to distinguish between paths in the source and destination trees.

it - node indexer.

currentRootNodePreL - the left-to-right preorder id of the current subtree processed in tree decomposition phase.

currentSubtreeSize - the size of the subtree currently processed in tree decomposition phase.

Returns:

type of the strategy path (LEFT, RIGHT, INNER).

updateFnArray

private void updateFnArray(int lnForNode,
                           int node,
                           int currentSubtreePreL)

fn array used in the algorithm before [1]. Using it does not change the complexity.

TODO: Do not use it [1, Section 8.4].

Parameters:

lnForNode - ---

node - ---

currentSubtreePreL - ---

updateFtArray

private void updateFtArray(int lnForNode,
                           int node)

ft array used in the algorithm before [1]. Using it does not change the complexity.

TODO: Do not use it [1, Section 8.4].

Parameters:

lnForNode - ---

node - ---

computeEditMapping

public List<int[]> computeEditMapping()

Compute the edit mapping between two trees. The trees are input trees to the distance computation and the distance must be computed before computing the edit mapping (distances of subtree pairs are required).

Returns:

Returns list of pairs of nodes that are mapped as pairs of their postorder IDs (starting with 1). Nodes that are deleted or inserted are mapped to 0.

forestDist

private void forestDist(NodeIndexer ted1,
                        NodeIndexer ted2,
                        int i,
                        int j,
                        float[][] forestdist)

Recalculates distances between subforests of two subtrees. These values are used in mapping computation to track back the origin of minimum values. It is basen on Zhang and Shasha algorithm.

The rename cost must be added in the last line. Otherwise the formula is incorrect. This is due to delta storing distances between subtrees without the root nodes.

i and j are postorder ids of the nodes - starting with 1.

Parameters:

ted1 - node indexer of the source input tree.

ted2 - node indexer of the destination input tree.

i - subtree root of source tree that is to be mapped.

j - subtree root of destination tree that is to be mapped.

forestdist - array to store distances between subforest pairs.

mappingCost

public float mappingCost(List<int[]> mapping)

Calculates the cost of an edit mapping. It traverses the mapping and sums up the cost of each operation. The costs are taken from the cost model.

Parameters:

mapping - an edit mapping.

Returns:

cost of edit mapping.