Ordered Tree Edit Distance with Merge and Split Operations

TR-2003-35, Author: Philip Bille

Philip Bille

September 2003

Abstract

Comparing trees is a fundamental problem in computer science. In particular, the ordered tree edit distance problem, defined as the problem of comparing ordered and labeled trees based on the cost and number of edit operations needed to transform a tree T1 into another tree T2 , arise in many applications. For the simple edit operations of inserting, deleting and relabeling a node the problem is a well-studied problem and algorithms with o(n 4 ) time complexity exists. In this paper we extend the set of operations with merge and split operations. We argue that this new problem naturally generalize the old problem and we provide polynomial time algorithms for solving it.

---

Technical report TR-2003-35 in IT University Technical Report Series, September 2003.

Available as PDF.