根付きラベル付き順序木のトップダウン距離計算のSETH困難性
5
0
0
全文
(2)
(3)
(4)
(5) 平田耕一. . 芳野拓也 . .
(6) . 九州工業大学情報工学研究院. . . . 九州工業大学情報工学府情報工学専攻.
(7)
(8)
(9) .
(10) . . . ! . . . ". 距離 )1 2 3+ 断片 距離 )1+ などの 距離が用途に応じて考案されてきた" これらの距離 は それぞれ マッピングの変種である トップダ 保存 ウンマッピング
(11) )- .+ マッピング$/( 0 )+ 制限マッ ピング )+ ボトムアップマッ ピング )1 2 3+ 断片マッピン グ )1+ の最小コストとして定式化 されている" これらの距離はすべて 時間で計算 可能である )- 1 . +" 本論文では 最も制限された編集距離の一つであり トップダウンマッピングの最小コストであるトップダ ウン距離 )- .+ に着目する" ここで トップダウンマッ ピングとは つの木の根の組と 根からのパスに含ま れるノードの組からなる マッピングであり 常に ボトムアップマッピング以外の上記のマッピングの条 件を満たす )1 2+" 操作的には トップダウン距離は削 除と挿入を葉にしか適用できない編集距離である" そして本論文では 高さ の木 もしくは 二分木のトップダウン距離がある定数 に対し て 時間で計算可能ならば ! ) + に反すること つまり の下ではトップダウン距離は 時間で計算不可能 困難 であることを示す" 木の問題に対する 困難性として ( ら )+ は 部分木同型 について 特に 無順序木 の困難性を扱っている" ただ し )+ における無順序二分木の部分木同型の 困 難性は その証明中 誘導部分木の部分木同型が埋め込. はじめに. . ウェブマイニングにおける #$ 文書や %#$ デー タ および バイオインフォマティクスにおける &'( データや糖鎖データなどにおける木構造データの比較 は データマイニングにおける重要な問題の一つであ る" 本論文では 木構造データを根付きラベル付き順序 木 以後 単に木 と いう として定式化し 木間の距離に着目する" 編集距離 は 最も代表的な木間の距 離である )*+" この編集距離は 置換 削 除 挿入 という編集操作を適用す ることで 一方の木から他方の木へ変換する最小コス トとして定式化される" 編集距離は 先祖子孫関係と兄 弟関係を保存する つの木間のノードの対応関係であ る マッピング 以後 単にマッピン グ という )*+ に対して 可能な マッピ ングの最小コストと一致する )*+" 順序木の編集距離は つの木のノード数の最大値 に対して 時間で 計算可能である ),+" 編集距離は木を比較する際に一般的な尺度である が 応用先によっては一般的過ぎる場合がある" そこ で より構造を考慮した距離として トップダウン
(12) または次数 距離 )- .+ 保存$/( 0 または次数 距離 )+ 制限 または孤立部 分木 距離 )+ ボトムアップ .
(13). .
(14). 連絡先：九州工業大学情報工学研究院知能情報工学研究系 〒 福岡県飯塚市川津 .
(15)
(16)
(17) . -1-.
(18) み部分木の部分木同型となっている箇所があり この ままではこの 困難性は成り立たない" 一方 本 論文のトップダウン距離計算の 困難性は 共通 トップダウン誘導部分木同型と対応するため ( ら )+ の結果よりも強い順序二分木の最大共通トップ ダウン誘導部分木の 困難性を導くことになる". . 当てられている根付き木をラベル付き木 という" 以後 と を同一視する" 本論文では 根 付きラベル付き順序木を単に木という". . . 定義 編集操作 木 の編集操作 を以下のように定義する" 図 は編集操作の直観的な 説明である" ". 準備. 非巡回連結グラフを木 という" 木 4 に対して と をそれぞれ と と表す" ま た のサイズ5 を 単に と表す" さら に を単に と表す" 空の木を で表す" ノード を根 として選んだ木を根付き木 という" 根付き木 の根を と表す" ノード. を根とする根付き木の各ノード に対して から. への一意なパスを で表す" ノード 4 に対して 上のノードを の先祖 という" また に隣接する先祖の ノードを の親 といい で表す" が の親であるとき を の子 といい が の先 祖であるとき を の子孫 という" 本論 文では が の先祖であるとき
(19) と表し
(20) または 4 であるとき と表す" 子を持たないノードを葉 という" 木 のすべ ての葉の集合を で表す" 木 とノード に 対して を根とし の子孫をすべて含む木を を根 とする の完全部分木といい と表す" に対して の辺の数を の高さ といい で表す" また ! を木 の高さ といい で表す" の子の数を の次数 といい で表す" また ! を木 の次数 といい で表す" 特 に 4 となる木 を高さ 木 4 となる木 を二分木 という" 根付き木 に対して の子ノードを とする" このとき において を訪問した後に を再帰的に訪問する走査を の 先行順走査 0 という" 同様に を訪問した後に を訪問する走査を の後行順走査という" 木 に対して 先行順走査で の すべてのノードを訪問した際の順番を 後行順走 査で訪問した際の順番を と表す" のノード と に対して かつ となるとき は の左である もしくは は の右である といい と表す" 順序 が固定された根付き木を順序木 といい そうでない木を無順序木 とい う" 各ノード にアルファベット 6 の要素 が割り. ". -". 置換 7 き換える". のノード のラベルを書. 削除 7 の 親 ¼ を持つノード を削 除し の子を ¼ の子として接続する" このとき 子は の位置に接続し ¼ の子の部分列として 左右順序関係を保存したまま接続する" 挿入 7 削除の逆操作" のノード ¼ の 子の連続部分列の位置にノード を子ノードとし て接続し 連続部分列を の子ノードとして接続 する" 置換. . . v. 削除. . . v. v. 挿入. . . 図. 7. v. . v. w. v v. 木に対する編集操作". を空白8 記号とし 6 4 6
(21) とす る" このとき 編集操作を で表す" ただし 6 6 である" 編集操作として は 4 かつ 4 のときに置換を 4 のときに 削除を 4 のときに挿入を表す" ノード と に 対して を単に と表す" ラベルの対に対して 7 6 6 . をコスト関数 という" コスト関数 は メトリック すなわち 4. . . 6. . 4 4 9 を満たす" 特に 4 9 となるコスト関数 をインデルコスト関数 といい 4 4 となるイ ンデルコスト関数 を単一インデルコスト関数 . . . -13-. . という".
(22) 編集距離 コスト関数 に対して 編集操作. 定義. . 定義 , より トップダウン距離は削除と挿入を葉のみ に適用する編集距離である". 4 のコスト は 4 で与 えられる" また 編集操作の列 4 のコス ト は 4 で与えらえる" このと き 木 と の編集距離 を 以下のように定義する". 部分木 4 と ¼ 4 ¼ ¼ を木と. 定義 し ¼. . 4 . ". は を に 変換するための 編集操作の列 . . ". 編集距離は 以下のマッピングと密接な関係がある )*+". . . 定義 マッピング と を木とする" このとき 任 意の が以下の条件を満たすよう な集合 を と の マッピン グ 以後 単にマッピング と いい と表す". 4 . " -". . . . . 4 . ". ". . . ¾ . . . . 9. ¾. . 9. . 定理. ¾. . . . 木 と に対して
(23) 以下が成り立つ 4 . . . . とし. . 以下の. . とする" トップダウンマッピング
(24) と表す". . . . .
(25).
(26) ) +. ". 入力7 上の 個の 値ベクトルか らなる つのリスト と " 出力7 4 を満たす対 が存在するならば真を返し そうでなけれ ば偽を返す". . . . 入力7 6 上の つの文字列 と " 出力7 文字列編集距離 ". さらに と のトップダウン距離
(27) または次数 距離 を以下のように 定義する". 4 . .
(28) )+. といい. . . . という". つの問題は ! の下で 定数 に対して 時間では計算不可能 困難 である ) +". 以下の条件を満たすような を と の 4. . 困難性. トップダウン距離 木 と に対して . ¼ に対して のとき ¼ となるとき ¼ を の誘導部分 . . 編集距離の変種として 本論文ではトップダウン距離 について議論する" 定義. 任意の に 木 . 木 と の共通部分木はマッピング を用いて特 徴づけることができる" は のノード のうち に含まれないものの集合であることに注意 すると 4 と 4 に対して ¼ 4 4 であり が と の共通部分 木 ¼ 4 ¼ ¼ を含むとき ¼ を と の による 共通部分木 という" し たがって インデルコスト関数における トップダウン マッピングによる共通部分木は 共通トップダウン誘導 部分木である". スト を以下のように定義する" 4. 任意の ¼ に対して
(29) であり
(30) かつ
(31) なる ¼ が存在しないときに ¼ ¼ となるとき を の埋め込み部分 木 という". . に対して を のノードのうち に含まれないものの集合 を のノードのうち に含まれないものの集合とする" このとき のコ . とする". 定義 最大共通部分木 木 と に対して 木 ¼ が と の部分木となるとき ¼ を と の共通部分 木 という" また と の共通部分 木のうち ノード数が最大の木を と の最大共通部 分木 という" さらに つの 木の共通部分木がそれぞれの根を含むとき トップダウ ン
(32) であるという". ". . . 完全部分木は誘導部分木の特別な場合である" 以後 埋 め込み部分木 誘導部分木 完全部分木を単に部分木と もいう". . ". . ". -14-.
(33) と $ の構成方法より自明である" ¾ 補題 4 ならば 4 # で あり
(34) そうでなければ # 9 で ある また
(35) $ 4 # 9 である 証明 と の最小コストのトップダウンマッピン 証明. 本節では これらの 困難問題からトップダウン 距離計算問題へ還元する". . . 定理 定数 に対して 木 と がたとえ高 さ 木としても は の下で 時間では計算不可能である" . . . .
(36) . グは 根から葉までの # 9 - 個の組 ! ! を要素とし そのコストは となる" また 以下の式が成り立つ". 証明 問題 から還元する" 6 上 の文字列 4
(37) 4 に対して 図 の 木 と を考える" ここで の と の は そのノードのラベルを表し 根のラベ ルは ! とする" このとき 明らかに 4 ¾ である". . . . ! ! 4 ) + 4 ) + 4 ! ! 4 ) + 4 ) + 4 ! ! 4 ) + 4 ) + 4 ! ! 4 - ) + 4 ) + 4 . これより 以下の式が成り立つ" . ½. ½. 図. . 7. 定理. . . . . -. ). . それ以外のとき". +4. ). +4. . の証明に用いる木 と ". 4 なので 4 ならば 4 # となり そ うでなければ # 9 となる" . 定理 定数 に対して 木 と がたとえ二分木 としても は の下で 時間では計算不可能である". . さらに $ と の最小コストのトップダウンマッ ピングは 根から葉まで # 9 個の組 ! ! を要素と し そのコストは である" また は の部分 木 !!! に含まれる ! の一つを要素として含まず そのコストは である" ! ! 4 ! ! 4 より $ 4 となる" ゆえに $ 4. . .
(38) . 証明 問題 から還元す る" 証明では ! のみでラベル付けされた木を用い る" また 単一インデルコスト関数をコスト関数として 用いる" を根に持ち の子が左から木 と木 " と なるような木を " で表す" また を根に持ち の子が木 となるような木を で表す" 4 4 とする" お よび の 番目 # の要素を それぞれ ) + および ) + と表す" とする" ) + # に対して 木 を ) + 4 ならば ! ) + 4 ならば ! と して構成する" そして を以下のように構成する". . . . . . . . # 9 - かつ $. 4 1# 9 4 1# 9 ,. . $ 4 !$ !$ !$ !!" 4,. ! $ . 証明 を と の最小コストのトップダウンマッ ピングとする" このとき は と $ のどちらかの ノードと のノードを対応付ける" 4 と仮定する" が と のノードの組 4 を含むならば 補題 と より 9 $ 4 # 9 ,# 9 4 1# 9 と なる" が $ と のノードの組を含むならば 補題 と より 4 $ 9 4 # 9 9 ,# 9 - 4 1# 9 , となる" ゆえに は常に と のノードの組を含み したがって 4 1# 9 が成り立つ". . ように構成する". . と に対して 木 と をそれぞれ と ! と構成する". . . . ¾. 補題 4 ならば であり
(39) そうでなければ である. . . . $ 9 4 # 9 となる". . 4 ! ! ! !!!" # に対して 木 を とする" ) + ) + 4 ならば ! ) + 4 ならば ! として構 成する" そして を以下のように構成する" 4 ! ! ! !!!" さらに $ # を ! とし $ を以下の. 補題. 4. . # 9 . 4,. -15-. . .
(40) 4 と仮定する" が $ と のノードの対 を含むならば 補題 と より 9 $ 4 # 9 9 ,# 9 4 1# 9 , と なる" が と のノードの組を含むならば 補題 と より 4 $ 9 4 # 9 9 ,# 9 - 4 1# 9 , となる" ゆえに は常に $ と のノードの組を含み したがって 4 1# 9 , が成り立つ" ¾. プマッピング )1 2 3+ と $/( 保存マッピング )+ の共 通部分であるボトムアップ $/( 保存マッピングの最小 コストとなり このマッピングは共通完全部分木 共通 ボトムアップ誘導部分木 と対応する" ( ら )+ は 無順序二分木に対する最大共通完全部分木問題の計 算が 困難であることを証明した" この結果が順 序木でも成り立つか否かについて議論することは今後 の課題である". . . 最後に 木 と を以下のように構成する". . 4. 参考文献. ! ! ! ! !! . . . 4 ! ! ! ! !!. . . .
(41) . . . . 証明 を と の最小コストのトップダウンマッピ. 補題 4 となる対 が存在するな らば 1# 9 , となり
(42) 存在 しないならば 4 1# 9 , となる ングとする" このとき は根から葉までの 9 # 9 個の組 ! ! を要素とし そのコストは である" また は任意の に対して と を対応付け る" 4 となる対 が存在するならば 補題 - より 1# 99 1# 9 , 4 1# 9 , となる" 存在しないならば 補題 より 4 1# 9 , 4 1# 9 , と なる" ¾. . . .
(43) .
(44) . ! "#!$"% "&!. ) # #$#* "&#. ".
(45) ' ( . +. ),
(46) -
(47) ., . .
(48)
(49) / 00 0&$& 000. 1. 2
(50) 34 5
(51)
(52) . #. 7
(53) 6 , 7
(54) .
(55) . !. .
(56) .
(57) .
(58) )3
(59) 6 "&&0. 8
(60) 9 .
(61) ':
(62) .
(63) $"+ "&1 7(
(64)
(65) .
(66) . ,. ., ;<.( : ( "&&% %. 3 - .
(67) . : /... ¾. *. 7 )
(68) )3. 定理 - の証明で単一インデルコスト関数を利用して いるので 共通部分木問題に対して以下の系が成り立つ". 0. 系 定数 に対して 木 と がたとえ二分木と しても 最大共通トップダウン誘導部分木は の 下で 時間では計算不可能である". &. . おわりに. ". 本論文では 高さ の木 もしくは 二分木の トップダウン距離は の下で 定数 に対し て 時間では計算不可能 困難 であるこ とを証明した" また の系として 二分木の最大共 通トップダウン誘導部分木の計算も 困難である ことが言える" 節で述べたように トップダウン距離は 編集距離 の最も制限された距離の一つである" 別の最も制限さ れた距離は ボトムアップ 保存距離 $/( 0 である" これは ボトムアッ.
(69). -16-. .
(70) . =. 1""$1++ 0%0. >
(71) . . . '9. *1$*! 0%%. Æ !. '52 & ""$"0 "&&.
(72) !
(73) " ,. )?. +#%$+!# "&&# 5. 7 ,
(74) 6
(75)
(76) !
(77) .. 5 6 1!+$1%1 00#. "
(78) !
(79) '.
(80) . = 8 )?. 1+9#* 00! 7 ,
(81) 6 =
(82) 6 ,
(83) ,
(84) .
(85)
関連したドキュメント
高齢者の性腺機能低下は，その症状が特異的で
基本波を用いる近似はピクセル単位の時間放射能曲線に対しては用いることができる
私は，２ ，３ ，５ ，１ ，４ の順で手をつけたいと思った。私には立体図形を脳内で描くことが難
P‐ \ovalbox{\tt\small REJECT}根倍の不定性が生じてしまう.この他対数写像を用いた議論 (Step 1) でも 1のp‐ \ovalbox{\tt\small REJECT}根倍の不定性が
定可能性は大前提とした上で、どの程度の時間で、どの程度のメモリを用いれば計
児童について一緒に考えることが解決への糸口 になるのではないか。④保護者への対応も難し
奥付の記載が西暦の場合にも、一貫性を考えて、 ［］付きで元号を付した。また、奥付等の数
奥付の記載が西暦の場合にも、一貫性を考えて、 ［］付きで元号を付した。また、奥付等の数
