Presentation is loading. Please wait.

Presentation is loading. Please wait.

集中講義(九州大学数理学研究院) バイオ構造データに対する数理モデルと アルゴリズム(3) + 数理談話会 木構造および画像データの文法圧縮

Similar presentations


Presentation on theme: "集中講義(九州大学数理学研究院) バイオ構造データに対する数理モデルと アルゴリズム(3) + 数理談話会 木構造および画像データの文法圧縮"— Presentation transcript:

1 集中講義(九州大学数理学研究院) バイオ構造データに対する数理モデルと アルゴリズム(3) + 数理談話会 木構造および画像データの文法圧縮
集中講義(九州大学数理学研究院) バイオ構造データに対する数理モデルと アルゴリズム(3) + 数理談話会 木構造および画像データの文法圧縮 阿久津 達也 京都大学 化学研究所 バイオインフォマティクスセンター

2 内容 背景 文法圧縮 EOTG (Elementary Ordered Tree Grammar)
圧縮アルゴリズム TREE-BISECTION アルゴリズムの解析 画像データの文法圧縮 結論と課題 [Akutsu, Tech. Rep., SIGFPAI, 2010] [Hayashida et al., AST 2010]

3 背景

4 研究の目的 人間の設計図 意外に少ない ここに全てが書かれているはず 人間の設計図がCD-ROM 1枚 32億文字 ⇒ CD-ROM 1枚
パソコンゲームより少ないかも 細胞は60兆個もある ここに全てが書かれているはず 臓器、脳、顔の作り方、知能、本能 でも、どう書かれているか、ほとんどわかっていない 人間の設計図がCD-ROM 1枚 データ圧縮の数理的原理があるはず!

5 文法圧縮

6 文法圧縮 与えられた文字列を一意に生成する最小の文脈自由文法を計算(もしくは近似) 例 abcabcabcabc ⇒
S → AA A → BB B →abc   様々な近似アルゴリズム        (下限:定数近似困難) BISECTION O((n/log n)0.5)近似 [Lehman & Shelat 02] LZ O((n/log n)2/3)近似 [Lehman & Shelat 02] SEQUITUR型 O((n/log n)3/4)近似 [Lehman & Shelat 02] GREEDY型    O((n/log n)2/3)近似 [Lehman & Shelat 02] ほぼ最適      O(log n)近似 [Charikar et al. 02] [Rytter 02][Sakamoto et al. 09]

7 文法圧縮 文法のサイズ:規則の右側に現れる文字数の和 abcabcabcabc S → AA A → BB B →abc サイズ=12
     S → abcabcabcabc サイズ=8      S → AA A → abcabc サイズ=7 (最小) S → AA A → BB B →abc  

8 文法圧縮の木構造への拡張 本研究 困難性の証明 [Yamgata et al. 03][Maneth & Bussato 04]
ヒューリスティックなアルゴリズム Variable Replacement Grammar [Yamagata et al. 03] Tree Transducer [Maneth & Bussato 04] TCGA algorithm [Murakami et al. 08] 近似率導出の困難性 木文法の定義に依存: 簡単すぎても難しすぎても不可 本研究 EOTG (Elementary Ordered Tree Grammar) の提案 CFG を縦横両方に拡張 BISECTION型の O(n5/6)近似アルゴリズム 順序木、無順序木の両方に対応可能

9 EOTG Elementary Ordered Tree Grammar

10 EOTG: Elementary Ordered Tree Grammar
特徴:枝にラベル、枝を木構造に書き換える タグ付き木 1個の葉にのみタグ(印): 枝の両端 ⇔ 根とタグ タグつき葉は、後で他の木の根と融合 生成規則:タグなし枝→タグなし木  タグあり枝→タグあり木 タグなし枝 タグあり枝

11 EOTG: 例1 文法 導出過程 文法 導出過程

12 EOTG: 例2 文法 導出過程

13 オイラー文字列 木を深さ優先探索 探索した順に頂点のラベルを並べる ただし、戻る時のラベルは の様に区別する
ただし、戻る時のラベルは の様に区別する 命題: T1 と T2 が同型 iff es(T1)=es(T2) ただし、根のラベルは無視

14 SEOTG: Simple Elementary Ordered Tree Grammar
タグ ⇔ x :  x は部分木に置換される

15 EOTG, SEOTGの性質 文法のサイズ: 右辺に現れる木の枝数の合計
文法のサイズ: 右辺に現れる木の枝数の合計 補題: サイズ m のEOTGは、サイズ 3m 以下の SEOTGに変換可能 定理: 与えられた木がEOTGから生成可能かどうか は多項式時間で判定可能 圧縮においては、1個の木のみを生成する文法のみを対象  ← 与えられた木を圧縮したい

16 圧縮アルゴリズム: TREE-BISECTION

17 BISECTION [Lehman & Schelat 2002]
分割の度に生成規則を追加 同じ文字列が出てきたら同じラベルを割り当てる

