著者
阿久津 達也 深川 大路 高須 淳宏
出版者
一般社団法人電子情報通信学会
雑誌
電子情報通信学会技術研究報告. 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>)以下となることを示す。

言及状況

はてなブックマーク (4 users, 4 posts)

収集済み URL リスト