4
$\begingroup$

I am trying to solve a problem of finding a max repetitive sub-tree in an object tree.

By the object tree I mean a tree where each leaf and node has a name. Each leaf has a type and a value of that type associated with that leaf. Each node has a set of leaves / nodes in certain order.

Given an arbitrary object tree that - we know - has a repetitive sub-tree in it.

By repetitive I mean 2 or more sub-trees that are similar in everything (names/types/order of sub-elements) but the values of leaves. No nodes/leaves can be shared between sub-trees.

Problem is to identify these sub-trees of the max height.

I know that the exhaustive search can do the trick. I am rather looking for more efficient approach.

$\endgroup$
4
$\begingroup$

For each non-leaf node in the tree make a hash of its names/order and of the hashes of its ordered sub-nodes. If a node is a leaf then its hash is its name/type. This gives an O(N) algorithm to get all the heights and subtree hashes. Next you can traverse the tree in order of decreasing height until you find a hash that matches one you've seen earlier -- this is your target match. So the whole algorithm is O(N).

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ Nice, that should work. I am not marking it as answered hoping to get more ideas. $\endgroup$ – Trident D'Gao Sep 4 '12 at 17:51
  • $\begingroup$ I'd mark this as answered. Hashing is pretty clearly the optimal choice. Are there any particular qualities you'd like out of a different algorithm? $\endgroup$ – Geoffrey Irving Sep 5 '12 at 1:22
  • $\begingroup$ @GeoffreyIrving, done. Yes I do, but the problem is put slightly differently and a hash wouldn't really work there. Let me explain. What I really need is not a 100% match (where a hash would work perfectly), but to find a max sub-set of elements 2 different nodes have in common. To avoid the specifics, I have a comparison function that for 2 given nodes gets a number from 0 to 1 which represent the similarity between 2 nodes. The implementation of that function is unknown. Nodes are considered similar if this number is over some threshold. $\endgroup$ – Trident D'Gao Sep 12 '12 at 14:28
  • $\begingroup$ If the details of the comparison function are unknown, I believe there's no way to beat quadratic time in the number of trees. $\endgroup$ – Geoffrey Irving Sep 12 '12 at 16:27

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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