根付きラベル付きキャタピラの編集距離の計算

根付きラベル付きキャタピラの編集距離の計算

Computing Edit Distance between Rooted Labeled Caterpillars

村家 康平

1∗

_{芳野 拓也}

2

_{平田 耕一}

2

Kohei Muraka

1

_{Takuya Yoshino}

2

_{Kouichi Hirata}

2

1

_{九州工業大学大学院 情報工学府}

1

_{Graduate School of Computer Science and Systems Engineering,}

Kyushu Institute of Technology

2

_{九州工業大学大学院 情報工学研究院}

2

_{Department of Artificial Intelligence, Kyushu Institute of Technology}

Abstract: A rooted labeled caterpillar is a rooted labeled tree transformed to a path after removing all the leaves in it. In this paper, we design the algorithm to compute the edit distance between rooted labeled caterpillars in O(σh2_{) time, where σ is the number of labels and h is the}

maximum height of two caterpillars.

1

はじめに

ウェブマイニングにおける HTML や XML データや, バイオインフォマティクスにおけるにおける RNA や 糖鎖データといった木構造データの比較はデータマイ ニングにおいて重要である. 根付きラベル付き無順序 木 (以後, 単に木という) の距離計算で最も有名な距離 として木編集距離 [5] がある. 編集距離は, ノードのラ ベルの置換, ノードの削除, ノードの挿入の 3 つの編集 操作を用いて, 一方の木から他方の木へ変換する最小コ ストとして定義される. また, 編集距離はメトリックで あり, Tai マッピング [5] の最小コストと対応する. しかし, 木同士の編集距離計算問題は MAX SNP 困 難である [6]. これは木が二分木や, 木の高さの最大値 が高々3 であっても成り立つ [1, 3]. キャタピラとは, 木からすべての葉を取り除くと 1 本 のパスになる木である. キャタピラは, 非常に制限され た単純な木であるが, 表 1 のように実データ中に多く存 在している. 一方, キャタピラは無順序木であるので, キャタピラの編集距離が多項式時間で計算できるか否 か解明されていない. 本論文では, キャタピラの編集距離を計算するアルゴ リズムを設計する. このアルゴリズムは, キャタピラの 次のような性質を利用する. キャタピラの内部ノード の子は, 高々1 つのキャタピラと葉の集合から構成され ているため, 内部ノードを削除すると, 高々1 つのキャ タピラと葉の集合を得ることができる. また, そのよう ∗_{連絡先： 九州工業大学大学院 情報工学府}        820-8502 福岡県飯塚市川津 680-4        E-mail:[email protected] にして得られた葉に対して, それ以前に分解された際 に得られた葉の集合を加えることができる. このアル ゴリズムの計算時間は, 比較するキャタピラの高さの最 大値を h, キャタピラに出現するラベル数を σ としたと き, O(σh2_{) 時間となる.}

2

キャタピラと木編集距離

閉路を持たない連結無向グラフを木という. ノード の集合 V と辺の集合 E からなる木 T = (V, E) に対し て, V を V (T ), E を V (E) とし, v∈ V を v ∈ V (T ) と する. また, 空の木 (∅, ∅) を ∅ と表す. 木 T からノード r を根として選んだ木を根付き木とし, その根付き木 T の根を r(T ) とする. 木を r = r(T ) となる根付き木といい, u, v, w∈ T と する. v1 = r, vk = v かつ, i(1 ≤ i ≤ k − 1) である (vi, vi+1)∈ E′ となる木 (V′, E′) において, r から v に 対するパスを U Pr(v) とする. par(v) を v(̸= r) の親と したとき, そのノードは U Pr(v) と隣接しており, v(̸= r) の先祖は U Pr(v)−{v} 上のノードである. u, v ∈ V (T ) において, par(u) = v で u と v が隣接しているとき, v を u の親といい, u を v の子という. また, ノードの子 の数を次数といい, d(v) で表す. このとき, 木 T の次数 を, d(T ) = max{d(v) | v ∈ T } と定義する. 子を持た ないノードを葉といい lv(T ) とする. ノード v の高さ を h(v) = max{|UPr(w)| | w ∈ lv(T [v])} とする. この とき, 木 T の高さを h(T ) = max{h(v) | v ∈ T } と定義 する. 根付き木の先祖子孫関係を <,≤ を用いて表す. つま 人工知能学会研究会資料 SIG-FPAI-B801-03

