The q-Gram Distance for Ordered Unlabeled Trees

摘要

In this paper, we investigate the q-Gram distance for ordered unlabeled trees (trees, for short). First, we formulate a q-gram as simply a tree with q nodes isomorphic to a line graph, and the q-gram distance between two trees as similar as one between two strings. Then, by using the depth sequence based on postorder, we design the algorithm EnumGram to enumerate all q-grams in a tree T with n nodes which runs in O(n~2) time and in O(q) space. Furthermore, we improve it to the algorithm LinearEnumGram which runs in O(qn) time and in O(qd) space, where d is the depth of T. Hence, we can evaluate the q-gram distance D_q(T_1,T_2) between T_1 and T_2 in O(q max {n_1, n_2}) time and in O(q max {d_1, d_2}) space, where n_i and d_i are the number of nodes in T_i and the depth of T_i, respectively. Finally, we show the relationship between the q-gram distance D_q(T_1, T_2) and the edit distance E(T_1, T_2) that D_q(T_1, T_2) ≤ (gl + 1) E(T_1, T_2), where g = max{g_1, g_2}, l = max{l_1, l_2}, g_i is the degree of T_i and l_i is the number of leaves in T_i. In particular, for the top-down tree edit distance F(T_1, T_2), this result implies that D_q(T_1, T_2) ≤ min{g~(q-2), l - 1} F(T_1,T_2).