Approximating Tree Edit Distance through String Edit Distance for Binary Tree Codes

作者：Aratsu Taku; Hirata Kouichi^*; Kuboyama Tetsuji

来源：Fundamenta Informaticae, 2010, 101(3): 157-171.

DOI：10.3233/FI-2010-282

• tree edit distance
• string edit distance
• binary tree code
• binary tree representation

This article proposes an approximation of the tree edit distance through the string edit distance for binary tree codes, instead of for Euler strings introduced by Akutsu (2006). Here, a binary tree code is a string obtained by traversing a binary tree representation with two kinds of dummy nodes of a tree in preorder. Then, we show that sigma/2 <= tau <= (h + 1)sigma + h, where tau is the tree edit distance between trees, and sigma is the string edit distance between their binary tree codes and h is the minimum height of the trees.

• 出版日期2010