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?