Affiliations: Department of Artificial Intelligence, Kyushu Institute of Technology, Kawazu 680-4, Iizuka 820-8502, Japan. aratsu@dumbo.ai.kyutech.ac.jp | Department of Artificial Intelligence, Kyushu Institute of Technology, Kawazu 680-4, Iizuka 820-8502, Japan. hirata@ai.kyutech.ac.jp | Computer Center, Gakushuin University, Mejiro 1-5-1, Toshima, Tokyo 171-8588, Japan. ori-JFI@tk.cc.gakushuin.ac.jp
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
