Department of Computer Science
 
Chair V

 
University of Bonn -> Department of Computer Science -> Chair V
CS-Reports 1997 Copyright 1997 University of Bonn, Department of Computer Science, Abt. V
85166

A New Measure of the Distance between Ordered Trees and its Applications
Thorsten Richter
[Download PostScript] [Download PDF]

The problem of computing the distance between two trees T_1 and T_2, also known as tree editing problem, is a generalization of the problem of computing the distance between two strings to labeled ordered trees. One view of the distance between two trees T_1 and T_2 is that of a mapping. A mapping M from T_1 to T_2 is a partial one-to-one map from the nodes of T_1 to the nodes of T_2 that preserves the ancestor relations and the left-to-right ordering of the nodes. In [18] an algorithm is given that computes the distance between two ordered trees T_1 and T_2 in time O(|T_1|*|T_2|*min(DEPTH(T_1), LEAVES(T_1))*min(DEPTH(T_2),LEAVES(T_2))) and in space O(|T_1|*|T_2|). In this paper we define a new measure of the distance between two ordered trees T_1 and T_2 that is based on a restricted kind of mapping which we call structure respecting. In a structure respecting mapping M from T_1 to T_2 for all (v_1, w_1),(v_2, w_2),(v_3, w_3) \in M the additional condition LCA(v_1, v_2) = LCA(v_1, v_3) \Leftrightarrow LCA(w_1, w_2) = LCA(w_1, w_3) holds, so that a structure respecting mapping preserves more of the structure of the trees involved than a general mapping. We then present a simple dynamic programming algorithm that computes a minimum cost structure respecting mapping between two ordered trees T_1 and T_2 in time O(DEGREE(T_1)*DEGREE(T_2)*|T_1|*|T_2|) and in space O(DEGREE(T_1)*DEPTH(T_1)*|T_2|).

Last Change: 08/18/99 at 13:00:38
 Deutsch
University of Bonn -> Department of Computer Science -> Chair V