Wyniki wyszukiwania - BazTech

Ograniczanie wyników

2 Fundamenta Informaticae

Znaleziono wyników: 2

Liczba wyników na stronie

Wyniki wyszukiwania

Wyszukiwano:
w słowach kluczowych: tree edit distance

Sortuj według:

Ogranicz wyniki do:

Segmental Mapping and Distance for Rooted Labeled Ordered Trees

Kan T., Higuchi S., Hirata K.

Fundamenta Informaticae

2014

Vol. 132, nr 4

461--483

In this paper, as variations of a Tai mapping between rooted labeled ordered trees (trees, for short), we introduce a segmentalmapping to preserve the parent-children relationship as possible, and also top-down segmengal and bottom-up segmental mappings as the segmental mappings that contain the pair of the roots and the pair of the leaves, respectively. Then, we show that these mappings provide a new hierarchy for the variations of the Tai mapping in addition to a well-known one, in particular, the top-down segmental mapping coincides with a top-down mapping. Also we show that both segmental and bottom-up segmental distances as the minimumcosts of segmental and bottom-up segmental mappings are metrics. Next, we design algorithms to compute the segmental and the bottom-up segmental distances in quadratic time and space. Finally, we give experimental results for the segmental distance.

Approximating Tree Edit Distance through String Edit Distance for Binary Tree Codes

Aratsu T., Hirata K., Kuboyama T.

Fundamenta Informaticae

2010

Vol. 101, nr 3

157-171

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.