- 著者
-
阿久津 達也
深川 大路
高須 淳宏
- 出版者
- 一般社団法人電子情報通信学会
- 雑誌
- 電子情報通信学会技術研究報告. COMP, コンピュテーション (ISSN:09135685)
- 巻号頁・発行日
- vol.106, no.63, pp.17-24, 2006-05-17
木の類似度の尺度として、木の編集距離が20年以上前に提案され、それ以来、多くの研究が行われてきた。順序木に対する編集距離計算アルゴリズムとしては(入力の木のサイズをO(n)として)O(n^3 logn)のものが現時点で最速であるが、文字列の編集距離がO(n^2)時間で計算できることが知られている。そこで本研究では、木を文字列に変換して文字列の編集距離を計算することにより、木の編集距離を近似する方法を提案する。そして、入力される木の次数が限定されており、かつ、編集操作には単位コストがかかるという場合には、木の編集距離が変換後の文字列の編集距離の1/6以上かつ、O(n^<3/4>)以下となることを示す。