| 講演名 | 2006-05-24 木の編集距離の文字列の編集距離による近似 阿久津 達也, 深川 大路, 高須 淳宏, |
|---|---|
| PDFダウンロードページ |  PDFダウンロードページへ |
| 抄録(和) | 木の類似度の尺度として、木の編集距離が20年以上前に提案され、それ以来、多くの研究が行われてきた。順序木に対する編集距離計算アルゴリズムとしては(入力の木のサイズをO(n)として)O(n^3 logn)のものが現時点で最速であるが、文字列の編集距離がO(n^2)時間で計算できることが知られている。そこで本研究では、木を文字列に変換して文字列の編集距離を計算することにより、木の編集距離を近似する方法を提案する。そして、入力される木の次数が限定されており、かつ、編集操作には単位コストがかかるという場合には、木の編集距離が変換後の文字列の編集距離の1/6以上かつ、O(n^<3/4>)以下となることを示す。 |
| 抄録(英) | We present a method to transform an ordered and rooted tree of bounded degree into a string, where it is done by computing the Euler string of the tree with slight modifications. We show that the edit distance between trees is at least 1/6 and at most O(n^<3/4>) of the edit distance between the transformed strings, where we consider unit cost edit operations and n is the maximum size of two input trees. |
| キーワード(和) | 編集距離 / 順序木 / オイラー文字列 / 近似アルゴリズム / 埋め込み |
| キーワード(英) | tree edit distance / approximation / embedding / Euler string |
| 資料番号 | COMP2006-12 |
| 発行日 |
| 研究会情報 | |
| 研究会 | COMP |
|---|---|
| 開催期間 | 2006/5/17(から1日開催) |
| 開催地（和） | |
| 開催地（英） | |
| テーマ（和） | |
| テーマ（英） | |
| 委員長氏名（和） | |
| 委員長氏名（英） | |
| 副委員長氏名（和） | |
| 副委員長氏名（英） | |
| 幹事氏名（和） | |
| 幹事氏名（英） | |
| 幹事補佐氏名（和） | |
| 幹事補佐氏名（英） | |
| 講演論文情報詳細 | |
| 申込み研究会 | Theoretical Foundations of Computing (COMP) |
|---|---|
| 本文の言語 | ENG |
| タイトル（和） | 木の編集距離の文字列の編集距離による近似 |
| サブタイトル（和） | |
| タイトル（英） | Approximating Tree Edit Distance Through String Edit Distance |
| サブタイトル（和） | |
| キーワード(1)（和/英） | 編集距離 / tree edit distance |
| キーワード(2)（和/英） | 順序木 / approximation |
| キーワード(3)（和/英） | オイラー文字列 / embedding |
| キーワード(4)（和/英） | 近似アルゴリズム / Euler string |
| キーワード(5)（和/英） | 埋め込み |
| 第 1 著者 氏名（和/英） | 阿久津 達也 / Tatsuya AKUTSU |
| 第 1 著者 所属（和/英） | 京都大学 化学研究所バイオインフォマティクスセンター Bioinformatics Center, Institute for Chemical Research, Kyoto University |
| 第 2 著者 氏名（和/英） | 深川 大路 / Daiji FUKAGAWA |
| 第 2 著者 所属（和/英） | 国立情報学研究所 National Institute of Informatics |
| 第 3 著者 氏名（和/英） | 高須 淳宏 / Atsuhiro TAKASU |
| 第 3 著者 所属（和/英） | 国立情報学研究所 National Institute of Informatics |
| 発表年月日 | 2006-05-24 |
| 資料番号 | COMP2006-12 |
| 巻番号（vol） | vol.106 |
| 号番号（no） | 63 |
| ページ範囲 | pp.- |
| ページ数 | 8 |
| 発行日 | |