り, v が u の先祖であるとき u < v とし, u < v かつ u = v のとき u≤ v とする. u ≤ w, v ≤ w かつ w′ ≤ w, u≤ w′, v≤ w′となる w′∈ T が存在しないとき, w を u と v の最近共通先祖といい, u⊔ v と表す. 木 T を根付き木 (V, E) とし, v∈ T とする. v を根と する完全部分木 T を, r(T′) = v, V′={u ∈ V | u ≤ v} かつ E′ ={(u, w) ∈ E | u, w ∈ V′} である根付き木 T′= (V′, E′) とし, T [v] と表す.

先行順 pre において, pre(u)≤ pre(v) であり, かつ

後項順 post において, post(u)≤ post(v) のとき, u は v

の左側に存在するという. 子ノード間に上記のような 順序関係が存在する木のことを順序木といい, 子ノード 間にそのような順序関係が存在しないものを無順序木 という. また, 各ノードがアルファベット Σ によってラ ベル付けされている木をラベル付き木といい, ノード v のラベルを l(v) と表す. 本論文では, 根付きラベル付 き無順序木を単に木といい, 木の集合を森という. 木の変種として根付きラベル付きキャタピラ (以後, 単にキャタピラという) を以下のように定義する. 定義 1 (キャタピラ ([2])) 全ての葉を取り除くと一本 のパスになる木をキャタピラ (caterpillar) という. キ ャタピラ C において, 葉を削除して残ったパスを背骨 (backbone) といい, bb(C) と表す. キャタピラは, 非常に制限されたデータであるが, 実 データ中に多く存在している. 表 1 は, KEGG1 _から

提供されている N-glycans と all glycans, CSLOGS2_,

dblp3, および, UW XML Repository4から提供されて いる SwissProt, TPC-H, Auction, University, Protain, Nasa データ中に含まれているキャタピラの数を表して おり, #cat はキャタピラの数, #data は木のデータ数で ある. また, D∈ {Auction, University, Protein, Nasa}

に対して, D− _{で, D の任意の木に対して根ノードを削} 除することによって得られる木の集合を表す. D− で は D 中の 1 つの木から複数の木が生成されるため, D− の#data は D の#data によりも大きくなる. 次に, 編集距離と Tai マッピングについて導入する. 定義 2 (編集操作 [5]) 以下の 3 つの操作を木 T におけ る編集操作という. 1) 置換 (v7→ w): v ∈ T のラベルを w に変える. 2) 削除 (v7→ ε): v ∈ T を削除し, v のすべての子を v の親 v′に連結する.

1_{Kyoto Encyclopedia of Genes and Genomes,}

http://www.kegg.jp/ 2 http://www.cs.rpi.edu/˜zaki/www-new/pmwiki.php/Software/Software 3_{http://dblp.uni-trier.de/} 4_{http://aiweb.cs.washington.edu/research/projects/xmltk/} xmldata/www/repository.html 表 1: 各データにおけるキャタピラの本数

dataset #cat #data %

