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

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

文法圧縮とは？

文法圧縮 与えられた文字列を一意に生成する最小の文脈自由文法を計算（もしくは近似） 例 abcabcabcabc ⇒ S → AA A → BB B →abc　　 様々な近似アルゴリズム　　　　　　　　（下限：定数近似困難） BISECTION O((n/log n)0.5)近似 [Lehman & Shelat 02] LZ78 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]

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

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

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

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

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

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

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

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圧縮による分割数は文法圧縮のサイズの下限となる ここではチョムスキー標準形のみ考えているが、他の場合も定数倍を除いて同様

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

アルゴリズム： アイデアと縮約規則 アイデア： 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 で、二分木なので）

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

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

近似率の解析　（１） 補題２： （各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 文字以外は同じ文字列に変換される。

近似率の解析　（２） 補題３： 最小の文法の規則数を 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)サイズの文法を出力

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

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

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

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

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

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

EOTG Elementary Ordered Tree Grammar

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

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

EOTG： 例２ 文法 導出過程

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

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

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

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

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

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

TREE-BISECTIONの解析

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

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

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

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

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

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