
University of Bonn > Department of Computer Science > Chair V  
CSReports 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 onetoone map from the nodes of T_1 to the nodes of T_2 that preserves the ancestor relations and the lefttoright 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 