阿久津 達也 京都大学 化学研究所 バイオインフォマティクスセンター

Presentation on theme: "阿久津 達也 京都大学 化学研究所 バイオインフォマティクスセンター"— Presentation transcript:

1 阿久津 達也 京都大学 化学研究所 バイオインフォマティクスセンター
情報生命科学特別講義III （10）文法圧縮 阿久津　達也 京都大学　化学研究所 バイオインフォマティクスセンター

2 講義予定 第１回: 文字列マッチング 第２回： 文字列データ構造 第３回： たたみ込みとハッシュに基づくマッチング
第１回:　文字列マッチング 第２回：　文字列データ構造 第３回：　たたみ込みとハッシュに基づくマッチング 第４回：　近似文字列マッチング 第５回：　配列アラインメント 第６回：　配列解析 第７回：　進化系統樹推定 第８回：　木構造の比較：順序木 第９回：　木構造の比較：無順序木 第１０回：　文法圧縮 第１１回：　RNA二次構造予測 第１２回：　タンパク質立体構造の予測と比較 第１３回：　固定パラメータアルゴリズムと部分k木 第１４回：　グラフの比較と列挙 第１５回：　まとめ

3 文法圧縮とは？

4 文法圧縮 与えられた文字列を一意に生成する最小の文脈自由文法を計算（もしくは近似） 例 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]

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

6 BISECTIONアルゴリズム 文字列を2iとなる場所で再帰的に分割 分割の度に生成規則を追加 同じ文字列が出てきたら同じラベルを割り当てる

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

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

9 LZ法と文法圧縮との関係 [Rytter: Theoret. Comp. Sci. 302, 2003]

10 LZ圧縮 圧縮アルゴリズム （ 入力： w=w[1…n] 出力: w=f1・f2…fk ） f1←w[1] とし、i=2 から以下を繰り返す
fi を f1・f2…fi-1 の最長の部分列（かつ、fi・fi+1…fkの接頭辞）とする 　　　（無い場合には fi は fi・fi+1…fk　の最初の文字） 例 w=abaababaabaab ⇒ f1・f2・ f3・f4 ・f5・f6 =a・b・a・aba・baaba・ab

11 LZ圧縮と文法圧縮の関係 （１） PTree(G): 「各内部頂点の左には同じラベルの内部頂点がない」 を満たす、文法 G による導出木の根を含む極大な部分木 G-分解： Ptree(G)の葉による w の分割: w=g1・g2…gr

