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

被引：5

作者：

Aratsu, Taku

Hirata, Kouichi

Kuboyama, Tetsuji

机构：

[1] Dep. of Art. Intel., Kyushu Institute of Technology, Iizuka 820-8502

[2] Computer Center, Gakushuin University, Toshima, Tokyo 171-8588

[3] IBM Japan, Co. Ltd.

来源：

FUNDAMENTA INFORMATICAE | 2010年 / 101卷 / 03期

关键词：

tree edit distance; string edit distance; binary tree code; binary tree representation;

D O I：

10.3233/FI-2010-282

中图分类号：

TP31 [计算机软件];

学科分类号：

081202 ; 0835 ;

摘要：

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.

引用

页码：157 / 171

页数：15

共 12 条

[1] A relation between edit distance for ordered trees and edit distance for Euler strings [J].