Paul said:
I am looking for an (efficient) implementation of an algorithm for
heirarchical tree comparison.
Very difficult in the general case. As far as I know this is still an open
research topic.
If you can restrict the problem a bit then you can convert it into a linear
diffing problem. Linear diffing is the subject of a /huge/ amount of research
(partly because the CS and genetics communities have tended to duplicate each
others efforts). I could point you at some of the papers, but it sounds as if
you are just looking for a ready-made implementation -- and there are quite a
few which are easy to find on the net.
If you can restrict it so that the children of each node have a fixed order
(alphabetical, say), and you don't want to consider the possibility that a node
may have moved from one subtree to another, then you can use a linear diff,
recursing into each sub-tree. Another way would be to linearise the entire
trees into a specific order, and then just do a big diff on the linear
representation. If you do that then you could choose to take the depth into
account, or to ignore it for these purposes.
-- chris
