search

JoaoFelipe / apted

Python APTED algorithm for the Tree Edit Distance
MIT License
86 stars 13 forks source link

Is the distance correct? #9

Open dkajtoch opened 2 months ago

dkajtoch commented 2 months ago

I have the following two trees:

tree1 = "{t{tr{td}{td}}{tr{td}{td}{td}}{tr{td}{td}{td}}{tr{td}{td}{td}}{tr{td}{td}{td}}{tr{td}{td}{td}}{tr{td}{td}{td}}{tr{td}{td}{td}}{tr{td}{td}{td}}{tr{td}{td}{td}}{tr{td}{td}{td}}}"
 tree2 = "{t{tr{td}{td}{td}{td}{td}{td}}{tr{td}{td}{td}{td}{td}{td}}{tr{td}{td}{td}{td}{td}{td}}{tr{td}{td}{td}{td}{td}{td}}{tr{td}{td}{td}{td}{td}{td}}}"

tree1 = Tree.from_text(tree1)
tree2 = Tree.from_text(tree2)
apted = APTED(tree1, tree2)
dist = apted.compute_edit_distance()

The distance between them is 18 according to the apted library. If I introduce the rename cost of 1, then the distance jumps to 49. I am not sure if this is correct since the normalization factor max(number_of_nodes_tree1, number_of_nodes_tree2) is 44, so the normalized tree distance would be > 1.0. Can anyone confirm that?

I am using apted==1.0.3 and python==3.10.14