木の編集距離の文字列の編集距離による近似 Approximating Tree Edit Distance Through String Edit Distance

この論文をさがす

著者

抄録

木の類似度の尺度として、木の編集距離が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.

収録刊行物

  • 電子情報通信学会技術研究報告. COMP, コンピュテーション

    電子情報通信学会技術研究報告. COMP, コンピュテーション 106(63), 17-24, 2006-05-17

    一般社団法人電子情報通信学会

参考文献:  15件中 1-15件 を表示

各種コード

  • NII論文ID(NAID)
    110004741451
  • NII書誌ID(NCID)
    AN10013152
  • 本文言語コード
    ENG
  • 資料種別
    ART
  • ISSN
    09135685
  • NDL 記事登録ID
    7938587
  • NDL 雑誌分類
    ZN33(科学技術--電気工学・電気機械工業--電子工学・電気通信)
  • NDL 請求記号
    Z16-940
  • データ提供元
    CJP書誌  NDL  NII-ELS 
ページトップへ