Proofs: Zhang-Shasha algorithm

The Zhang-Shasha algorithm computes the tree edit distance full

This proof shows: correctness, termination.

Setting. A forest is an ordered list of ordered rooted trees. For two nodes $u, u'$ of a forest, $u$ is an ancestor of $u'$ if it lies on the path from $u'$ to its root (a node is not its own proper ancestor), and $u$ is to the left of $u'$ if neither is an ancestor of the other and $u$ comes first in postorder. A mapping $M$ between forests $F$ and $G$ is a set of pairs $(v, w) \in F \times G$ in which each node occurs at most once, and such that for all $(v_1, w_1), (v_2, w_2) \in M$: $v_1$ is an ancestor of $v_2$ exactly when $w_1$ is an ancestor of $w_2$, and $v_1$ is to the left of $v_2$ exactly when $w_1$ is to the left of $w_2$. Its cost $\gamma(M)$ is $\sum_{(v, w) \in M} \gamma(v \to w) + \sum_{v \text{ unmapped}} \gamma(v \to \varepsilon) + \sum_{w \text{ unmapped}} \gamma(\varepsilon \to w)$, with non-negative costs. Let $\delta(F, G)$ be the least cost of a mapping; the empty set is a mapping, so $\delta$ is well defined. For a node $v$, $T(v)$ is its subtree; $F - v$ is $F$ with $v$ removed and its children put in its place; $F - T(v)$ is $F$ without the subtree of $v$.

Termination. All loops of lines L3 to L9 have fixed bounds, so the algorithm stops.

Lemma 1 (empty forests). $\delta(\emptyset, \emptyset) = 0$, $\delta(F, \emptyset)$ is the sum of the deletion costs of $F$, and $\delta(\emptyset, G)$ is the sum of the insertion costs of $G$.

Proof. The only mapping with an empty side is the empty mapping. $\square$

Lemma 2 (forest recurrence). Let $F$ and $G$ be non-empty forests with rightmost roots $v$ and $w$. Then

If moreover $F = T(v)$ and $G = T(w)$, then

Proof. Each term is the cost of a mapping (upper bound). A mapping of $F - v$ and $G$ is a mapping of $F$ and $G$ in which $v$ is unmapped: removing $v$ keeps the ancestor and left relations among the other nodes. So $\delta(F, G) \le \delta(F - v, G) + \gamma(v \to \varepsilon)$, and the same for $w$. Let $M_1$ be a mapping of $F - T(v)$ and $G - T(w)$ and $M_2$ a mapping of $T(v)$ and $T(w)$. Every node of $F - T(v)$ is to the left of every node of $T(v)$, because $v$ is the rightmost root, and the same holds in $G$. So $M_1 \cup M_2$ keeps both relations, and its cost is the sum of the two costs. In the tree case, a mapping $M_2'$ of $T(v) - v$ and $T(w) - w$ together with the pair $(v, w)$ is a mapping: $v$ and $w$ are ancestors of all other nodes of their trees.

An optimal mapping has one of these forms (lower bound). Let $M$ be a mapping of least cost. If $v$ is unmapped, $M$ is a mapping of $F - v$ and $G$ with $\gamma(M) = \gamma(M \text{ on } F - v) + \gamma(v \to \varepsilon)$, so $\delta(F, G) \ge$ the first term. The same holds if $w$ is unmapped. Otherwise $(v, w') \in M$ and $(v', w) \in M$ for some $w'$, $v'$. Suppose $w' \ne w$. Then $v' \ne v$. As $v$ is the rightmost root, $v'$ is either a descendant of $v$ or to the left of $v$. If $v'$ is a descendant of $v$, then $w'$ is an ancestor of $w$, which is impossible since $w$ is a root. If $v'$ is to the left of $v$, then $w$ is to the left of $w'$, so $w$ comes before $w'$ in postorder. This is impossible, since $w$ is the rightmost root and so the last node of $G$ in postorder. So $(v, w) \in M$. Now a pair $(x, y) \in M$ with $x \in T(v)$, $x \ne v$, has $v$ as an ancestor of $x$, so $w$ is an ancestor of $y$ and $y \in T(w)$; symmetrically for $y \in T(w)$. So $M$ splits into $M_1$ on $F - T(v)$ and $G - T(w)$ and $M_2$ on $T(v)$ and $T(w)$, with $(v, w) \in M_2$, and $\gamma(M) = \gamma(M_1) + \gamma(M_2) \ge \delta(F - T(v), G - T(w)) + \delta(T(v), T(w))$. In the tree case, $F - T(v)$ and $G - T(w)$ are empty, and $M_2 \setminus \{(v, w)\}$ is a mapping of $T(v) - v$ and $T(w) - w$, so $\gamma(M) \ge \delta(T(v) - v, T(w) - w) + \gamma(v \to w)$. $\square$

