Nearest Embedded and Embedding Self-Nested Trees

Abstract

Self-nested trees present a systematic form of redundancy in their subtrees and thus achieve optimal compression rates by directed acrylic graph (DAG) compression. A method for quantifying the degree of self-similarity of plants through self-nested trees was introduced by Godin and Ferraro in 2010. The procedure consists of computing a self-nested approximation, called the nearest embedding self-nested tree, that both embeds the plant and is the closest to it. In this paper, we propose a new algorithm that computes the nearest embedding self-nested tree with a smaller overall complexity, but also the nearest embedded self-nested tree. We show from simulations that the latter is mostly the closest to the initial data, which suggests that this better approximation should be used as a privileged measure of the degree of self-similarity of plants.

1. Introduction

Trees form a wide family of combinatorial objects that offers many application fields, e.g., plant modeling and XML files analysis. Modern databases are huge and thus stored in compressed form. Compression methods take advantage of repeated substructures appearing in the tree. As explained in [1], one often considers the following two types of repeated substructures: subtree repeat (used in DAG compression [2,3,4,5]) and tree pattern repeat (exploited in tree grammars [6,7] and top tree compression [1]). We restrict ourselves to DAG compression of unordered rooted trees, which consists of building a Directed Acyclic Graph (DAG) that represents a tree without the redundancy of its identical subtrees (see Figure 1). Two different algorithms exist for computing the DAG reduction of a tree $\tau$ [5] (2.2 Computing Tree Reduction), which share the same time-complexity in $O(\#\mathcal{V}{\left(\tau \right)}^2\times \mathcal{D}\left(\tau \right)\times log\left(\mathcal{D}\left(\tau \right)\right))$ where $\mathcal{V}\left(\tau \right)$ denotes the set of vertices of $\tau$ and $\mathcal{D}\left(\tau \right)$ its outdegree.

Trees that are the most compressed by DAG compression present the highest level of redundancy in their subtrees: all the subtrees of a given height are isomorphic. In this case, the DAG related to a tree $\tau$ is linear, i.e., there exists a path going through all vertices, with exactly $\mathcal{H}\left(\tau \right)+1$ vertices, $\mathcal{H}\left(\tau \right)$ denoting the height of $\tau$, which is the minimal number of vertices among trees of this height (see ${\tau }_3$ in Figure 1). This family of trees has been introduced in [8] as the first interesting class of trees for which the subtree isomorphism problem is in NC${}^2$. It has been known under the name of nested trees [8] and next self-nested trees [5] to insist on their recursive structure and their proximity to the notion of structural self-similarity.

The authors of [5] are interested in capturing the self-similarity of plants through self-nested trees. They propose to construct a self-nested tree that minimizes the distance of the original tree to the set of self-nested trees that embed the initial tree. The distance to this Nearest Embedding Self-nested Tree (NEST) is then used to quantify the self-nestedness of the tree and thus its structural self-similarity (see $\tau$ and $\mathrm{NEST}\left(\tau \right)$ in Figure 2). The main result of [5] (Theorem 1 and E. NEST Algorithm) is an algorithm that computes the NEST of a tree $\tau$ from its DAG reduction in $O(\mathcal{H}{\left(\tau \right)}^2\times \mathcal{D}\left(\tau \right))$.

The goal of the present article is three-fold. We aim at proposing a new and more explicit algorithm that computes the NEST of a tree $\tau$ with the same time-complexity $O(\mathcal{H}{\left(\tau \right)}^2\times \mathcal{D}\left(\tau \right))$ as in [5] but that takes as input the height profile of $\tau$ and not its DAG reduction. We establish that the height profile of a tree $\tau$ can be computed in $O(\#\mathcal{V}(\tau )\times \mathcal{D}(\tau ))$ reducing the overall complexity of a linear factor. Based on this work, we also provide an algorithm in $O(\mathcal{H}{\left(\tau \right)}^2)$ that computes the Nearest embedded Self-nested Tree (NeST) of a tree $\tau$ (see $\tau$ and $\mathrm{NeST}\left(\tau \right)$ in Figure 2). Finally, we show from numerical simulations that the distance of a tree $\tau$ to its NeST is much lower than the distance to its NEST. The NeST is most of the time a better approximation of a tree than the NEST and thus should be privileged to quantify the degree of self-nestedness of plants.

The paper is organized as follows. The structures of interest in this paper, namely unordered trees, DAG compression and self-nested trees, are defined in Section 2. Section 3 is dedicated to the definition and the study of the height profile of a tree. The approximation algorithms are presented in Section 4. We give a new insight on the definitions of the NEST and of the NeST in Section 4.1. Our NEST algorithm is presented in Section 4.2, while the NeST algorithm is given in Section 4.3. Section 5 is devoted to simulations. We state that the NeST is mostly a better approximation of a tree than the NEST in Section 5.1. An application to a real rice panicle is presented in Section 5.2. A summary of the paper and concluding remarks can be found in Section 6. All the figures and numerical experiments presented in the article have been made with the Python library treex [9].

2. Preliminaries

2.1. Unordered Rooted Trees

A rooted tree $\tau$ is a connected graph containing no cycle, i.e., without chain from any vertex v to itself, and such that there exists a unique vertex $\mathcal{R}\left(\tau \right)$, called the root, which has no parent, and any vertex different from the root has exactly one parent. The leaves of $\tau$ are all the vertices without children. The set of vertices of $\tau$ is denoted by $\mathcal{V}\left(\tau \right)$. The height of a vertex v may be recursively defined as $\mathcal{H}\left(v\right)=0$ if v is a leaf of $\tau$ and

$$\mathcal{H}\left(v\right)=1+\underset{w\in {\mathcal{C}}_{\tau }\left(v\right)}{max}\mathcal{H}\left(w\right)$$

otherwise, ${\mathcal{C}}_{\tau }\left(v\right)$ denoting the set of children of v in $\tau$. The height of the tree $\tau$ is defined as the height of its root, $\mathcal{H}\left(\tau \right)=\mathcal{H}\left(\mathcal{R}\right(\tau \left)\right)$. The outdegree $\mathcal{D}\left(\tau \right)$ of $\tau$ is the maximal branching factor that can be found in $\tau$, i.e.,

$$\mathcal{D}\left(\tau \right)=\underset{v\in \tau }{max}\#{\mathcal{C}}_{\tau }\left(v\right).$$

A subtree $\tau \left[v\right]$ rooted in v is a particular connected subgraph of $\tau$. Precisely, $\tau \left[v\right]=\left(V\right[v],E[v\left]\right)$ where $V\left[v\right]$ is the set of the descendants of v in $\tau$ and $E\left[v\right]$ is defined as

$$E\left[v\right]=\left\{(\xi ,{\xi }^{\prime })\in \mathcal{E}\left(\tau \right):\xi \in V\left[v\right],{\xi }^{\prime }\in V\left[v\right]\right\},$$

with $\mathcal{E}\left(\tau \right)$ the set of edges of $\tau$.

In all the sequel, we consider unordered rooted trees for which the order among the sibling vertices of any vertex is not significant. A precise characterization is obtained from the additional definition of isomorphic trees. Let $\tau$ and $\theta$ two rooted trees. A one-to-one correspondence $\phi :\mathcal{V}\left(\tau \right)\to \mathcal{V}\left(\theta \right)$ is called a tree isomorphism if, for any edge $(v,w)\in \mathcal{E}\left(\tau \right)$, $\left(\phi \right(v),\phi (w\left)\right)\in \mathcal{E}\left(\theta \right)$. Structures ${\tau }_1$ and ${\tau }_2$ are called isomorphic trees whenever there exists a tree isomorphism between them. One can determine if two n-vertex trees are isomorphic in $O\left(n\right)$ [10] (Example 3.2 and Theorem 3.3). The existence of a tree isomorphism defines an equivalence relation on the set of rooted trees. The class of unordered rooted trees is the set of equivalence classes for this relation, i.e., the quotient set of rooted trees by the existence of a tree isomorphism.

2.2. DAG Compression

Now we consider the equivalence relation “existence of a tree isomorphism” on the set of the subtrees of a tree $\tau$. We consider the quotient graph $\mathcal{Q}\left(\tau \right)=(V,E)$ obtained from $\tau$ using this equivalence relation. V is the set of equivalence classes on the subtrees of $\tau$, while E is a set of pairs of equivalence classes $(C_1,C_2)$ such that $\mathcal{R}\left(C_2\right)\in {\mathcal{C}}_{\tau }\left(\mathcal{R}\left(C_1\right)\right)$ up to an isomorphism. The graph $\mathcal{Q}\left(\tau \right)$ is a DAG [5] (Proposition 1) that is a connected directed graph without path from any vertex v to itself.

Let $(C_1,C_2)$ be an edge of the DAG $\mathcal{Q}\left(\tau \right)$. We define $N(C_1,C_2)$ as the number of occurrences of a tree of $C_2$ just below the root of any tree of $C_1$. The tree reduction $\mathcal{R}\left(\tau \right)$ is defined as the quotient graph $\mathcal{Q}\left(\tau \right)$ augmented with labels $N(C_1,C_2)$ on its edges [5] (Definition 3 (Reduction of a tree)). Intuitively, the graph $\mathcal{R}\left(\tau \right)$ represents the original tree $\tau$ without its structural redundancies (see Figure 1).

2.3. Self-Nested Trees

A tree $\tau$ is called self-nested [5] (III. Self-nested trees) if for any pair of vertices v and w, either the subtrees $\tau \left[v\right]$ and $\tau \left[w\right]$ are isomorphic, or one is (isomorphic to) a subtree of the other. This characterization of self-nested trees is equivalent to the following statement: for any pair of vertices v and w such that $\mathcal{H}\left(v\right)=\mathcal{H}\left(w\right)$, $\tau \left[x\right]=\tau \left[y\right]$, i.e., all the subtrees of the same height are isomorphic.

Linear DAGs are DAGs containing at least one path that goes through all their vertices. They are closely connected with self-nested trees by virtue of the following result.

Proposition 1

(Godin and Ferraro [5]). A tree τ is self-nested if and only if its reduction $\mathcal{R}\left(\tau \right)$ is a linear DAG.

This result proves that self-nested trees achieve optimal compression rates among trees of the same height whatever their number of nodes (compare ${\tau }_3$ with ${\tau }_1$ and ${\tau }_2$ in Figure 1). Indeed, $\mathcal{R}\left(\tau \right)$ has at least $\mathcal{H}\left(\tau \right)+1$ nodes and the inequality is saturated if and only if $\tau$ is self-nested.

3. Height Profile of the Tree Structure

3.1. Definition and Complexity

This section is devoted to the definition of the height profile ${\rho }_{\tau }$ of a tree $\tau$ and to the presentation of an algorithm to calculate it. In the sequel, we assume that the tree $\tau$ is always traversed in the same order, depth-first search to set the ideas down. In particular, when vectors are indexed by nodes of $\tau$ sharing the same property, the order of the vector is important and should be always the same.

Given a vertex $v\in \mathcal{V}\left(\tau \right)$,

$${\gamma }_h\left(v\right)=\#\{v^{\prime }\in {\mathcal{C}}_{\tau }\left(v\right):\mathcal{H}\left(\tau \left[v^{\prime }\right]\right)=h\}$$

is the number of subtrees of height h directly under v. Now, we consider the vector

$${\rho }_{\tau }(h_1,h_2)=\left({\gamma }_{h_2}\left(v\right):v\in \mathcal{V}\left(\tau \right),\mathcal{H}\left(\tau \left[v\right]\right)=h_1\right)$$

made of the concatenation of the integers ${\gamma }_{h_2}\left(v\right)$ over subtrees $\tau \left[v\right]$ of height $h_1$ ordered in depth-first search. Consequently, ${\rho }_{\tau }$ is an array made of vectors with varying lengths.

Let $A_1$ and $A_2$ be two arrays for which each entry is a vector. We say that $A_1$ and $A_2$ are equivalent if, for any line i, there exists a permutation ${\sigma }_i$ such that for any column j,

$$A_1(i,j)={\sigma }_i\left(A_2(i,j)\right).$$

In particular, i being fixed, all the vectors $A_1(i,j)$ and $A_2(i,j)$ must have the same length. This condition defines an equivalence relation. The height profile of $\tau$ is the array ${\rho }_{\tau }$ as an element of the quotient space of arrays of vectors under this equivalence relation. In other words, the vectors ${\rho }_{\tau }(h_1,h_2)$, $0\le h_2<h_1$ and $h_1$ fixed, must be ordered in the same way but the choice of the order is not significant. Finally, it should be already remarked that ${\rho }_{\tau }(h_1,h_2)=\varnothing$ when $h_2\ge h_1$ or $h_1>\mathcal{H}\left(\tau \right)$. Consequently, the height profile can be reduced to the triangular array

$${\rho }_{\tau }={\left[{\rho }_{\tau }(h_1,h_2)\right]}_{0\le h_2<h_1\le \mathcal{H}\left(\tau \right)}.$$

The application ${\rho }_{\tau }$ provides the distribution of subtrees of height $h_2$ just below the root of subtrees of height $h_1$ for all couples $(h_1,h_2)$, which typically represents the height profile of $\tau$. For clarity’s sake, we give the values of ${\rho }_{{\tau }_k}$ for the trees ${\tau }_k$ of Figure 1, coefficient $(i,j)$ of the matrix being ${\rho }_{{\tau }_k}(i,j-1)$,

$${\rho }_{{\tau }_1}={\rho }_{{\tau }_2}=\left[\begin{array}{ccc}(1,1,2)& \varnothing & \varnothing \\ (0,1,1)& (1,1,1)& \varnothing \\ \left(0\right)& \left(0\right)& \left(3\right)\end{array}\right]\mathrm{and}{\rho }_{{\tau }_3}=\left[\begin{array}{ccc}(1,1,1)& \varnothing & \varnothing \\ (1,1,1)& (1,1,1)& \varnothing \\ \left(0\right)& \left(0\right)& \left(3\right)\end{array}\right].$$

(1)

It should be noticed that the height profile does not contain all the topology of the tree since trees ${\tau }_1$ and ${\tau }_2$ of Figure 1 are different but share the same height profile (1). However, the height of a tree $\tau$ can be recovered from its height profile through the relation $\mathcal{H}\left(\tau \right)=dim\left({\rho }_{\tau }\right)$, the dimension of ${\rho }_{\tau }$ being defined by

$$dim\left({\rho }_{\tau }\right)=min\left\{n\ge 0:\forall i\ge 0,{\rho }_{\tau }(n+1,i)=\varnothing \right\}.$$

Proposition 2.

${\rho }_{\tau }$ can be computed in $O(\#\mathcal{V}(\tau )\times \mathcal{D}(\tau ))$-time.

Proof. 

First, attribute to each node $v\in \mathcal{V}\left(\tau \right)$ the height of the subtree $\tau \left[v\right]$ with complexity $O(\#\mathcal{V}(\tau ))$. Next, traverse the tree in depth-first search in $O(\#\mathcal{V}(\tau ))$ and calculate for each vertex v the vector ${\left({\gamma }_h\left(v\right)\right)}_{0\le h<\mathcal{H}\left(\tau \right[v\left]\right)}$ in $\#{\mathcal{C}}_{\tau }\left(v\right)\le \mathcal{D}\left(\tau \right)$ operations. Finally, append this vector to ${\rho }_{\tau }(\mathcal{H}\left(\tau \left[v\right]\right),·)$ component by component. □

3.2. Relation with Self-Nested Trees

Self-nested trees are characterized by their height profile considering the following result.

Proposition 3.

τ is self-nested if and only if, for any $0\le h_2<h_1\le \mathcal{H}\left(\tau \right)$, all the components of the vector ${\rho }_{\tau }(h_1,h_2)$ are the same (for instance see the profile (1) of the tree ${\tau }_3$ presented in Figure 1). In addition, a self-nested tree τ can be reconstructed from ${\rho }_{\tau }$ (see Algorithm 1).

Proof. 

If $\tau$ is self-nested, the $N_{h_1}$ subtrees of height $h_1$ appearing in $\tau$ are isomorphic and thus have the same number $n_{h_1,h_2}$ of subtrees of height $h_2$ just below their root. Consequently,

$${\rho }_{\tau }(h_1,h_2)=\underset{N_{h_1}}{\underleftrightarrow{(n_{h_1,h_2},\dots ,n_{h_1,h_2})}}.$$

The reciprocal result may be established considering the following lemma which proof presents no difficulty. □

Lemma 1.

If all the subtrees of height $0\le h<H$ appearing in a tree τ are isomorphic, and if all the subtrees of height H have the same number of subtrees of height $0\le h<H$ just below their root, then all the subtrees of height H appearing in τ are isomorphic.

All the subtrees of height 1 in $\tau$ are isomorphic because all the components of ${\rho }_{\tau }(1,0)$ are the same. The expected result is shown by induction on the height thanks to the previous lemma which assumptions are satisfied since ${\rho }_{\tau }$ always contains vectors for which all the entries are equal. The previous reasoning also provides a way (presented in Algorithm 1) to build a unique (self-nested) tree $\mathcal{T}$ from the height profile ${\rho }_{\tau }$. In addition, this is easy to see that $\tau$ and $\mathcal{T}$ are isomorphic.

To present the algorithm of reconstruction of a self-nested tree from its height profile, we need to define the restriction of a height profile to some height. Let p be a height profile. The restriction $p_{{|}_h}$ of p to height $h\ge 0$ is the array defined by

$$\left\{\begin{array}{ccc}\forall 1\le h_1\le h,\hfill & \forall h_2\ge 0,\hfill & p_{{|}_h}(h_1,h_2)=p(h_1,h_2),\hfill \\ \forall h_1>h,\hfill & \forall h_2\ge 0,\hfill & p_{{|}_h}(h_1,h_2)=\varnothing .\hfill \end{array}\right.$$

Consequently, $dim(p_{{|}_h})=min(dim\left(p\right),h)$. A peculiar case is $p_{{|}_0}$ for which each entry is the empty set and thus $dim(p_{{|}_0})=0$. It should be also remarked that there may exist no tree $\tau$ such that $p_{{|}_h}$ is the height profile of $\tau$.

Algorithm 1: Construction of a self-nested tree from its height profile.

As we can see in the proof of Proposition 3 or in Algorithm 1, the lengths of the vectors ${\rho }_{\tau }(h_1,h_2)$ are not significant to reconstruct a self-nested tree $\tau$. Consequently, since all the components of ${\rho }_{\tau }(h_1,h_2)$ are the same, we can identify the height profile of a self-nested tree with the integer-valued array $\left[{\rho }_{\tau }{(h_1,h_2)}_1\right]$.

Proposition 4.

The number of nodes of a self-nested tree τ can be computed from ${\rho }_{\tau }$ in $O(\mathcal{H}{\left(\tau \right)}^2)$.

Proof. 

By induction on the height, one has $\#\mathcal{V}\left(\tau \right)=\mathcal{N}\left(\mathcal{H}\right(\tau \left)\right)$, where the sequence $\mathcal{N}$ is defined by $\mathcal{N}\left(0\right)=1$ (number of nodes of a tree reduced to a root) and,

$$\forall 1\le H\le \mathcal{H}\left(\tau \right),\mathcal{N}\left(H\right)=1+\sum _{h=0}^{H-1}{\rho }_{\tau }(H,h)\mathcal{N}\left(h\right).$$

(2)

The number of operations required to compute $\mathcal{N}\left(\mathcal{H}\right(\tau \left)\right)$ is of order $O(\mathcal{H}{\left(\tau \right)}^2)$. □

The authors of [5] (Proposition 6) calculate the number of nodes of a tree (self-nested or not) from its DAG reduction by a formula very similar to (2), and which achieve the same complexity on self-nested trees. As mentioned before, a tree cannot be recovered from its height profile in general, thus we cannot expect such a result from the height profile of any tree.

4. Approximation Algorithms

4.1. Definitions

4.1.1. Editing Operations

We shall define the NEST and the NeST of a tree $\tau$. As in [5] (Equation (5)), we ask these approximations to be consistent with Zhang’s edit distance between unordered trees [11] denoted $D_Z$ in this paper. Thus, as in [11] (2.2 Editing Operations), we consider the following two types of editing operations: adding a node and deleting a node. Deleting a node w means making the children of w become the children of the parent v of w and then removing w (see Figure 3). Adding w as a child of v will make w the parent of a subset of the current children of v (see Figure 4).

4.1.2. Constrained Editing Operations

Zhang’s edit distance is defined from the above editing operations and from constrained mappings between trees [11] (3.1 Constrained Edit Distance Mappings). A constrained mapping between two trees $\tau$ and $\theta$ is a mapping [11] (2.3.2 Editing Distance Mappings), i.e., a one-to-one correspondence $\phi$ from a subset of $\mathcal{V}\left(\tau \right)$ into a subset of $\mathcal{V}\left(\theta \right)$ preserving the ancestor order, with an additional condition on the Least Common Ancestors (LCAs) [11] (condition (2) p. 208): if, for $1\le i\le 3$, $v_i\in \mathcal{V}\left(\tau \right)$ and $w_i=\phi \left(v_i\right)\in \mathcal{V}\left(\theta \right)$, then $\mathrm{LCA}(v_1,v_2)$ is a proper ancestor of $v_3$ if and only if $\mathrm{LCA}(w_1,w_2)$ is a proper ancestor of $w_3$.

Let $\theta$ be a tree that approximates $\tau$ obtained by inserting nodes in $\tau$ only and consider the induced mapping $M_{\tau \to \theta }$ that associates nodes of $\tau$ with themselves in $\theta$. We want the approximation process to be consistent with Zhang’s edit distance $D_Z$, i.e., we want the mapping $M_{\tau \to \theta }$ to be a constrained mapping in the sense of Zhang, which in particular implies $D_Z(\theta ,\tau )=\#\mathcal{V}\left(\theta \right)-\#\mathcal{V}\left(\tau \right)$. We shall prove that this requirement excludes some inserting operations in our context.

Indeed, the mapping $M_{\tau \to \theta }$ involved in the inserting operation of Figure 4 is partially displayed in Figure 5, nodes $v_i$ of $\tau$ being associated with nodes $w_i$ of $\theta$. The LCA of $v_1$ and $v_2$ in $\tau$ is a proper ancestor of $v_3$. However, the LCA of $w_1$ and $w_2$ in $\theta$ is not a proper ancestor of $w_3$. Consequently, this mapping is not a constrained mapping as defined by Zhang. A necessary and sufficient condition for $M_{\tau \to \theta }$ to be a constrained mapping is given in Lemma 2.

Lemma 2.

Let τ be a tree and $v\in \mathcal{V}\left(\tau \right)$. Let θ be the tree obtained from τ by adding a node w as a child of v making the nodes of the subset $C\subset {\mathcal{C}}_{\tau }\left(v\right)$ children of w. The mapping $M_{\tau \to \theta }$ induced by these inserting operations is a constrained mapping in the sense of Zhang if and only if $C=\varnothing$, $\#C=1$ or $\#C=\#{\mathcal{C}}_{\tau }\left(v\right)$.

Proof. 

The proof is obvious if v has one or two children. Thus, we assume that v has at least three children $c_1$, $c_2$ and $c_3$. In $\tau$, the LCA of $c_1$ and $c_2$ is v and v is an ancestor of $c_3$. Adding w as the parent of $c_1$ and $c_2$ makes it the LCA of these two nodes, but not an ancestor of $c_3$ in $\theta$. The additional condition on the LCAs is then not satisfied. This problem appears only when making w the parent of at least two children and of not all the children of v. □

Consequently, we restrict ourselves to the following inserting operations which are the only ones that ensure that the associated mapping satisfies Zhang’s condition: adding w as a child of v will make w (i) a leaf, (ii) the parent of one current child of v, or (iii) the parent of all the current children of v. However, it should be noticed that (iii) can always be expressed as (ii) (see Figure 6). Finally, we only consider the inserting operations that make the new child of v the parent of zero or one current child of v. For obvious reasons of symmetry, the allowed deleting operations are the complement of inserting operations, i.e., one can delete an internal node if and only if it has a unique child, which also ensures that the induced mapping is constrained in the sense of Zhang.

4.1.3. Preserving the Height of the Pre-Existing Nodes

In [5] (Definition 9 and Figure 6), the NEST of a tree $\tau$ is obtained by successive partial linearizations of the (non-linear) DAG of $\tau$ which consist of merging all the nodes at the same height of the DAG. A consequence is that the height of any pre-existing node of $\tau$ is not changed by the inserting operations. For the sake of consistency with [5], we only consider inserting and deleting operations that preserve the height of all the pre-existing nodes of $\tau$.

The next two results deal with inserting operations that preserve the height of the pre-existing nodes.

Lemma 3.

Let τ be a tree, $v\in \mathcal{V}\left(\tau \right)$ and $c\in {\mathcal{C}}_{\tau }\left(v\right)$. Let θ be the tree obtained from τ by adding the internal node w as a child of v making w the parent of c. Then,

$$\forall u\in \mathcal{V}\left(\tau \right),\mathcal{H}\left(\theta \right[u\left]\right)=\mathcal{H}\left(\tau \right[u\left]\right)⟺\mathcal{H}\left(\tau \right[c\left]\right)+1<\mathcal{H}\left(\tau \right[v\left]\right).$$

Proof. 

Adding w may only increase the height of v and the one of its ancestors in $\tau$. If the height of v is not changed by adding w, the height of its ancestors will not be modified. The height of v remains unchanged if and only if the height of w in $\theta$, i.e., $\mathcal{H}\left(\tau \right[c\left]\right)+1$, is strictly less than the height of $\tau \left[v\right]$. □

Lemma 4.

Let τ be a tree and $v\in \mathcal{V}\left(\tau \right)$. Let θ be the tree obtained from τ by adding a tree t as a child of v. Then,

$$\forall u\in \mathcal{V}\left(\tau \right),\mathcal{H}\left(\theta \right[u\left]\right)=\mathcal{H}\left(\tau \right[u\left]\right)⟺\mathcal{H}\left(t\right)+1\le \mathcal{H}\left(\tau \right[v\left]\right).$$

Proof. 

Adding a subtree t under v may only increase the height of v and the one of its ancestors in $\tau$. If the height of v is not changed by adding t, the height of its ancestors will not be modified. Adding t will make the height of v increase if $\mathcal{H}\left(t\right)$ is strictly greater than the height of the higher child of v. □

A particular case of Lemma 4 is the insertion of leaves in a tree. Considering the above result, a leaf can be added under v if and only if $\mathcal{H}\left(\tau \right[v\left]\right)\ge 1$, i.e., v is not a leaf. The below results concern deleting operations that preserve the height of the remaining nodes of $\tau$.

Lemma 5.

Let τ be a tree, $v\in \mathcal{V}\left(\tau \right)$, $w\in {\mathcal{C}}_{\tau }\left(v\right)$ and ${\mathcal{C}}_{\tau }\left(w\right)=\left\{c\right\}$. Let θ be the tree obtained from τ by deleting the internal node w making its unique child c a child of v. Then,

$$\forall u\in \mathcal{V}\left(\theta \right),\mathcal{H}\left(\theta \left[u\right]\right)=\mathcal{H}\left(\tau \left[u\right]\right)⟺\exists w^{\prime }\in {\mathcal{C}}_{\tau }\left(v\right)\backslash \left\{w\right\},\mathcal{H}\left(\tau \left[w^{\prime }\right]\right)+1=\mathcal{H}\left(\tau \left[v\right]\right).$$

Proof. 

Deleting w may only decrease the height of v and the one of its ancestors in $\tau$. If the height of v is not changed by deleting w, the height of its ancestors will not be modified. The height of v remains unchanged if and only if it has a child different of w of height $\mathcal{H}\left(\tau \right[v\left]\right)-1$. □

Lemma 6.

Let τ be a tree, $v\in \mathcal{V}\left(\tau \right)$, $c\in {\mathcal{C}}_{\tau }\left(v\right)$. Let θ be the tree obtained from τ by deleting the subtree $\tau \left[c\right]$. Then,

$$\forall u\in \mathcal{V}\left(\theta \right),\mathcal{H}\left(\theta \left[u\right]\right)=\mathcal{H}\left(\tau \left[u\right]\right)⟺\exists c^{\prime }\in {\mathcal{C}}_{\tau }\left(v\right)\backslash \left\{c\right\},\mathcal{H}\left(\tau \left[c^{\prime }\right]\right)+1=\mathcal{H}\left(\tau \left[v\right]\right).$$

Proof. 

The proof follows the same reasoning as in the previous result. □

4.1.4. NEST and NeST

In view of the foregoing, we consider the set of inserting and deleting operations that fulfill the below requirements.

Adding operations (see Figure 7)

• Internal nodes (AI): adding w as a child of v making w the parent of the child c of v can be done only if $\mathcal{H}\left(\tau \right[c\left]\right)+1<\mathcal{H}\left(\tau \right[v\left]\right)$.
• Subtrees (AS): adding t as a child of v can be done only if $\mathcal{H}\left(t\right)+1\le \mathcal{H}\left(\tau \right[v\left]\right)$.

Deleting operations (see Figure 8)

• Internal nodes (DI): deleting $v\in {\mathcal{C}}_{\tau }\left(u\right)$ (making the unique child w of v a child of u) can be done only if there exists $v^{\prime }\in {\mathcal{C}}_{\tau }\left(u\right)$, $v\ne v^{\prime }$, such that $\mathcal{H}\left(\tau \left[v^{\prime }\right]\right)\ge \mathcal{H}\left(\tau \left[v\right]\right)$.
• Subtrees (DS): deleting the subtree $\tau \left[w\right]$, $w\in {\mathcal{C}}_{\tau }\left(v\right)$, of $\tau$ can be done if there exists $w^{\prime }\in {\mathcal{C}}_{\tau }\left(v\right)$, $w^{\prime }\ne w$, such that $\mathcal{H}\left(\tau \left[w^{\prime }\right]\right)+1=\mathcal{H}\left(\tau \left[v\right]\right)$.

Proposition 5.

The editing operations AI and AS (DI and DS, respectively) are the only inserting (deleting, respectively) operations that ensure that (i) the induced mapping is a constrained mapping and that (ii) the height of all the pre-existing nodes is unchanged.

Proof. 

This result is a direct corollary of Lemmas 2–6. □

The NEST (the NeST, respectively) of a tree $\tau$ is the self-nested tree obtained by the set of inserting operations AI and AS (of deleting operations DI and DS, respectively) of minimal cost, the cost of inserting a subtree being its number of nodes. Existence and uniqueness of the NEST are not obvious at this stage. The NeST exists because the (self-nested) tree composed of a unique root can be easily obtained by deleting operations from any tree, but its uniqueness is not evident.

4.2. NEST Algorithm

To present our NEST algorithm in a concise form in Algorithm 2, we need to define the following operations involving two vectors u and v of the same size n and a real number $\gamma$,

$$\left\{\begin{array}{ccccc}u& +& v& =& (u_1+v_1,\dots ,u_n+v_n),\hfill \\ u& +& \gamma & =& (u_1+\gamma ,\dots ,u_n+\gamma ),\hfill \\ u& \vee & \gamma & =& (max(u_1,\gamma ),\dots ,max(u_n,\gamma )).\hfill \end{array}\right.$$

In other words, these operations must be understood component by component. In addition, in a condition, $u=0$ ($u\ne 0$, respectively) means that for all $1\le i\le n$, $u_i=0$ ($u_i\ne 0$, respectively). Finally, for $1\le i\le j\le n$, $u_{i\dots j}$ denotes the vector $(u_i,\dots ,u_j)$ of length $j-i+1$. This notation will also be used in Algorithm 3 for calculating the NeST. It should be noticed that an illustrative example that can help the reader to follow the progress of the algorithm is provided in Section 6.

Algorithm 2: Construction of the nearest embedding self-nested tree.

The relation between the above algorithm and the NEST of a tree is provided in the following result, which states in particular the existence of the NEST.

Proposition 6.

For any tree τ, Algorithm 2 returns the unique NEST of τ in $O(\mathcal{H}{\left(\tau \right)}^2\times \mathcal{D}\left(\tau \right))$.

Proof. 

By definition of the NEST, the height of all the pre-existing nodes of $\tau$ cannot be modified. Thus, the number of nodes of height $h-1$ under a node of height h can only increase by inserting subtrees in the structure. Then we have

$${\rho }_{\mathrm{NEST}\left(\tau \right)}(h,h-1)\ge max{\rho }_{\tau }(h,h-1).$$

(3)

Let v be a vertex of height h in $\tau$. We recall that ${\gamma }_i\left(v\right)$ denotes the number of subtrees of height i under v. Our objective is to understand the consequences for ${\gamma }_i\left(v\right)$ of inserting operations to obtain ${\rho }_{\mathrm{NEST}\left(\tau \right)}(h,h-1)$ subtrees of height $h-1$ under v. To this aim, we shall define a sequence ${\gamma }_i^{(h-1,j)}\left(v\right)$ starting from ${\gamma }_i^{(h-1,0)}\left(v\right)={\gamma }_i\left(v\right)$ that corresponds to the modified versions of $\tau$. The first exponent $h-1$ means that this sequence concerns editing operations used to get the good number of subtrees of height $h-1$ under v. □

Let ${\Delta }_{h-1}^{\left(0\right)}\left(v\right)={\rho }_{\mathrm{NEST}\left(\tau \right)}(h,h-1)-{\gamma }_{h-1}^{\left(0\right)}\left(v\right)$ be the number of subtrees of height $h-1$ that must be added under v to obtain the height profile of the NEST under v, i.e.,

$${\gamma }_{h-1}^{(h-1,1)}\left(v\right)={\rho }_{\mathrm{NEST}\left(\tau \right)}(h,h-1).$$

Implicitly, it means that ${\gamma }_i^{(h-1,1)}\left(v\right)={\gamma }_i\left(0\right)\left(v\right)$ for $i\ne h-1$. The subtrees of height $h-1$ that we must add are isomorphic, self-nested and embed all the subtrees of height $h-2$ appearing in $\tau$ by definition of the NEST. In particular, they can be obtained by the allowed inserting operations from the subtrees of height $h-2$ under v, by first adding an internal node to increase their height to $h-1$. In addition, it is less costly in terms of editing operations to construct the subtrees of height $h-1$ from the subtrees of height $h-2$ available under v than to directly add these subtrees under v. If all the subtrees of height $h-2$ under v must be reconstructed later, it will be possible to insert them and the total cost will be same as by directly adding the subtrees of height $h-1$ under v. Consequently, all the available subtrees of height $h-2$ are used to construct subtrees of height $h-1$ under v and it remains

$${\Delta }_{h-1}^{\left(1\right)}=\left({\Delta }_{h-1}^{\left(0\right)}\left(v\right)-{\gamma }_{h-2}^{(h-1,1)}\right)\vee 0$$

subtrees of height $h-1$ to be built under v. Furthermore, in the new version of $\tau$, we have

$${\gamma }_{h-2}^{(h-1,2)}\left(v\right)={\gamma }_{h-2}^{(h-1,1)}\left(v\right)-{\Delta }_{h-1}^{\left(1\right)}\left(v\right).$$

The ${\Delta }_{h-1}^{\left(1\right)}$ subtrees of height $h-1$ can be constructed from subtrees of height $h-3$ (with a larger cost than from subtrees of height $h-2$), and so on. To this aim, we define the sequence of the modified versions of $\tau$ by, for $0\le j\le h-2$,

$$\left\{\begin{array}{ccc}{\Delta }_{h-1}^{(j+1)}\left(v\right)& =& \left({\Delta }_{h-1}^{\left(j\right)}\left(v\right)-{\gamma }_{h-1-(j+1)}^{(h-1,j+1)}\left(v\right)\right)\vee 0,\hfill \\ {\gamma }_{h-(j+2)}^{(h-1,j+2)}\left(v\right)& =& {\gamma }_{h-(j+2)}^{(h-1,j+1)}\left(v\right)-{\Delta }_{h-1}^{(j+1)}\left(v\right).\hfill \end{array}\right.$$

At the final step $j=h-2$, the ${\Delta }_{h-1}^{\left(0\right)}\left(v\right)$ subtrees of height $h-1$ have been constructed from all the available subtrees appearing under v, starting from subtrees of height $h-2$, then $h-3$, etc., and then have been added if necessary.

From now on, the number of subtrees of height $h-2$ under v will not decrease. Indeed, it would mean that an internal node has been added between v and the root of a subtree of height $h-2$. This would have the consequence to increase of one unit the number of subtrees of height $h-1$ in subtrees of height h, which cost is (strictly) larger than adding a subtree of height $h-2$ in all the subtrees of height h. Consequently, we obtain

$${\rho }_{\mathrm{NEST}\left(\tau \right)}(h,h-2)\ge \underset{\{v\in \mathcal{V}(\tau ):\mathcal{H}(\tau \left[v\right])=h\}}{max}{\gamma }_{h-2}^{(h-1,h)}\left(v\right).$$

We can reproduce the above reasoning to construct under v subtrees of height $h-i$, i from 2 to $h-1$, from subtrees with a smaller height, which defines a sequence ${\gamma }_i^{(h-i,j)}$ of modified versions of $\tau$, which size is $h-i+1$, and we get the following inequality,

$$\forall 2\le i\le h,{\rho }_{\mathrm{NEST}\left(\tau \right)}(h,h-i)\ge \underset{\{v\in \mathcal{V}(\tau ):\mathcal{H}(\tau \left[v\right])=h\}}{max}{\gamma }_{h-i}^{(h-i+1,h-i+2)}\left(v\right).$$

(4)

The tree returned by Algorithm 2 is self-nested and its height profile saturates the inequalities (3) and (4) for all the possible values of h and i by construction. In addition, we have shown that this tree can be obtained from $\tau$ by the allowed inserting operations. Since increasing of one unit the height profile at $(h_1,h_2)$ has a (strictly) positive cost, this tree is thus the (unique) NEST of $\tau$. As seen previously, the number of iterations of the while loop at line 7 is the number of subtrees of height $h_2<h_1$ available to construct a tree of height $h_1$, i.e., the degree of $\tau$ in the worst case, which states the complexity.

4.3. NeST Algorithm

This section is devoted to the presentation of the calculation of the NeST in Algorithm 3. An illustrative example that can help the reader to follow the progress of the algorithm is provided in Section 6.

Algorithm 3: Construction of the nearest embedded self-nested tree.

Proposition 7.

For any tree τ, Algorithm 3 returns the unique NeST of τ in $O(\mathcal{H}{\left(\tau \right)}^2)$.

Proof. 

The proof follows the same reasoning as the proof of Proposition 6. First, one may remark that

$${\rho }_{\mathrm{NeST}\left(\tau \right)}(h,h-1)\le min{\rho }_{\tau }(h,h-1),$$

(5)

because the number of subtrees of height $h-1$ under a node v of height h can only decrease by the allowed deleting operations. Let v be a node of height h in $\tau$ and ${\gamma }_i\left(v\right)$ the number of subtrees of height i under v. If a subtree of height $h-i$ under v that must be deleted is not self-nested, one can first modify it to get a self-nested tree and then remove it with the same overall cost. Thus, we can assume without loss of generality that all the subtrees under v are self-nested. ${\Delta }_{h-1}\left(v\right)={\gamma }_{h-1}\left(v\right)-{\rho }_{\mathrm{NeST}\left(\tau \right)}(h,h-1)$ denotes the number of subtrees of height $h-1$ that have to be removed from v. Let ${\gamma }_i^{\left(j\right)}\left(v\right)$ the sequence of the modifications to obtain ${\rho }_{\mathrm{NeST}\left(\tau \right)}(h,h-1)$ subtrees of height $h-1$ under v, with ${\gamma }_i^{\left(0\right)}\left(v\right)={\gamma }_i\left(v\right)$. Instead of deleting a subtree of height $h-1$, it is always less costly to decrease its height of one unit by deleting its root. However it is possible only if this internal node has only one child, i.e., if ${\rho }_{\tau }(h-1,h-2)=1$ and ${\rho }_{\tau }(h-1,i)=0$ for $0\le i<h-2$. If this new tree of height $h-2$ must be deleted in the sequel, it will be done with the same global cost as by directly deleting the subtree of height $h-1$. Consequently,

$$\left\{\begin{array}{ccc}{\gamma }_{h-1}^{\left(1\right)}\left(v\right)& =& {\rho }_{\mathrm{NeST}\left(\tau \right)}(h,h-1),\hfill \\ {\gamma }_{h-2}^{\left(1\right)}\left(v\right)& =& {\gamma }_{h-2}^{\left(0\right)}\left(v\right)+{\Delta }_{h-1}\left(v\right){\mathbb{I}}_{\{{\rho }_{\tau }(h-1,h-2)=1,\forall 3\le i\le h,{\rho }_{\tau }(h-1,h-i)=0\}}.\hfill \end{array}\right.$$

From now on, the number of subtrees of height $h-2$ under v will thus not increase and we obtain

$${\rho }_{\mathrm{NeST}\left(\tau \right)}(h,h-2)\le \underset{\{v\in \mathcal{V}(\tau ):\mathcal{H}(\tau \left[v\right])=h\}}{min}{\gamma }_{h-2}^{\left(1\right)}\left(v\right).$$

There are ${\Delta }_{h-2}\left(v\right)={\gamma }_{h-2}^{\left(1\right)}\left(v\right)-{\rho }_{\mathrm{NeST}\left(\tau \right)}(h,h-2)$ subtrees of height $h-2$ to be deleted under v. We can repeat the previous reasoning and delete the root of subtrees of height $h-2$ if possible rather than delete the whole structure, and so on for any height. Thus, the sequence ${\gamma }_i^{\left(j\right)}$ is defined from

$$\left\{\begin{array}{ccc}{\Delta }_{h-1-i}\left(v\right)& =& {\gamma }_{h-1-i}^{\left(i\right)}\left(v\right)-{\rho }_{\mathrm{NeST}\left(\tau \right)}(h,h-1-i),\hfill \\ {\gamma }_{h-1-i}^{(i+1)}\left(v\right)& =& {\rho }_{\mathrm{NeST}\left(\tau \right)}(h,h-1-i),\hfill \\ {\gamma }_{h-2-i}^{(i+1)}\left(v\right)& =& {\gamma }_{h-2-i}^{\left(i\right)}\left(v\right)+{\Delta }_{h-1-i}\left(v\right){\mathbb{I}}_{\{{\rho }_{\tau }(h-1,h-2)=1,\forall i+2\le j\le h,{\rho }_{\tau }(h-i,h-j)=0\}},\hfill \end{array}\right.$$

and we have

$$\forall 0\le i\le h-2,{\rho }_{\mathrm{NeST}(\tau }(h,h-2-i)\le \underset{\{v\in \mathcal{V}(\tau ):\mathcal{H}(\tau \left[v\right])=h\}}{min}{\gamma }_{h-2-i}^{(i+1)}\left(v\right).$$

(6)

The tree returned by Algorithm 3 saturates the inequalities (5) and (6) for all the possible values of h and i. Decreasing of one unit the height profile at $(h_1,h_2)$ has a (strictly) positive cost. Thus, this tree is the (unique) NeST of $\tau$. The time-complexity is given by the size of the height profile array. □

5. Numerical Illustration

5.1. Random Trees

The aim of this section is to illustrate the behavior of the NEST and of the NeST on a set of simulated random trees regarding both the quality of the approximation and the computation time. We have simulated 3000 random trees of size 10, 20, 30, 40, 50, 75, 100, 150, 200, and 250. For each tree, we have calculated the NEST and the NeST. The number of nodes of these approximations is displayed in Figure 9. We can observe that the number of nodes of the NEST is very large in regards with the size of the initial tree: approximately one thousand nodes on average for a tree of 150 nodes, which is to say an approximation error of 750 vertices. Remarkably, the NEST has never been a better approximation than the NeST on the set of simulated trees.

The computation time required to compute the NEST or the NeST of one tree on a 2.8 GHz Intel Core i7 has also been estimated on the set of simulated trees and is presented in Figure 10. As predicted by the theoretical complexities given in Propositions 6 and 7, the NeST algorithm requires less computation time than the NEST. Consequently, the NeST provides a much better and faster approximation of the initial data than the NEST.

5.2. Structural Analysis of a Rice Panicle

Considering [5], we propose to quantify the degree of self-nestedness of a tree $\tau$ by the following indicator based on the calculation of $\mathrm{NEST}\left(\tau \right)$,

$${\delta }_{\mathrm{NEST}}\left(\tau \right)=1-\frac{D_Z(\mathrm{NEST}\left(\tau \right),\tau )}{\#\mathcal{V}\left(\tau \right)}=\frac{2\#\mathcal{V}\left(\tau \right)-\#\mathcal{V}\left(\mathrm{NEST}\right(\tau \left)\right)}{\#\mathcal{V}\left(\tau \right)},$$

(7)

where $D_Z$ stands for Zhang’s edit distance [11]. In [5] (Equation (6)), the degree of self-nestedness of a plant is defined as in (7) but normalizing by the number of nodes of the NEST and not the size of the initial data, which avoids the indicator to be negative. In the present paper, we prefer normalizing by the number of nodes of $\tau$ to obtain the following comparable self-nestedness measure based on the calculation of $\mathrm{NeST}\left(\tau \right)$,

$${\delta }_{\mathrm{NeST}}\left(\tau \right)=1-\frac{D_Z(\mathrm{NeST}\left(\tau \right),\tau )}{\#\mathcal{V}\left(\tau \right)}=\frac{\#\mathcal{V}\left(\mathrm{NeST}\right(\tau \left)\right)}{\#\mathcal{V}\left(\tau \right)}.$$

The main advantage of this normalization is that if the NEST and the NeST offer equally good approximations, i.e., $D_Z(\mathrm{NEST}\left(\tau \right),\tau )=D_Z(\mathrm{NeST}\left(\tau \right),\tau )$, then the degree of self-nestedness does not depend on the chosen approximation scheme, ${\delta }_{\mathrm{NEST}}\left(\tau \right)={\delta }_{\mathrm{NeST}}\left(\tau \right)$.

We propose to investigate the degree of structural self-similarity of the topological structure of the rice panicle studied in [5] (4.2 Analysis of a Real Plant) through these self-nested approximations. The rice panicle $V_1$ is made of a main axis bearing a main inflorescence $P_1$ and lateral systems $V_i$, $2\le i\le 5$, each composed of inflorescences $P_j$, $2\le j\le 8$ (see Figure 11). We have computed the indicators of self-nestedness ${\delta }_{\mathrm{NEST}}\vee 0$ and ${\delta }_{\mathrm{NeST}}$ for each substructure composing the whole panicle (see Figure 12). The numerical values and the shape of these indicators are similar. However, ${\delta }_{\mathrm{NeST}}$ is always greater than ${\delta }_{\mathrm{NEST}}$, in particular for the largest structures $V_i$. Based on a better approximation procedure as highlighted in the previous section, the NeST better captures the self-nestedness of the rice panicle.

6. Summary and Concluding Remarks

Self-nested trees are unordered rooted trees that are the most compressed by DAG compression. Since DAG compression takes advantage of subtree repetitions, they present the highest level of redundancy in their subtrees. In this paper, we have developed a new algorithm for computing the Nearest Embedding Self-nested Tree (NEST) of a tree $\tau$ in $O(\mathcal{H}{\left(\tau \right)}^2\times \mathcal{D}\left(\tau \right))$, as well as the first algorithm for determining its Nearest embedded Self-nested Tree (NeST) with time-complexity $O(\mathcal{H}{\left(\tau \right)}^2)$.

To this end, we have introduced the notion of height profile of a tree. Roughly speaking, the height profile is a triangular array which component $(h_1,h_2)$, with $h_2<h_1$, is the list of the numbers of direct subtrees of height $h_2$ in subtrees of height $h_1$, where a subtree is said direct if it is attached to the root. We have shown in Proposition 3 that self-nested trees are characterized by their height profile. While the first NEST algorithm [5] was based on edition of the DAG related to the tree to be compressed, the two approximation algorithms developed in the present paper take as input the height profile of any tree $\tau$, which can be computed in $O(\#\mathcal{V}(\tau )\times \mathcal{D}(\tau \left)\right)$-time (see Proposition 2), and modify it from top to bottom and from right to left, to return the self-nested height profile of the expected estimate (see Algorithms 2 and 3). Figure 13 and Figure 14 illustrate the progress of the algorithms on a simple example. They should be examined in relation to the corresponding algorithms. We would like to emphasize that our paper also states the uniqueness of the NEST and of the NeST, and studies the link with edit operations admitted in Zhang’s distance.

Remarkably, estimations performed on a dataset of random trees establish that the NeST is a more accurate approximation of the initial tree than the NEST. This observation could be investigated from a theoretical perspective. In addition, we have shown that the NeST better captures the degree of structural self-similarity of a rice panicle than the NEST.

The algorithms developed in this paper are available in the last version of the Python library treex [9].