Taiマッピングの根無し木への拡張

人工知能学会研究会資料
SIG-FPAI-B502-16
Tai マッピングの根無し木への拡張
Enhanced Tai Mapping to Unrooted Trees
芳野拓也 1∗
Takuya Yoshino1
平田耕一 2
Kouichi Hirata2
九州工業大学情報工学府情報工学専攻
Graduate School of Computer Science and Systems Engineering,
Kyushu Institute of Technology
2
九州工業大学情報工学研究院
Department of Artificial Intelligence, Kyushu Institute of Technology
1
1
2
Abstract: In this paper, we enhance a Tai mapping to unrooted trees, motivated by the 4point condition and the 3-point condition for phylogenetic trees. First, we introduce 4-pointpreserving mapping, rooted 4-point-preserving mapping and 3-point-preserving mapping, additionally subtree-preserving mapping, center-preserving mapping and and path-preserving mapping
as a bijection of nodes in two unrooted trees. Then, we show that, for rooted trees, a constrained
mapping coincides with a 3-point-preserving mapping and a less-constrained mapping coincides
with a 4-point-preserving mapping and a rooted 4-point preserving mapping. We also show that,
for unrooted trees, a subtree-preserving mapping is always center-preserving, a center-preserving
mapping is always 4-point-preserving and a 4-point-preserving mapping is always path-preserving,
but no converse directions hold in general.
1
はじめに
2 つの根付き木 (rooted tree) 間の Tai マッピング
(Tai mapping) [8] は, 単射であり, かつ, 先祖子孫関係
を保存する (根付き順序木の場合はさらに兄弟関係を保
存する) ノード間の対応付けである. この Tai マッピン
グは, マッピングによる対応付けがあるノードを置換,
対応付けがない木のノードを削除と挿入とみなすこと
で, 2 つの根付き木間の Tai マッピングの最小コストが
木編集距離 (tree edit distance) となることが知られて
いる [8]. また, Tai マッピングに様々な制約を入れる
ことで, 数多くの木編集距離の変種を導入することが
でき [4, 5, 10, 11, 12], そのときの Tai マッピングが階
層を成すことも知られている [3, 9]. さらに, Tai マッ
ピングは, 木カーネルの一種であるマッピングカーネ
ル [2, 6] の定式化における数え上げの対象でもある.
このように, 根付き木において Tai マッピングは木編
集距離や木カーネルとして重要な概念であるが, この
Tai マッピングを根無し木 (unrooted tree) に拡張する
ためには, 単射であることに加えて, 先祖子孫関係に代
わる条件を導入する必要がある. Zhang ら [12] は, 挿
∗ 連絡先：九州工業大学情報工学府情報工学専攻
〒 820-8502 福岡県飯塚市川津 680-4
E-mail: [email protected]
入と削除を次数 2 以下のノードに制限した次数 2 距離
(degree-2 distance) を根無し木に拡張する際, 根付き木
の LCA 保存マッピングの拡張として, 3 つのノードの
中心 (center) を保存する中心保存マッピング (centerpreserving mapping) を導入した. ここで, 3 つのノー
ドの中心とは, 2 つのノード間の 3 つのパスの共通ノー
ドである. 本研究では, この中心に着目する.
生物種の進化を表す進化系統樹 (phylogenetic tree) [7]
は, 葉に生物種のラベルが付いた根無し木もしくは根付
き木である. この進化系統樹の再構成とは, すべての生
物種 (葉) 間の距離が距離行列として与えらえれたとき,
その距離がパス上の辺の重みの総和となる進化系統樹
を求める問題である.
距離行列から進化系統樹を再構成できるとき, 距離
行列は加法的である (additive) といい, 距離行列から
葉の高さがすべて等しい根付き進化系統樹を構成でき
るとき, 距離行列は超計量的である (ultrametric) とい
う [7]. このとき, 距離行列における任意の異なる 4 つ
の生物種が 4 点条件 (4-point condition) [1] を満たす
とき, そのときに限り, 距離行列は加法的となる [7]. ま
た, 加法的距離行列における任意の異なる 3 つの生物
種が 3 点条件 (3-point condition) を満たすとき, その
ときに限り, 距離行列は超計量的になる [7].
この 4 点条件と 3 点条件は, 辺の重みの総和としての
− 55 −
距離についての条件である. 本論文では, この 2 つの条
件を, 中心を用いることで木のトポロジーを特徴づける
条件に変更する. ノード u, v, w の中心を c(u, v, w) とす
る. 根無し木のノード u, v, w, x が c(u, v, w) = c(u, v, x)
かつ c(u, w, x) = c(v, w, x) を満たすとき, ノードの 2
つの組 (u, v) と (w, x) は 4 点条件を満たすという. ま
た, 先祖子孫関係 ≤ に対して, 根 r を持つ根付き木の
ノード u, v, w が c(u, w, r) ≤ c(v, w, r) = c(u, v, r) を
満たすとき, (u, v, w) は 3 点条件を満たすという.
根無し木 T1 と T2 に対して, M ⊆ V (T1 ) × V (T2 ) を
単射とする. M に 4 点条件と 3 点条件を保存するとい
う条件を加えることによって, 4 点保存マッピング (4point-preserving mapping), 根付き 4 点保存マッピン
グ (rooted 4-point-preserving mapping), 3 点保存マッ
ピング (3-point-preserving mapping) を導入する.
また, M が T1 の部分木と T2 の部分木を対応付ける
とき M を部分木保存マッピング (subtree-preserving
mapping) という. また, M が T1 , T2 のパスを対応付
けるとき, M をパス保存マッピング (path-preserving
mapping) という.
これらの準備の下で, 本論文では, M が根付き木の
マッピングの場合, 以下が成り立つことを示す.
M は制限 (constrained) マッピング [10, 11]
⇐⇒ M は 3 点保存マッピング.
M は劣制限 (less-constrained) マッピング [4]
⇐⇒ M は 4 点保存マッピング
⇐⇒ M は根付き 4 点保存マッピング.
また, M が根無し木のマッピングの場合, 以下の含意が
成り立つことを示す. ただし, 一般に逆は成り立たない.
M は部分木保存マッピング
=⇒ M は中心保存マッピング
=⇒ M は 4 点保存マッピング
=⇒ M はパス保存マッピング.
2
ての u, v ∈ V ′ に対して u から v へのパスが T’ 中に存
在するとき, T ′ を T の部分木という.
特に, 根付き木 T の根を r とするとき, ノード v(∈
T \ {r}) に対して, [r, v] 上の v に隣接するノードを v
の親といい, par (v) で表す. また, [r, v] \ {v} のノード
を v の先祖という. u, v ∈ T に対して, v が u の親であ
るとき, u を v の子という. 子を持たないノードを葉と
いう.
本論文では, v が u の先祖であることを, u < v と表
し, u < v または u = v であることを, u ≤ v と表す.
u, v ∈ T に対して, u ≤ w, v ≤ w であり, w′ < w な
る w′ が存在しないような w を u と v の最近共通先祖
(LCA) といい, u ⊔ v で表す.
補題 1 根付き木 T の根ノードを r とし, u, v ∈ T とす
る. このとき c(u, v, r) = u ⊔ v が成り立つ.
ノード u, v ∈ T に対して, 先行走査順 pre に関し
て pre(u) ≤ pre(v) であり, 後行走査順 post に関して
post(u) ≤ post(v) であるとき, u を, v の左にあるとい
い, u ⪯ v と表す. 根付き木に対して, 兄弟間の左右の
順序関係が与えられているものを順序木, そうでないも
のを無順序木という.
アルファベット Σ の要素が各ノードに割り当てられ
ているような木をラベル付き木という. また各ノード
に割り当てられた記号をラベルといい, v ∈ T のラベル
を l(v) で表す.
最後に, 進化系統樹 [7] における 4 点条件と 3 点条件
を導入する. 本来の 4 点条件と 3 点条件の定義は辺の
重みの和によって定義されるが, 本稿では中心を用いる
ことによって, (根の有無に関わらず) 木のトポロジー
に基づいて定式化する.
定義 1 (4 点条件) 木 T の 2 組のノードの対 (u, v) と
(w, x) に対して, c(u, v, w) = c(u, v, x) and c(u, w, x) =
c(v, w, x) が成り立つとき, その 2 組のノード対は 4 点
条件を満たすという.
準備
閉路を持たない連結グラフを木という. 木 T = (V, E)
に対して, v ∈ V (T ) を単に v ∈ T と表す.
木 T のうち, 根ノード r ∈ T を 1 つ選んだものを根
付き木, そうでないものを根無し木という. 根付き木 T
の根を r(T ) と表す.
T = (V, E) を木とする. u, v ∈ T に対して, V ′ =
{v1 , . . . , vn }, E ′ = {(vi , vi+1 ) | 1 ≤ i ≤ n − 1}, v1 =
u, vn = v を満たす木 (E ′ , V ′ ) を u から v へのパスとい
い, [u, v] で表す. u, v, w ∈ T に対して, [u, v], [v, w], [w, u]
に共通するノードを {u, v, w} の中心 [12] といい, c(u, v, w)
で表す. V ′ ⊆ V , E ′ ⊆ E, T ′ = (V ′ , E ′ ) とする. すべ
図 1 (左) は, 4 点条件のトポロジーである. ここで,
実線はパス, c(u, v, w) = c(u, v, x) = c, c(u, w, x) =
c(v, w, x) = d である.
中心と 4 点条件は, 根付き木でも定義できる. 図 1
(右) はノード r を根とする根付き木における 4 点条件
のトポロジーである.
定義 2 (3 点条件) T を根付き木とし, その根ノード r
とする. T のノードの 3 つ組 (u, v, w) に対して, c(u, w, r) ≤
c(v, w, r) = c(u, v, r), すなわち u ⊔ w ≤ v ⊔ w = u ⊔ v
が成り立つとき, その 3 つ組は 3 点条件を満たすという.
図 2 は根付き木の 3 点条件のトポロジーである.
進化系統樹の再構成では, 以下の補題が知られている.
− 56 −
u
v
r
w
d
d
u
x
また, 根付き木に関して, Tai マッピングの変種を導
入する.
v
w
定義 5 (根付きマッピングの変種 (1)) M を T1 , T2 間
の根付きマッピングとする.
x
図 1: 根無し木 (左) および根付き木 (右) における 4 点
条件のトポロジー.
1. M が以下を満たすとき, M をトップダウンマッ
ピング [5] といい, M ∈ MTop (T1 , T2 ) と表す.
(
)
∀(v1 , v2 ) ∈ M (par (v1 ), par (v2 )) ∈ M .
r
u
v
2. M が以下を満たすとき, M を LCA 保存マッピ
ング [12] といい, M ∈ MLca (T1 , T2 ) と表す.
(
)
∀(u1 , u2 ), (v1 , v2 ) ∈ M (u1 ⊔ v1 , u2 ⊔ v2 ) ∈ M .
w
図 2: 根付き木における 3 点条件のトポロジー.
3. M が以下を満たすとき, M を孤立部分木マッピ
ング [9], もしくは制限マッピング [10, 11] とい
い, M ∈ MIlSt (T1 , T2 ) と表す.
補題 2 (cf. [7]) 根無し木の任意の 4 つの異なる葉に対
して, 4 点条件を満たすような 2 組の対の取り方が存在
する.
補題 3 (cf. [7]) 根付き木の任意の 3 つの異なる葉に
対して, 3 点条件を満たすような 3 つ組の取り方が存在
する.
3
マッピング
本節では, マッピングを 2 つの木のノード間の一対一
対応として定義する.
∀(u
(1 , u2 ), (v1 , v2 ), (w1 , w2 ) ∈ M,
)
w1 < u1 ⊔ v1 ⇐⇒ w2 < u2 ⊔ v2 .
補題 4 根付き木 T1 , T2 と, A ∈ {Top,Lca,IlSt} に
対して, M ∈ MA (T1 , T2 ) ならば, M ∈ MTai (T1 , T2 ).
定義 6 (根付きマッピングの変種 (2)) M を T1 , T2 間
の根付きマッピングとする.
1. M が以下を満たすとき, M を劣制限マッピング [4]
といい, M ∈ MLess (T1 , T2 ) と表す.
定義 3 (マッピング [8]) T1 , T2 を木とし, M ⊆ V (T1 )×
V (T2 ) とする. M が以下を満たすとき, 3 つ組 (M, T1 , T2 )
を木 T1 , T2 間のマッピングという:
(
)
∀(u1 , u2 ), (v1 , v2 ) ∈ M u1 = v1 ⇐⇒ u2 = v2
∀(u
(1 , u2 ), (v1 , v2 ), (w1 , w2 ) ∈ M,
)
u1 ⊔ v1 < u1 ⊔ w1 =⇒ v2 ⊔ w2 = u2 ⊔ w2 .
2. M が Tai マッピングであり, 劣制限マッピングで
あるとき, すなわち
(一対一対応).
誤解の恐れがない場合, 3 つ組 (M, T1 , T2 ) を, 単に M
で表す. また, 根付き木 (根無し木) 間のマッピングを
単に根付き (根無し) マッピングという.
定義 4 (Tai マッピング [8]) T1 , T2 を根付き木, M を
T1 , T2 間の根付きマッピングとする. M が以下を満た
すとき, M を T1 , T2 間の順序 Tai マッピングという:
(
)
1. ∀(u1 , u2 ), (v1 , v2 ) ∈ M u1 ≤ v1 ⇐⇒ u2 ≤ v2
(先祖子孫関係の保存).
(
)
2. ∀(u1 , u2 ), (v1 , v2 ) ∈ M u1 ⪯ v1 ⇐⇒ u2 ⪯ v2
M ∈ MTai (T1 , T2 ) ∩ MLess (T1 , T2 )
であるとき, M を劣制限 Tai マッピングといい,
M ∈ MLessTai (T1 , T2 ) と表す.
次に, 根無しマッピングの変種と, 4 点条件と 3 点条
件に関連した根付きマッピングの変種を導入する.
定義 7 (根無しマッピングの変種) M を T1 , T2 間の根
無しマッピングとする.
(兄弟関係の保存).
また, M が上記条件の 1 を満たすとき, M を T1 , T2 間
の無順序 Tai マッピングという. M が順序 Tai マッ
ピングまたは無順序 Tai マッピングであるとき, M ∈
MTai (T1 , T2 ) と表記する.
− 57 −
1. M が以下のパス保存条件を満たすとき, M をパ
ス保存マッピングといい, M ∈ MPath (T1 , T2 ) と
表す:
∀(u
(1 , u2 ), (v1 , v2 ), (w1 , w2 ) ∈ M, )
w1 ∈ [u1 , v1 ] ⇐⇒ w2 ∈ [u2 , v2 ] .
2. M が以下の中心保存条件 [12] を満たすとき, M
を中心保存マッピングといい, M ∈ MCnt (T1 , T2 )
と表す:
点保存マッピングといい, M ∈ M3Pnt (T1 , T2 ) と表す:
任意の (u1 , u2 ), (v1 , v2 ), (w1 , w2 ) ∈ M に対して,
以下を満たすように ui , vi , wi (i = 1, 2) を置き換える
ことができる.
∀(u
(1 , u2 ), (v1 , v2 ), (w1 , w2 ) ∈ M,
)
(c(u1 , v1 , w1 ), c(u2 , v2 , w2 )) ∈ M .
3. 集合 {u ∈ T1 | (u, v) ∈ M } と
{v ∈ T2 | (u, v) ∈ M } が, それぞれ T1 = (V1 , E1 )
と T2 = (V2 , E2 ) の部分木を誘導し,
任意の (u1 , u2 ), (v1 , v2 ) ∈ M に対して, (u1 , v1 ) ∈
E1 ⇐⇒ (u2 , v2 ) ∈ E2 を満たすとき, M を部分
木保存といい, M ∈ MSubt (T1 , T2 ) と表す.
4. M が以下の 4 点保存条件を満たすとき, M を 4
点保存マッピングといい, M ∈ M4Pnt (T1 , T2 ) と
表す:
任意の (u1 , u2 ), (v1 , v2 ), (w1 , w2 ), (x1 , x2 ) ∈
M に対して, 以下を満たすように ui , vi , wi , xi
(i = 1, 2) を置き換えることができる.
⇐⇒
c(u1 , v1 , w1 ) = c(u1 , v1 , x1 ) かつ
c(u1 , w1 , x1 ) = c(v1 , w1 , x1 )
c(u2 , v2 , w2 ) = c(u2 , v2 , x2 ) かつ
c(u2 , w2 , x2 ) = c(v2 , w2 , x2 ).
また, 根付き木の 4 点保存条件を以下の通りに導入
する.
定義 8 (根付き 4 点保存条件) T1 , T2 をそれぞれ, r1 , r2
を根とする根付き木, M を T1 , T2 間の根付きマッピン
グとする. M が以下の根付き 4 点保存条件を満たす
とき, M を根付き 4 点保存マッピングといい, M ∈
Mr4Pnt (T1 , T2 ) と表す:
任意の (u1 , u2 ), (v1 , v2 ), (w1 , w2 ) ∈ M に対して,
以下を満たすように ui , vi , wi (i = 1, 2) を置き換える
ことができる.
⇐⇒
⇐⇒
c(u1 , w1 , r1 ) ≤ c(v1 , w1 , r1 ) = c(u1 , v1 , r1 )
(u1 ⊔ w1 ≤ v1 ⊔ w1 = u1 ⊔ v1 と等価)
c(u2 , w2 , r2 ) ≤ c(v2 , w2 , r2 ) = c(u2 , v2 , r2 )
(u2 ⊔ w2 ≤ v2 ⊔ w2 = u2 ⊔ v2 と等価).
マッピングの階層
4
根付きマッピングには以下の階層が知られている.
MTop (T1 , T2 ) ⊂ MLca (T1 , T2 ) ⊂ MIlSt (T1 , T2 ) ⊂
MLessTai (T1 , T2 ) ⊂ MTai (T1 , T2 ).
まず, 根付きマッピングの改装について議論する. 以
下, T1 , T2 を根付き木とする.
定理 1 M3Pnt (T1 , T2 ) = MIlSt (T1 , T2 ).
[証明] M ∈ MIlSt (T1 , T2 ) と仮定すると, M は w1 ≤
u1 ⊔ v1 ⇐⇒ w2 ≤ u2 ⊔ v2 を満たす. このとき, M は
図 3 で示す M1 , M2 , M3 のどれかの形をとる. このう
ち, 3 点保存条件を満たすのは M1 と M3 である. また,
ui を vi と置き換えることにより, M2 もまた, 3 点保存
条件を満たす. したがって, M ∈ M3Pnt (T1 , T2 ) が成
り立つ.
一方, M ∈ M3Pnt (T1 , T2 ) と仮定すると, M は u1 ⊔
w1 ≤ v1 ⊔w1 = u1 ⊔v1 ⇐⇒ u2 ⊔w2 ≤ v2 ⊔w2 = u2 ⊔v2
を満たす. このとき, M は M1 , M2′ , M3 のどれかの形
をとる. M2′ について, w1 ≤ u1 ⊔ v1 ⇐⇒ w2 ≤ u2 ⊔ v2
が成り立つ. したがって, M ∈ MIlSt (T1 , T2 ) が成り立
つ.
2
補題 5 M ∈ MTai (T1 , T2 ) \ Mr4Pnt (T1 , T2 ) となる根
付きマッピング M が存在する.
c(u1 , v1 , w1 ) = c(u1 , v1 , r1 ) かつ
c(u1 , w1 , r1 ) = c(v1 , w1 , r1 )
c(u2 , v2 , w2 ) = c(u2 , v2 , r2 ) かつ
c(u2 , w2 , r2 ) = c(v2 , w2 , r2 ).
補題 6 M ∈ Mr4Pnt (T1 , T2 ) \ MTai (T1 , T2 ) となる根
付きマッピング M が存在する.
M が Tai マッピングであり, 根付き 4 点保存マッピ
ングでもあるとき, すなわち, M ∈ MTai (T1 , T2 ) ∩
Mr4Pnt (T1 , T2 ) であるとき, M を根付き 4 点保存 Tai
マッピングといい, M ∈ Mr4PntTai (T1 , T2 ) と表す.
定義 9 (3 点保存条件) T1 , T2 をそれぞれ, r1 , r2 を根
とする根付き木, M を T1 , T2 間の根付きマッピングと
する. M が以下の 3 点保存条件を満たすとき, M を 3
定理 2 M4Pnt (T1 , T2 ) = Mr4Pnt (T1 , T2 ) = MLess (T1 , T2 ).
[証明] M4Pnt (T1 , T2 ) = Mr4Pnt (T1 , T2 ) は自明に成り
立つ. 補題 1 より, 根付き 4 点保存条件を以下のように
書き換えることができる.
⇐⇒
− 58 −
c(u1 , v1 , w1 ) = u1 ⊔ v1 かつ u1 ⊔ w1 = v1 ⊔ w1
c(u2 , v2 , w2 ) = u2 ⊔ v2 かつ u2 ⊔ w2 = v2 ⊔ w2 .
したがって, M ∈ Mr4Pnt (T1 , T2 ) が成り立つ.
r1
1
u1
r1
r2
2
v1
w1
u2
r2
u1
v2
w1
w2
u2
d1
M1
w2
v2
M2
r1
v1
次に, 根無しマッピングの階層について議論する. 以
下, T1 と T2 は根無し木とする.
r2
v2
d1
w1
u1
d2
w2
r1
u2
u1
r2
w1
u2
v1
M2′
補題 7 MSubt (T1 , T2 ) ⊂ MCnt (T1 , T2 ).
w2
v2
M3
図 3: 定理 1 の証明に用いる根付きマッピング Mi .
M ∈ Mr4Pnt (T1 , T2 ) と仮定する. もし, u1 ⊔ v1 <
u1 ⊔ w1 , ならば T1 中の u1 , v1 , w1 のトポロジーは, 図 4
(1), (2), (3) に示す通りになる. このとき (2), (3) では
u1 < v1 or v1 < u1 のどちらか一方が成り立つ. よっ
て, c(u1 , v1 , w1 ) = u1 ⊔ v1 < u1 ⊔ w1 = v1 ⊔ w1 が
成り立つ. 根付き 4 点保存条件より, c(u2 , v2 , w2 ) =
u2 ⊔ v2 及び u2 ⊔ w2 = v2 ⊔ w2 が成り立つ. ゆえに,
M ∈ MLess (T1 , T2 ) が成り立つ.
r1
r1
r1
r2
d1
d1
w1
d2
1
u1
注意 1 定理 2 の Mr4PntTai (T1 , T2 ) = MLessTai (T1 , T2 )
を示すには, T1 , T2 のトポロジーを図 4 の (1), (4), (7)
と比較すればよい.
d2
v1
v1
w1
w1
v1
u1
v1
(1)
2
u1
(2)
u2
(3)
r2
2
w2
r2
v2
2
v2
w2
u2
u2
(5)
(6)
u2
v2
[証明] M ∈ MSubt (T1 , T2 ) とし, (u1 , u2 ), (v1 , v2 ),
(w1 , w2 ) ∈ M とする. このとき, T1 の [u1 , v1 ] ([v1 , w1 ],
[w1 , u1 ]) と, T2 の [u2 , v2 ] ([v2 , w2 ], [w2 , u2 ]) は同型で
あるので, (c(u1 , v1 , w1 ), c(u2 , v2 , w2 )) ∈ M が成り立
つ. ゆえに, M ∈ MCnt (T1 , T2 ) が成り立つ.
一方, 図 5 のようなマッピング M ∈ MCnt (T1 , T2 ) \
MSubt (T1 , T2 ) が存在する.
2
u1
Æ
u2
1
v1
Æ
Æ
Æ
w1
2
v2
Æ
w2
Æ
図 5: 補題 7 の根無しマッピング M .
補題 8 MCnt (T1 , T2 ) ⊂ M4Pnt (T1 , T2 ).
w2
v2
(4)
r2
2
w2
(7)
図 4: 定理 2 の証明に用いる木のトポロジー.
逆に, M ∈ MLess (T1 , T2 ) を仮定する. u1 ⊔ v1 <
u1 ⊔w1 とすると, 図 4 (1), (2), (3) より, c(u1 , v1 , w1 ) =
u1 ⊔ v1 及び u1 ⊔ w1 = v1 ⊔ w1 が成り立つ. 一方,M は
劣制限マッピングであるため, v2 ⊔ w2 = u2 ⊔ w2 が成
り立つ. そのため, c(u2 , v2 , w2 ) = u2 ⊔ v2 を示せばよ
いことになる.
もし, u2 ⊔ v2 < u2 ⊔ w2 ならば, T2 中での u2 , v2 , w2
のトポロジーは図 4 (4), (5), (6) に示す通りになり,
c(u2 , v2 , w2 ) = u2 ⊔v2 = c2 が成り立つ. もし, u2 ⊔v2 =
u2 ⊔w2 ならば, T2 中での u2 , v2 , w2 のトポロジーは図 4
(7) に示す通りになり, c(u2 , v2 , w2 ) = u2 ⊔ v2 = c2 が
成り立つ.
[証明] M ∈ MCnt (T1 , T2 ) とし,
(u1 , u2 ), (v1 , v2 ), (w1 , w2 ), (x1 , x2 ) ∈ M とする. 補題 1
より, c1 = c(u1 , v1 , w1 ) = c(u1 , v1 , x1 ) かつ d1 =
c(u1 , w1 , x1 ) = c(v1 , w1 , x1 ) を満たすように, u1 , v1 , w1 ,
x1 を置き換えることができる. もし (c1 , c2 ) ∈ M なる
ノード c2 ∈ T2 が存在するなら, c1 = c(u1 , v1 , w1 ) =
c(u1 , v1 , x1 ) であり M が中心保存マッピングであるこ
とから, c2 = c(u2 , v2 , w2 ) = c(u1 , v1 , x1 ) が成り立つ.
また, (d1 , d2 ) ∈ M なるノード d2 ∈ T2 が存在するな
ら, d1 = c(u1 , w1 , x1 ) = c(v1 , w1 , x1 ) であり M が中心
保存マッピングであることから, d2 = c(u2 , w2 , x2 ) =
c(v2 , w2 , x2 ) が成り立つ. ゆえに, M ∈ M4Pnt (T1 , T2 )
となる.
一方, 図 6 のようなマッピング M ∈ M4Pnt (T1 , T2 ) \
MCnt (T1 , T2 ) が存在する.
2
補題 9 M4Pnt (T1 , T2 ) ⊂ MPath (T1 , T2 ).
[証明] M ∈ M4Pnt (T1 , T2 ) とする. このとき, すべ
ての (u1 , u2 ), (v1 , v2 ), (w1 , w2 ), (x1 , x2 ) ∈ M のトポロ
ジーは T1 , T2 中で図 7 の通りになる.
(y1 , y2 ) ∈ M となる, y1 ∈ [c1 , d1 ], y2 ∈ [u2 , c2 ] を
仮定する. このとき, c(u1 , v1 , y1 ) = c(u1 , v1 , w1 ) = c1 ,
− 59 −
u1
w1
1
u2
d1
v1
w2
2
x1
u1
d2
v2
w1
1
x2
v1
図 6: 補題 8 の M .
u1
w1
1
v1
w2
2
x1
2
x1
w2
d2
x2
注意 2 操作的には, MTop [5] と MSubt は, 挿入と削除
を次数 1 のノード (根付き木の場合は葉, 根無し木の場
合は端点) に制限したものと対応する. また, MLca [12]
と MCnt [12] は, 挿入と削除を次数 2 以下のノードに
制限したものと対応する.
d2
v2
T1
d1
v2
図 8: 補題 9 の M .
u2
d1
u2
x2
T2
図 7: 補題 9 の証明で用いる M のトポロジー.
c(u2 , v2 , y2 ) = y2 , c(u2 , v2 , w2 ) = c2 が成り立つ. ゆえ
に, y2 = c2 となる.
(y1 , y2 ) ∈ M となる, y1 ∈ [u1 , c1 ], y2 ∈ [v2 , d2 ] を
仮定する. このとき, c(y1 , v1 , x1 ) = c(y1 , v1 , w1 ) =
c1 , c(y2 , v2 , x2 ) = c(y2 , v2 , w2 ) = y2 が成り立つ. ま
た, c(u2 , y2 , w2 ) = c(u2 , y2 , x2 ) = c2 , c(u1 , y1 , w1 ) =
c(u1 , y1 , x1 ) = y1 が成り立つ.
(y1 , y2 ) ∈ M となる, y1 ∈ [u1 , c1 ], y2 ∈ [w2 , d2 ]
を仮定する. このとき, c(y1 , v1 , x1 ) = c(y1 , v1 , w1 ),
c(y2 , v2 , x2 ) = d2 , c(y2 , v2 , w2 ) = y2 が成り立つ. また,
c(u2 , v2 , y2 ) = c(u2 , v2 , x2 ), c(u1 , v1 , y1 ) = y1 ,
c(u1 , v1 , x1 ) = c1 が成り立つ. ゆえに, y1 = c1 , y2 = d2
となる.
上記の議論を組み合わせることにより, (y1 , y2 ) ∈ M
に対して以下が成り立つ. ここで, k ∈ {u, v}, l ∈
{w, x} である.
1. y1 ∈ [c1 , d1 ] iﬀ y2 ∈ [c2 , d2 ].
参考文献
[1] P. Buneman: A note on the metric properties of
trees, J. Comb. Theory (B) 17, 48–50, 1974.
[2] K. Hirata, T. Kuboyama, T. Yoshino: Mapping kernels between rooted labeled trees beyond orderd trees,
New Frontier in Artificial Intelligence, LNAI 9067,
317–330, 2015.
[3] T. Kuboyama: Matching and learning in trees, Ph.D
thesis, University of Tokyo, 2007.
[4] C. L. Lu, Z.-Y. Su, C. Y. Yang: A new measure
of edit distance between labeled trees, Proc. COCOON’01, LNCS 2108, 338–348, 2001.
[5] S. M. Selkow: The tree-to-tree editing problem, Inform. Process. Lett. 6, 184–186, 1977.
[6] K. Shin, M. Cuturi, T. Kuboyama: Mapping kernels
for trees, Proc. ICML 2011, 2011.
[7] W.-K. Sung: Algorithms in bioinformatics: A practical introduction, Chapman & Hall/CRC, 2009.
[8] K.-C. Tai,
The tree-to-tree correction problem,
J. ACM 26, 422–433, 1979.
2. y1 ∈ [u1 , v1 ] iﬀ y2 ∈ [u2 , v2 ].
3. y1 ∈ [w1 , x1 ] iﬀ y2 ∈ [w2 , x2 ].
4. y1 ∈ [k1 , c1 ] かつ y2 ∈ [l2 , d2 ] ならば, y1 = c1 か
つ y2 = d2 .
5. y1 ∈ [l1 , d1 ] かつ y2 ∈ [k2 , c2 ] ならば, y1 = d1 か
つ y2 = c2 .
したがって, M ∈ MPath (T1 , T2 ) となる.
一方, 図 8 のようなマッピング M ∈ MPath (T1 , T2 ) \
M4Pnt (T1 , T2 ) が存在する.
2
[9] J. T. L. Wang, K. Zhang: Finding similar consensus
between trees: An algorithm and a distance hierarchy, Pattern Recog. 34, 127–137, 2001.
[10] K. Zhang: Algorithms for the constrained editing distance between ordered labeled trees and related problems, Pattern Recog. 28, 463–474, 1995.
[11] K. Zhang: A constrained edit distance between unordered labeled trees, Algorithmica 15, 205-222, 1996.
[12] K. Zhang, J. Wang and D. Shasha: On the editing
distance between undirected acyclic graphs, Internat.
J. Found. Comput. Sci. 7, 43–58, 1995.
補題 7, 8, 9 をまとめると以下の通りになる.
定理 3 根無し木 T1 , T2 に対して, 以下が成り立つ.
MSubt (T1 , T2 ) ⊂ MCnt (T1 , T2 ) ⊂
M4Pnt (T1 , T2 ) ⊂ MPath (T1 , T2 ).
− 60 −

Download Report