Postorder intervals. Number each tree $1, \ldots, n$ in postorder and let $l(i)$ be the leftmost leaf of $T(i)$. The subtree $T(i)$ is the interval $[l(i), i]$. For $l(i) \le i_1 \le i$, the nodes $l(i), \ldots, i_1$ form a forest $T[l(i)..i_1]$ whose rightmost root is $i_1$; removing $i_1$ gives $T[l(i)..i_1 - 1]$, and removing $T(i_1)$ gives $T[l(i)..l(i_1) - 1]$, where an interval with its end below its start is the empty forest. If $l(i_1) = l(i)$, then $T[l(i)..i_1] = T(i_1)$.

Lemma 3 (the table). Fix a pair of keyroots $(i, j)$ handled at lines L5 to L13, and assume that every entry $\mathit{td}[i_1][j_1]$ read at line L13 already holds $\delta(T_1(i_1), T_2(j_1))$. Then after the pair, $\mathit{fd}[i_1][j_1] = \delta(T_1[l_1(i)..i_1], T_2[l_2(j)..j_1])$ for all $l_1(i) - 1 \le i_1 \le i$ and $l_2(j) - 1 \le j_1 \le j$, and line L12 sets $\mathit{td}[i_1][j_1] = \delta(T_1(i_1), T_2(j_1))$ for every $i_1$ with $l_1(i_1) = l_1(i)$ and $j_1$ with $l_2(j_1) = l_2(j)$.

Proof. Lines L5 to L7 fill the row and the column of the empty forests, correctly by Lemma 1. The loops of lines L8 and L9 go through the other entries row by row. Each read entry has a smaller row, or the same row and a smaller column, or the row $l_1(i_1) - 1 < i_1$ and the column $l_2(j_1) - 1 < j_1$, and all these indices are at least $l_1(i) - 1$ and $l_2(j) - 1$, since $l(i_1) \ge l(i)$ for $i_1$ in $T(i)$. So each read entry was written earlier in this pair. By the postorder intervals, line L11 is the tree case of Lemma 2 and line L13 is its forest case, with the assumed values of $\mathit{td}$. Line L12 copies a value that, in the tree case, is $\delta(T_1(i_1), T_2(j_1))$. $\square$

Lemma 4 (order of the keyroots). For each node $i_1$, let $k(i_1)$ be the highest node with the leftmost leaf $l(i_1)$. Then $k(i_1)$ is a keyroot, $l(i_1) \le i_1 \le k(i_1)$, and $\mathit{td}[i_1][j_1]$ is written at line L12 during the pair $(k_1(i_1), k_2(j_1))$. If $i_1$ lies in $T_1(i)$ and $l_1(i_1) \ne l_1(i)$, then $k_1(i_1) < i$; if $l_1(i_1) = l_1(i)$ for a keyroot $i$, then $k_1(i_1) = i$. The same holds in $T_2$.

Proof. The nodes with the leftmost leaf $l(i_1)$ form a path upward from that leaf, and $k(i_1)$ is the top of this path, so no later node has the same leftmost leaf: it is a keyroot, and $i_1$ is on the path, so $i_1 \le k(i_1)$. In the pair $(k_1(i_1), k_2(j_1))$, $i_1$ and $j_1$ satisfy the test of line L10, so line L12 writes $\mathit{td}[i_1][j_1]$. If $i$ is a keyroot and $l(i_1) = l(i)$, both are on the same path, whose top is $i$. If $i_1 \in T(i)$ and $l(i_1) \ne l(i)$, the path of $l(i_1)$ is inside $T(i)$ and does not reach $i$, so its top is a proper descendant of $i$, and comes before $i$ in postorder. $\square$

Theorem. ZHANG-SHASHA returns $\delta(T_1, T_2)$.

Proof. Process the pairs of keyroots in the order of lines L3 and L4: by increasing $i$, and for each $i$ by increasing $j$. We show by induction over this order that the assumption of Lemma 3 holds for each pair. At line L13 for the pair $(i, j)$, $i_1$ and $j_1$ do not both have the leftmost leaves of $i$ and $j$. By Lemma 4, $\mathit{td}[i_1][j_1]$ was written in the pair $(k_1(i_1), k_2(j_1))$, where either $k_1(i_1) < i$, or $k_1(i_1) = i$ and $k_2(j_1) < j$. In both cases this pair comes earlier, and by the induction hypothesis and Lemma 3 the value written there is $\delta(T_1(i_1), T_2(j_1))$. Later pairs may overwrite $\mathit{td}[i_1][j_1]$ only with the same value, by Lemma 3 again. So Lemma 3 applies to every pair. The roots $n_1$ and $n_2$ are keyroots with $l(n_t) = 1$, and the last pair $(n_1, n_2)$ writes $\mathit{td}[n_1][n_2] = \delta(T_1, T_2)$ at line L12, which line L14 returns. $\blacksquare$