12 LZ圧縮と文法圧縮の関係 （2） 命題１： |G| ≧ r (r は Ptree(G) による w の分割数） 証明 : G には内部頂点が r-1 個あるが、定義より Ptree(G) の内部頂点には同じラベルの頂点がない。 よって、A→BC という型の規則が r-1 個存在。 また、A→a という型の規則も少なくとも1個存在。 命題２： r ≧ k 証明 : i についての帰納法で | g1・g2…gi |≦|f1・f2…fi | を示す。 LZ圧縮では各時点で最長の接頭辞を選んでいるので、 | g1・g2…gi |=|f1・f2…fi | であれば | gi+1 |≦|fi+1 | が成立。 そうでなくても、 gi+1 は f1・f2…fi の部分列か、 gi+1 の接尾辞で f1・f2…fi に含まれない部分は fi+1 に含まれる。 定理１: LZ圧縮による分割数は文法圧縮のサイズの下限となる ここではチョムスキー標準形のみ考えているが、他の場合も定数倍を除いて同様

13 O(log2n) 近似アルゴリズム [Maruyama, Miyagawa, Sakamoto: LNCS 4288, 2006]

14 アルゴリズム： アイデアと縮約規則 アイデア： Z→XY という型の規則を次々に導入しながら文を縮小。 その際、同じ部分列はほぼ同様の規則に圧縮されるようにする 規則１：　Xk （ただし、k≧2）　　　⇒ 　左端、および、右端の各2文字を同じ記号に置換。これを繰り返す。 　例： aaaaaaaa ⇒ AAAA 　　　　 aaaaaaaaa ⇒ AAaAA （ただし、A→aa） 規則２：　AiAjAk かつ j<i,k 　　⇒ 　AjAk (minimal pair)を置換（Ap→ AjAk を新たに導入） 規則３：　AiAjAkAh かつ （i <j<k<h or i>j>k>h）かつ hlca(j,k)>hlca(i,j), hlca(k,h) 　　　　　　　　⇒　　AjAk （maximal pair）を別の記号に置換 hlca(i,j): すべての終端記号、非終端記号を葉とする完全二分木における 　　i と j の共通祖先で最も下にある頂点（lowest common ancestor）の高さ 途中で出てくる記号の場所もあらかじめ用意しておく（全部で n 以下） hlca(i,j) の高さは 1+log n 以下 hlca(i,j) ≠ hlca(j,k) が必ず成立　(i<j<k もしくは i>j>k で、二分木なので）

15 アルゴリズム： LCAcompress アルゴリズムの説明： 以下の作業を必要回数繰り返す。 1. 規則1 を適用可能なものにすべて適用。 2. 規則2、規則3をこの順で適用。どちらも適用不可であれば、最初の2文字をまとめる。これを文字列全体に繰り返す。 （なお、w は毎回、書き換えられる）

16 計算量の解析 補題１： LCAcompress は線形時間で動作 証明： Repeat ループの各回において、少なくとも w[i..i+1], w[i+1..i+2] のいずれかは一つの記号に変換される。 よって、ループ1回あたり、w のサイズは 2/3 になる。 よって、repeat ループは O(log n) 回しか実行されない。 １回あたりの実行は O(|w|) 時間で実行可能であるので、全体の計算時間は n は w の最初の長さ

17 近似率の解析　（１） 補題２： （各repeatループにおいて） w[i1..j1]= w[i2..j2] とする（j1<i2）と、ある k ≦ c log n が存在し、 w[i1+k..j1-k] と w[i2+k..j2-k] は同じ文字列に変換される 略証： w[i1..j1] が apβbq というパターンをしていた場合、β部分は同じ文字列に変換され、ap, bq もそれぞれ高々2文字を除いては同じ文字列に変換される（k=2）。 それ以外の場合、hlca(i,j) の高さは 1+log n 以下であるので、c log n 以上の長さの文字列は必ず、minimal かmaximal な部分列を含むはずである。よって、最初と最後の c log n 文字以外は同じ文字列に変換される。

18 近似率の解析　（２） 補題３： 最小の文法の規則数を gOPT とすると、LCAcompress は O(gOPT log2n)サイズの文法を出力 略証： w=f1・f2…fk を入力 w のLZ分解とする（k≦gOPT）。 fi は f1・f2…fi-1 の部分文字列か |fi|=1であるので、補題2より、 fi を変換するのに新たに導入された規則はO(log n) 個のみである。 よって、repeatループ１回あたり、O(k・log n) 個の規則が導入される。 ループは O(log n)回実行されるので、LCAcompress により導入される規則の個数は O(k・log2n)≦ O(gOPT log2n)。 定理： 最小の文法の規則数を gOPT とすると、LCAcompress は線形時間で O(gOPT log2n)サイズの文法を出力

19 画像データの文法圧縮 [Hayashida et al.: Integrated Comp.-Aided. Eng. 2012]

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

21 近似率の解析 補題：サイズ g の文法により生成される画像中のサイズ k×h の部分画像で異なるものは高々 2ngk 個　　（n はもとの画像の最大辺。k≧h） 定理 　QUADSECTION 　の近似率は O(n4/3) d次元の場合は 　　 　　　　　　　 近似 でも、画像をラスタースキャンして文字列に 変換して圧縮した方が、より良い近似精度

22 近似率の解析 再帰の深さが (2/3) log n になるまでに生成される規則の個数 最小の文法のサイズを g* とする
深さ (2/3) log n 以上で生成される画像のサイズは、1, 2×2, 4×4, … なので、mk補題より異なる画像の個数は よって、実行中に生成される異なる規則の個数

23 木の文法圧縮 [Akutsu: Inf. Proc. Lett. 2010]

24 文法圧縮の木構造への拡張 本研究 困難性の証明 [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)近似アルゴリズム 順序木、無順序木の両方に対応可能

25 EOTG Elementary Ordered Tree Grammar

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

27 EOTG： 例１ 文法 導出過程 文法 導出過程

28 EOTG： 例２ 文法 導出過程

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

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

31 EOTG, SEOTGの性質 文法のサイズ： 右辺に現れる木の枝数の合計
文法のサイズ：　右辺に現れる木の枝数の合計 補題： サイズ m のEOTGは、サイズ 3m 以下の SEOTGに変換可能 定理： 与えられた木がEOTGから生成可能かどうか は多項式時間で判定可能 圧縮においては、１個の木のみを生成する文法のみを対象　　←　与えられた木を圧縮したい オイラー文字列を作ってから文法圧縮すると、必ずしも木文法は得られない

32 圧縮アルゴリズム： TREE-BISECTION

33 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|は制約されないが、タグなし木なので次ステップで必ず小さくなる） 多項式時間で動作するのは、ほぼ明らか

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

35 TREE-BISECTIONの解析

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

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

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

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

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

41 まとめ 補足 文法圧縮： 入力データを一意に生成する最小文法の近似 文字列の文法圧縮 画像データの文法圧縮： 四分割法（二分割法の拡張）
文法圧縮：　入力データを一意に生成する最小文法の近似 文字列の文法圧縮 二分割法、LZ圧縮との関連、LCAを用いた圧縮 画像データの文法圧縮： 四分割法（二分割法の拡張） 木構造データの文法圧縮： 二分割法の拡張 補足 文字列の文法圧縮については最適に近い近似が可能 　　　　　　 　　[Rytter: Theoret. Comp. Sci. 2003], [Charikar et al.: IEEE Trans. Inf. Theory 2005] 文法圧縮した文字列に対する効率的な検索なども可能 　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　 [Bille et al.: Proc. SODA 2011] 画像データ、木構造データの近似率の改善は研究課題