N-glycans 514 2,141 23.996 all glycans 8,005 10,704 74.785 CSLOGS 41,592 59,691 69.679 dblp 5,154,295 5,154,530 99.995 SwissProt 6,804 50,000 13.608 YPC-H 86,805 86,805 100.000 Auction 0 37 0 University 0 6,738 0 Protein 0 262,625 0 Nasa 0 2,340 0 Auction− 259 259 100.000 University− 74,638 79,213 94.224 Protein− 1,874,703 2,204,068 85.057 Nasa− 21,245 27,921 76.089 3) 挿入 (ε7→ w): ノード v に v′ の子の部分列を連結 し, v を v′に連結する. 置換 (v7→ w) v 7→ w 削除 (v 7→ ε) v′ v 7→ v′ 挿入 (ε7→ v) v′ 7→ v′ v 図 1: 編集操作. ε∈ Σ とし, Σε= Σ∪{ε} とする. このとき, (l1, l2)∈ (Σε× Σε− {(ε, ε)} において, 各編集操作を (l1 7→ l2) と表す. l1̸= ε かつ l2̸= ε のときは置換であり, l2= ε のときは削除, l1= ε のときは挿入である. また, ノー ド v と w において, (l(v)7→ l(w)) を (v 7→ w) とする. ここで, γ : (Σε×Σε\{(ε, ε)} 7→ R+を 2 つのラベル間 のコスト関数とするとき, 編集操作 (l1, l2) のコストを γ(l1, l2) と表す. 特に断らない限り, コスト γ はメトリッ クとする. すなわち, γ(l1, l2)≥ 0, γ(l1, l2) = 0⇔ l1= l2, γ(l1, l2) = γ(l2, l1), γ(l1, l3) ≤ γ(l1, l2) + γ(l2, l3) が成り立つ.

定義 3 (編集距離 [5]) 木 T1から T2 への編集操作列 E = e1, e2, ..., enのコストを γ(E) = ∑n i=1γ(ei) とす るとき, 木 T1と T2との編集距離 τTai(T1, T2) を以下の ように定義する. τ_Tai(T1, T2) = min { γ(E)    E は T1から T2への 編集操作列 } . 定義 4 (Tai マッピング [5]) T1と T2を木とする. M ⊆ V (T1)×V (T1) かつ任意の (v1, w1), (v2, w2)∈ M が以下の条件を満たすとき, (M, T1, T2) を Tai マッピン グ ( 以後, 単にマッピング ) といい , M ∈ MTai(T1, T2) と表す. 1) v1= v2かつ w1= w2(一対一対応). 2) v1≤ v2かつ w1≤ w2(先祖子孫関係の保存). 以後, M ∈ MTai(T1, T2) によって混同することがない とき, (M, T1, T2) を単に M とする. M を T1から T2へのマッピングとする. また, M に は含まれていない T1と T2のノードの組みを IM, JM とする. つまり, IM ={v ∈ T1 | (v, w) /∈ M}, JM = {w ∈ T2| (v, w) /∈ M} である. このとき, M のコスト γ(M ) を以下のように定義する. γ(M ) = ∑ (v,w)∈M γ(v, w) + ∑ v∈IM γ(v, ε) + ∑ w∈JM γ(ε, w). IM = JM = ∅ かつ γ(M) = 0 であるマッピング M ∈ M_Tai(T1, T2) が存在するとき, T1と T2は同型で あるという. 定理 1 (Tai [5]) 木 T1と T2に対して以下が成り立つ.

τ_Tai(T1, T2) = min{γ(M) | M ∈ MTai(T1, T2)}.

しかし, 残念ながら τ_Tai(T1, T2) の計算問題に対して以 下の定理が知られている. 定理 2 ([1, 3, 6]) T1と T2を木とする. このとき, τ_Tai(T1, T2) を計算する問題は MAX SNP 困難である. これは, 2 つの木の最大次数が 2 のとき, もしくは, 最 大高さが 3 のときも成り立つ.

3

キャタピラの編集距離計算