18 mk補題 サイズ m の文法により生成される文字列中の長さ k の部分列で異なるものは高々 mk 個
略証:各非終端記号により始めてカバーされる長さ k の部分列の個数は高々 k 個。全部で高々 m 個の規則があるので補題が成立。 灰色の配列で S により始めてカバーされるのは k 個。 それ以外は T1 か T2 によりカバーされる。

19 BISECTIONの解析 簡単のため、もとの文字列の長さを n=2h と仮定(h=log n) 文法のサイズ=2×(異なる文字列の個数)
最小の文法のサイズを m* とする 深さ h/2 以上で生成される文字列の長さは、1, 2, 4, …, k/2   なので、mk補題より異なる文字列の個数は よって、実行中に生成される異なる文字例の個数は

20 TREE-BISECTION (1) 木を再帰的に分割 同型な部分木が出てきたら同じラベルを割り当てる T が枝 A のみの場合
A→a という規則を追加して終了 (a は枝 A のラベル) T がタグなし木の場合 T を T1, T2 に分割。ただし、|T1|≦(1/2)|T|+1、かつ、 T1 はタグつき T2 を T3, T4 に分割。ただし、|T3|, |T4|≦(3/4)|T|+1 T がタグつき木の場合 T2 を T3, T4 に分割。 T3, T4 のいずれかのみがタグつき木 T3 がタグつき木なら、 |T3|≦(1/2)|T|+1  (逆も同様) (|T4|は制約されないが、タグなし木なので次ステップで必ず小さくなる) 多項式時間で動作するのは、ほぼ明らか

21 TREE-BISECTION (2) 枝1本のみ タグなし木 タグあり木

22 アルゴリズムの解析

23 mk-補題(1) mk-補題 [Lehman & Schelat 02] 文字列 s がサイズ m の CFG により生成されたとすると、 s に現れる長さ k の文字列のうち、異なるものは mk 個以下。 オイラー文字列を用いて順序木に拡張 補題: 木 T がサイズ m の EOTG により生成されたとすると、 es(T) に現れる長さ k の文字列のうち、異なるものは 2mk 個以下。 証明: サイズ m のEOTG は、サイズ 2m の CFG に変換可能 例:

24 mk-補題(2) 命題:m*を最小EOTGのサイズとすると、アルゴリズム中で現れる サイズ k の木の種類は高々
証明: サイズ k の木 ⇒ 長さ 2k-2 の文字列。ただし、途中にタグが入る場合は、長さ k1 と 長さ (2k-2)-k1 の文字列の組み合わせ。

25 その他の補題 補題: 大きさ n の木を生成するEOTGのサイズは 補題: TREE-BISECTION の再帰の深さは
補題: TREE-BISECTION の 同じ深さの再帰レベルに現れる 木の枝の数の合計は n-1 以下 証明: TREE-BISECTION は もとの木を edge disjoint な木 に分解

26 定理: TREE-BISECTION の近似率は O(n5/6)
同じ再帰レベルに現れるサイズnα +1以上の木の個数は (n-1)/nα < n1-α 以下 アルゴリズム中に現れるサイズnα +1以上の木の個数は  O(n1-α log n) サイズ nα 以下の木の種類は よって、アルゴリズム中に現れる異なる木の種類は α=1/6, m* が O(n1/6) とおいて

27 (次数制約つき)無順序木への拡張 TREE-BISECTIONの変更点 EOTGの変更点 ⇒ O(n5/6)近似
T2 を、r(T2) と wj の子孫からなる部分木(j=1,…,h)に分解 順序木の同型性判定を無順序木の同型性判定に置き換え ⇒ 入力木は子の順序に関係なく、一意に分解される EOTGの変更点 子の順序を無視    e.g., (IIIA)=(IIIB) ⇒ O(n5/6)近似

28 画像データの文法圧縮

29 画像データに対する文法圧縮 対象とする文法 下図のような、より複雑な文法にも拡張可 アルゴリズム: QUADSECTION 4分割型
BISECTIONの拡張

30 近似率の解析 補題:サイズ g の文法により生成される文字列中のサイズ k×h の部分画像で異なるものは高々 2ngk 個  (n はもとの画像の最大辺。k≧h) 定理  QUADSECTION  の近似率は O(n4/3) d次元の場合は            近似

31 結論と課題

32 結論 今後の課題 CFGを順序木に拡張した EOTG を提案 与えれた木を生成するEOTG計算アルゴリズム
  TREE-BISECTION を提案 O(n5/6)近似であることを証明 無順序木への拡張 画像圧縮アルゴリズムQUADSECTIONを提案 今後の課題 TREE-BISECTION の改良 無順序木の場合の次数制約の解除 文字列に対する他の近似技法の木への応用 木以外のグラフ構造に対する(近似率の保証   つき)文法圧縮アルゴリズムの開発 神経系や循環器系ネットワークの圧縮


Download ppt "集中講義(九州大学数理学研究院) バイオ構造データに対する数理モデルと アルゴリズム(3) + 数理談話会 木構造および画像データの文法圧縮"

Similar presentations


Ads by Google