| 講演抄録／キーワード |
| 講演名 |
2006-05-24 13:00
木の編集距離の文字列の編集距離による近似
○阿久津達也（京大）・深川大路・高須淳宏（NII） |
| 抄録 |
（和） |
木の類似度の尺度として、木の編集距離が20年以上前に提案され、それ以来、多くの研究が行われてきた。順序木に対する編集距離計算アルゴリズムとしては（入力の木のサイズを$O(n)$として）$O(n^3 \log n)$のものが現時点で最速であるが、文字列の編集距離が$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 / / / / |
| 文献情報 |
信学技報, vol. 106, no. 63, COMP2006-12, pp. 17-24, 2006年5月. |
| 資料番号 |
COMP2006-12 |
| 発行日 |
2006-05-17 (COMP) |
| ISSN |
Print edition: ISSN 0913-5685 |
| PDFダウンロード |
|