Affiliations: Department of Artificial Intelligence, Kyushu Institute of Technology, Kawazu 680-4, Iizuka 820-8502, Japan. [email protected] | Department of Artificial Intelligence, Kyushu Institute of Technology, Kawazu 680-4, Iizuka 820-8502, Japan. [email protected] | Computer Center, Gakushuin University, Mejiro 1-5-1, Toshima, Tokyo 171-8588, Japan. [email protected]
Note: [] Address for correspondence: Dep. of Art. Intel., Kyushu Institute of Technology, Kawazu 680-4, Iizuka 820-8502. Japan
Abstract: 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 σ/2 ≤ τ ≤ (h + 1)σ + h, where τ is the tree edit distance between trees, and σ is the string edit distance between their binary tree codes and h is the minimum height of the trees.
Keywords: tree edit distance, string edit distance, binary tree code, binary tree representation
