0
$\begingroup$

I need to calculate the edit distance between many pairs of binary trees. Unfortunately this is computationally expensive.

The trees are stored as a flattened list of indices into node and terminal lookup tables. The particular flattening structure is the pre-order encoding format (pseudo code: flat(tree) = [id(root)] + flat(left) + flat(right)).

If I calculate the Levenshtein distance between the flattened trees, rather than between trees:

  • How big will my error be? (Difference to tree based distance)
  • Would other flat structures be more accurate?
Improve this question
$\endgroup$
4
  • 1
    $\begingroup$ 1) This looks like pre-order encoding, this does not uniquely describe trees. Am I missing something here? 2) Error compared to what? 3) What have you tried and where did you get stuck? $\endgroup$
    – Raphael
    Commented Oct 13, 2016 at 13:46
  • $\begingroup$ @Raphael Good points. I've updated the question somewhat. How does this encoding not uniquely describe a tree? Each list item is an ID. IDs are stored in the lookup tables. If it's in the terminal table it's a leaf node. If it's in the node table it's binary. (this is a simplification, the lookup table contains the arity of the nodes) $\endgroup$
    – AnnanFay
    Commented Oct 13, 2016 at 14:09
  • $\begingroup$ Consider the pre-order sequence 1 2 .. n. There are $2^{n-1}$ fitting trees from linear chains alone (attach left or right) and many others. $\endgroup$
    – Raphael
    Commented Oct 13, 2016 at 14:57
  • $\begingroup$ @Raphael We know which items are branches however, the 'lookup tables' in my question. Say we have trees = {[1,3,4], [2,3,4], [1,2,3,4,3]}, bins=[1,2], terms=[3,4] where bins tells us which indices represent binary branching and 'terms' indicate leaf nodes. The first two have the same structure but with different roots. The third has two nodes and three terminals. $\endgroup$
    – AnnanFay
    Commented Oct 13, 2016 at 15:06

1 Answer 1

Reset to default
1
$\begingroup$

This approximation is essentially arbitrarily bad.

Suppose you have a complete binary tree $T$ containing $2^k - 1$ nodes, of which the bottom $2^{k-1}$ are leaves. Let $u$ and $v$ be the left and right child of the root, and $U$ and $V$ be the subtrees rooted at these vertices, respectively. Let $w$ be the rightmost leaf in $U$. To transform $T$ into a tree in which the locations of the leaf $w$ and the entire subtree $V$ have been swapped (so that the new tree has height $2k-1$) requires $2^{k-1}-1$ deletions of all nodes in $V$, the deletion of $w$, followed by the same number of insertions -- but the Levenshtein distance between the corresponding strings is just 2: delete the single list element corresponding to $w$ (from just before the half-way point of the string) and append it to the end.

(Well, possibly up to 2 tree-edits can be saved by turning pairs of insertions and deletions into substitutions.)

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.