キャタピラ C に出現するすべての森は, 根から bb(C) に含まれるある内部ノードまでのパスの削除, もしくは bb(C) の完全部分木に含まれている. したがって, キャ タピラ C は, li(1≤ i ≤ k) を葉, C を葉のないキャタ ピラとしたときに,{C}, {l1, ..., lk}, {l1, ..., lk, C} のい v C[v℄ B(v) v C[v℄ L(v) v C[v℄ L(v) B(v) 図 2: キャタピラ C[v] の表現. ずれかの形となる. L ={l1, ..., lk} とするとき, Prolog のリスト表記を用いて, 上記の森をそれぞれ⟨∅ | C⟩, ⟨L | ∅⟩, ⟨L | C⟩ と表す. 特に, 空の森 ⟨∅ | ∅⟩ を単に Φ と表す. C[v] を, v を根とするキャタピラとする. ここで, L(v) を v の子の葉の集合 (空集合も含む) とし, B(v) を v の 子の高々1 つのキャタピラとする. このとき, C[v] は図 2 のうちの 1 つの形となる. さらに, C[v] から v を削除 することによって,⟨∅ | B(v)⟩, ⟨L(v) | ∅⟩, ⟨L(v) | B(v)⟩ のうちの 1 つの森を得ることができる. 図 3 は, C1[v] と C2[w] との編集距離 τTai(C1[v], C2[w]) を δTai(⟨∅|C1[v]⟩, ⟨∅|C2[w]⟩) として計算する再帰式で ある. (A) δ_Tai(⟨L1|C1⟩, Φ) = ∑ v∈L1 γ(v, ε) + ∑ v∈C1 γ(v, ε). δ_Tai(Φ,⟨L2|C2⟩) = ∑ w∈L2 γ(ε, w) + ∑ w∈C2 γ(ε, w). (B) δ_Tai(⟨L1|∅⟩, ⟨L2|∅⟩) = τ_Tai(r(L1), r(L2)). (C) δ_Tai(⟨L1|∅⟩, ⟨L2|C2[w]⟩) = min      γ(ε, w) +δ_Tai(⟨L1|∅⟩, ⟨L2∪ L2(w)|B2(w)⟩), (1) min v∈L1 {γ(v, w) + δTai(⟨L1\ {v}|∅⟩, ⟨L2|∅⟩)} +δ_Tai(Φ,⟨L2(w)|B2(w)⟩) (2)     . (D) δ_Tai(⟨L1|C1[v]⟩, ⟨L2|∅⟩) = min      γ(v, ε) +δ_Tai(⟨L1∪ L1(v)|B1(v)⟩, ⟨L2|∅⟩), (3) min w∈L2 {γ(v, w) + δTai(⟨L1|∅⟩, ⟨L2\ {w}|∅⟩)} +δ_Tai(⟨L1(v)|B1(v)⟩, Φ) (4)     . (E) δ_Tai(⟨L1|C1[v]⟩, ⟨L2|C2[w]⟩) = min            γ(v, w) + δ_Tai(⟨L1|∅⟩, ⟨L2|∅⟩) +δ_Tai(⟨L1(v)|B1(v)⟩, ⟨L2(w)|B2(w)⟩), (5) γ(v, ε) +δ_Tai(⟨L1∪ L1(v)|B1(v)⟩, ⟨L2|C2[w]⟩), (6) γ(ε, w) +δ_Tai(⟨L1|C1[v]⟩, ⟨L2∪ L2(w)|B2(w)⟩) (7)            . 図 3: C1[v] と C2[w] の編集距離 τTai(C1[v], C2[w]) を δ_Tai(⟨∅|C1[v]⟩, ⟨∅|C2[w]⟩) として計算する再帰式. 定理 3 図 3 の再帰式は, C1[v] と C2[w] との編集距離 τ_Tai(C1[v], C2[w]) を δTai(⟨∅|C1[v]⟩, ⟨∅|C2[w]⟩) として 正しく計算する. 証明 少なくとも 1 つの森が空のとき, 再帰式 (A) が 編集距離を計算することは明らかである.

L 1 L 2 w L2(w) B 2 (w) ⟨L1| ∅⟩ ⟨L2| C2[w]⟩ (ε, w)∈ M L1 L2 L 2 (w) B 2 (w) (v, w)∈ M v L1 L 2 w C2[w℄ L2(w) B2(w) 図 4: ⟨L1| ∅⟩, ⟨L2| C2[w]⟩ と (ε, w) ∈ M と (v, w) ∈ M. 再帰式 (B) は, L1 と L2 を子としてもつ r を根と する 2 つの木 r(L1) と r(L2) の編集距離を計算する. τ_Tai(r(L1), r(L2)) は以下のように計算する. r(L1) と r(L2) の最小コストマッピング M は, r と r を, l(v) = l(w) となる v ∈ L1と w ∈ L2を可能な限り一対一で コスト 0 で対応づける. さらに, L1(L2) に残るノード を L1\ L2 (L2\ L1) とみなすと, M は最小コストで v∈ L1\ L2と w∈ L2\ L1を可能な限り一対一で対応 づけ, 残りのノードを ε と対応づける. 再帰式 (C) において, M を⟨L1 | ∅⟩ と ⟨L2 | C2[w]⟩ 間の最小コストマッピングとする. w に焦点を当てる と, 図 4 のように, ある v∈ L1において (ε, w) か (v, w) のどちらかを M は含んでいる. (ε, w) ∈ M のとき, M は ⟨L1 | ∅⟩ のノードから ⟨L2∪ L2(w)| B2(w)⟩ のノードへマッピングし, これは δ_Tai(⟨L1|∅⟩, ⟨L2∪ L2(w)|B2(w)⟩) にて計算される. ある v ∈ L1 において (v, w) ∈ M のとき, M は ⟨L1\ {v} | ∅⟩ のノードから ⟨L1 | ∅ のノードへマッ ピングし, これは δTai(⟨L1\ {v} | ∅⟩, ⟨L2| ∅⟩) にて計 算される. M は最小コストなので, ある v ∈ L1 の γ(v, ε) + δ_Tai(⟨L1\ {v}|∅⟩, ⟨L2|∅⟩) の値を最小化する 必要がある. さらに, ある v∈ L1において M が (v, w) を含むと, M は w の子孫から切り離される. つまり, ⟨L2(w) | B2(w)⟩ にはノードが含まれていない. これ は, δTai(Φ,⟨L2(w)|B2(w)⟩) において計算される. した がって, 式 (2) は M のコストを計算している. 再帰式 (D) についても, (C) と同様に証明することが できる. 再帰式 (E) において, M を⟨L1 | C1[v]⟩ と ⟨L2 | C2[w]⟩ との最小コストのマッピングとする. v と w に焦点を当てると, 図 5 のように M は (v, w), (v, ε), (ε, w) のいずれかのペアを含んでいる. (v, w) ∈ M のとき, M は ⟨L1 | ∅⟩ から ⟨L1(v) | B1(v)⟩ のノードへマッピングできず, ⟨L2 | ∅⟩ から ⟨L2(w)| B2(w)⟩ のノードへマッピングもできない. こ のとき, M は⟨L1 | ∅⟩ のノードを ⟨L2 | ∅⟩ のノードへ マッピングし, これは δ_Tai(⟨L1|∅⟩, ⟨L2|∅⟩) によって計 算される. これにより式 (5) は, M のコストを計算し ている. (v, ε)∈ M のとき, M は ⟨L1∪ L1(v)| B1(v)⟩ のノー ドを_⟨L2(w)| C2[w]⟩ のノードへマッピングする. これ は, δ_Tai(⟨L1∪ L1(v)| B1(v)⟩, ⟨L2| C2[w]⟩) によって計 算される. これにより式 (6) は, M のコストを計算し ている. (ε, w) ∈ M のとき, M は ⟨L1 | C1[v]⟩ のノードを ⟨L2∪ L2(w)| B2(w)⟩ のノードへマッピングする. こ れは, δTai(⟨L1|C1[v]⟩, ⟨L2∪ L2(w)|B2(w)⟩) によって 計算される. これにより式 (7) は, M のコストを計算 している. 2 例 1 2 つのキャタピラ C1と C2について考える. 図 3 の再帰式により, C1と C2との編集距離 τTAI(C1, C2) は以下ように 3 となる. ここでは, キャタピラを言語的 に, C1= a(b, b, b), C2= a(b, a(b, (b(a, a)))) と表す.

L 1 L 2 w L2(w) B 2 (w) ⟨L1| ∅⟩ ⟨L2| C2[w]⟩ (ε, w)∈ M L1 L2 L 2 (w) B 2 (w) (v, w)∈ M v L1 L 2 w C2[w℄ L2(w) B2(w) 図 5: ⟨L1| ∅⟩, ⟨L2| C2[w]⟩ と (ε, w) ∈ M と (v, w) ∈ M. τ_Tai(C1, C2)

= δ_Tai(⟨∅|a(b, b, b)⟩, ⟨∅|a(b, a(b, b(a, a)))⟩) = γ(a, a)

| {z }

=0

+δ_Tai(⟨{b, b, b}|∅⟩, ⟨{b}|a(b, b(a, a))⟩) = γ(ε, a)

| {z }

=1

+δ_Tai(⟨{b, b, b}|∅⟩, ⟨{b, b}|b(a, a)⟩) = 1 + γ(b, b)

| {z }

=0

+δ_Tai(⟨{b, b}|∅⟩, ⟨{b, b}|∅⟩) +δ_Tai(Φ,⟨{a, a}|∅}⟩)

= 1 + γ(b, b) | {z } =0 + γ(b, b) | {z } =0 + γ(ε, a) | {z } =1 + γ(ε, a) | {z } =1 = 3. このとき, γ(l1, l2) において l1̸= ε かつ l2 ̸= ε であ る (l1, l2)∈ C1× C2の組を集めることによって, C1と C2との最適マッピング M を得ることができる. C1[v] と C2[w] をキャタピラとする. このとき, bb(C1[v]) を vn = v かつ par(vi) = vi+1 (1≤ i ≤ n − 1) である v1, ..., vnの列, bb(C2[w]) を wm = w かつ par(wj) = wj+1 (1 ≤ j ≤ m − 1) である w1, ..., wmの列として 表す. この場合, bb(C1[v]) = [v1, ..., vn], bb(C2[w]) = [w1, ..., wm] と表す. さらに, 1≤ i ≤ n における L1(vi) と B1(vi), 1≤ j ≤ m における L2(wj) と B2(wj) にも 同じ表記を用いる. アルゴリズム 1 は, 図 3 の再帰式を基にキャタピラ C1と C2との編集距離 τTai(C1, C2) の計算をするアル ゴリズムである. ここでは, 再帰式 (A),(B),(C),(D),(E) は, それぞれ 6 行目と 12 行目, 3 行目, 9 行目, 15 行目, 19 行目と対応している. 定理 4 C1と C2がキャタピラのとき, C1と C2の編集 距離 τ_Tai(C1, C2) は O(σh2) 時間で計算可能である. こ のとき, σ =|Σ|, h = max{h(C1), h(C2)} である. 証明 bb(C1) = [v1, ..., vn], bb(C2) = [w1, ..., wm] とす る. このとき, h(C1) = n + 1 かつ h(C2) = m + 1 は明 らかであり, m≤ h − 1, n ≤ h − 1 である. アルゴリズム 1 の τ_TAI(C1, C2) は一度に (vi, wj) ∈ bb(C1)× bb(C2) のすべての組を呼び出す. このとき, Σ 中のラベルと L1と L2におけるその頻度の組である Σ のハッシュテーブルを用いることで, δ_Tai(⟨L1(vi₋₁)| C1[vi]⟩, ⟨L2(wj₋₁)| C2[wj]⟩) を O(σ) 時間で計算する ことができる. 最後に, アルゴリズム 1 は L1(v1)∪ ... ∪ L1(vn) と L2(w1)∪ ... ∪ L2(wm) における Σ のハッシュ テーブルを比較すればよい. したがって, アルゴリズム 1 の全体の計算時間は以 下のようになる. n ∑ i=1 m ∑ j−1

O(σ) = O(σ)mn≤ O(σ)(h − 1)2= O(σh2).

2

また, 定理 5 は, キャタピラという構造的制限が, 無 順序木の編集距離の多項式時間計算可能の限界を与え ていることも主張している. すべての葉が取り除かれ

た後にキャタピラになる木を一般化キャタピラという. このとき, [1, 3] の結果として以下の定理が成り立つ. 定理 5 ([1, 3]) 一般化キャタピラ間の編集距離の計算 問題は, たとえ最大高さが 3 であっても MAX SNP 困 難である. 証明 文献 [1] の定理 4.3 または, 文献 [3] の定理 1 よ り成り立つ. 2 アルゴリズム 1: τ_Tai(C1, C2) procedure τtai(C1, C2) /* C1, C2: キャタピラ*/ τtai(C1, C2)← δ_Tai(⟨∅|C1⟩, ⟨∅|C2⟩); 1 procedure δ_Tai(⟨L1|C1⟩, ⟨L2|C2⟩) /* L1, L2 : 葉集合, C1, C2: キャタピラ*/ if C1=∅ and C2 =∅ then 2 δ_Tai(⟨L1|∅⟩, ⟨L2|∅⟩) ←再帰式(B)を計算; 3

else if C1=∅ and C2̸= ∅ then

4 /* bb(C2) = [w1, . . . , wm], wm= r(C2) */ if L1=∅ then 5 δ_Tai(Φ,⟨L2|C2⟩) ←再帰式(A)を計算; 6 /*⟨L1|C1⟩ = Φ */ else 7 for j = 1 to m do 8 δ_Tai(⟨L1|∅⟩, ⟨L2|C2[wj]⟩) ← wをwj 9 として再帰式(C)を計算;

else if C1̸= ∅ and C2=∅ then

10 /* bb(C1) = [v1, . . . , vn], vn= r(C1) */ if L2=∅ then 11 δ_Tai(⟨L1|C1⟩, Φ) ←再帰式(A)を計算; 12 /*⟨L2|C2⟩ = Φ */ else 13 for i = 1 to n do 14 δ_Tai(⟨L1|C1[vi]⟩, ⟨L2|∅⟩) ← vをviと 15 して再帰式(D)を計算; else 16 /* bb(C1) = [v1, . . . , vn], bb(C2) = [w1, . . . , wm], vn= r(C1), wm= r(C2) */ for i = 1 to n do 17 for j = 1 to m do 18 δ_Tai(⟨L1|C1[vi]⟩, ⟨L2|C2[wj]⟩) ← v, w 19 をそれぞれvi, wjとして再帰式(E)を 計算; アルゴリズム 1

4

まとめと今後の課題

本論文では, 無順序木の編集距離を多項式時間で計算 する制限を加えたキャタピラの編集距離を O(σh2_{) 時} 間で計算するアルゴリズムを構築した. この論文は, 理論のみであるので, まずアルゴリズム 1 を実装し, 実データに対して実験を行うことが必要で ある. その際, キャタピラの編集距離を完全部分木ヒス トグラム距離 [1] やパスヒストグラム距離 [4] と比較し, 考察をすることが課題として挙げられる. また, キャタ ピラと一般化キャタピラもしくは一般の木の編集距離 の計算問題が多項式時間で可能であるか否かについて 議論することも今後の課題である. 特に, 表 1 にある

D ∈ {Auction, University, Protein, Nasa} である D−

と関連して, キャタピラの森編集距離の計算問題が多 項式時間で計算可能か否かの調査を行うことも課題で ある.

参考文献

[1] T. Akustu, D. Fukagawa, M. M. Halldorsson, A. Takasu, K. Tanaka: Approximation and

parame-terized algorithms for common subtrees and edit distance between unordered trees , Theoret.

Com-put. Sci. 470, 10-22 (2013).

[2] J. A. Gallian: A dynamic survey of graph

label-ing, Electorn. J. Combin. 14, DS6 (2007).

[3] K. Hirata, Y. Yamamoto, T. Kuboyama:

Im-proved MAX SNP-hard results for finding an edit distance between unordered trees , Proc. CPM’11,

LNCS 6661, 402-415 (2011).

[4] T. Kawaguchi, T. Yoshino, K. Hirata: Path

his-togram distance for rooted labeled caterpillars,

Proc. ACIIDS’18. LNAI 10751, 276-286 (2018).

[5] K. -C. Tai: The tree-to-tree correction problem , J. ACM 26, 422-433 (1979).

[6] K. Zhang, T. Jiang: Some Max SNP-hard results

concerning unordered labeled trees , Inform.