情報生命科学特別講義III
(10)文法圧縮
阿久津 達也
京都大学 化学研究所
バイオインフォマティクスセンター
講義予定















第1回: 文字列マッチング
第2回: 文字列データ構造
第3回: たたみ込みとハッシュに基づくマッチング
第4回: 近似文字列マッチング
第5回: 配列アラインメント
第6回: 配列解析
第7回: 進化系統樹推定
第8回: 木構造の比較:順序木
第9回: 木構造の比較:無順序木
第10回: 文法圧縮
第11回: RNA二次構造予測
第12回: タンパク質立体構造の予測と比較
第13回: 固定パラメータアルゴリズムと部分k木
第14回: グラフの比較と列挙
第15回: まとめ
文法圧縮とは?
文法圧縮



与えられた文字列を一意に生成する最小の文脈自由
文法を計算(もしくは近似)
例 abcabcabcabc ⇒
S → AA A → BB B →abc
様々な近似アルゴリズム
(下限:定数近似困難)





BISECTION
LZ78
SEQUITUR型
GREEDY型
ほぼ最適
O((n/log n)0.5)近似 [Lehman & Shelat 02]
O((n/log n)2/3)近似 [Lehman & Shelat 02]
O((n/log n)3/4)近似 [Lehman & Shelat 02]
O((n/log n)2/3)近似 [Lehman & Shelat 02]
O(log n)近似
[Charikar et al. 02] [Rytter 02][Sakamoto et al. 09]
文法圧縮


文法のサイズ:規則の右側に現れる文字数の和
abcabcabcabc

サイズ=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)
文法のサイズ=2×(異なる文字列の個数)
再帰の深さが h/2 になるまでに生成される文字列の個数
1  2  22  23   2(log n / 2)  O( n )

最小の文法のサイズを m* とする
 深さ h/2 以上で生成される文字列の長さは、1, 2, 4, …, 2h/2
なので、mk補題より異なる文字列の個数は
m  2m  4m   2
*

*
*
(log n / 2)
m  O(m
*
よって、実行中に生成される異なる文字例の個数は
O( n )  O(m
*
n )  O(m
*
n)
*
n)
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圧縮と文法圧縮の関係 (1)
PTree(G): 「各内部頂点の左には同じラベルの内部頂点がない」
を満たす、文法 G による導出木の根を含む極大な部分木
G-分解: Ptree(G)の葉による w の分割: w=g1・g2…gr
LZ圧縮と文法圧縮の関係 (2)
命題1: |G| ≧ r (r は Ptree(G) による w の分割数)
証明 : G には内部頂点が r-1 個あるが、定義より Ptree(G) の内
部頂点には同じラベルの頂点がない。
よって、A→BC という型の規則が r-1 個存在。
また、A→a という型の規則も少なくとも1個存在。
命題2: 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 に含まれる。
定理1: LZ圧縮による分割数は文法圧縮のサイズの下限となる
ここではチョムスキー標準形のみ考えているが、他の場合も定数倍を除いて同様
O(log2n) 近似アルゴリズム
[Maruyama, Miyagawa, Sakamoto: LNCS 4288, 2006]
アルゴリズム: アイデアと縮約規則
アイデア: Z→XY という型の規則を次々に導入しながら文を縮小。
その際、同じ部分列はほぼ同様の規則に圧縮されるようにする
規則1: Xk (ただし、k≧2)
⇒
左端、および、右端の各2文字を同じ記号に置換。これを繰り返す。
例: aaaaaaaa ⇒ AAAA
aaaaaaaaa ⇒ AAaAA (ただし、A→aa)
規則2: AiAjAk かつ j<i,k
⇒
AjAk (minimal pair)を置換(Ap→ AjAk を新たに導入)
規則3: 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
re pe at
アルゴリズムの説明:
for each maximalrepetitiondo
以下の作業を必要回
applyRule - 1;
数繰り返す。
i  1;
1. 規則1 を適用可能
wh ile(i | w |) do
なものにすべて適用。
2. 規則2、規則3をこ
if w[i..i  1] is minimalor maximalth e n
の順で適用。どちらも
applyRule - 2 or Rule - 3; i  i  2
適用不可であれば、
e lseif w[i  1..i  2] is minimalor maximalth e n
最初の2文字をまとめ
る。これを文字列全体
applyRule - 2 or Rule - 3; i  i  3
に繰り返す。
e lse
(なお、w は毎回、書き
replacew[i..i  1]; i  i  2;
換えられる)
u n tilall pairsin w are different
計算量の解析
補題1: LCAcompress は線形時間で動作
証明:
Repeat ループの各回において、少なくとも w[i..i+1],
w[i+1..i+2] のいずれかは一つの記号に変換される。
よって、ループ1回あたり、w のサイズは 2/3 になる。
よって、repeat ループは O(log n) 回しか実行されない。
1回あたりの実行は O(|w|) 時間で実行可能であるので、
全体の計算時間は
O((1   ( )  )n)  O(n)
2
3
2 2
3
n は w の最初の長さ
近似率の解析 (1)
補題2: (各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 文字以外は同じ文字列に変換される。
近似率の解析 (2)
補題3: 最小の文法の規則数を 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ループ1回あたり、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]
画像データに対する文法圧縮

対象とする文法

4分割型
下図のような、より複
雑な文法にも拡張可
 アルゴリズム:
QUADSECTION


BISECTIONの拡張
近似率の解析

補題:サイズ g の文法により生成される画像
中のサイズ k×h の部分画像で異なるものは
高々 2ngk 個 (n はもとの画像の最大辺。k≧h)


定理
QUADSECTION
の近似率は O(n4/3)
d次元の場合は
d 2 /(d+1)
O(n
) 近似
でも、画像をラスタースキャンして文字列に
変換して圧縮した方が、より良い近似精度
近似率の解析

再帰の深さが (2/3) log n になるまでに生成される規則の個数
( 23 log n)
1  4  4  4   4
2

3
 O(n
)
最小の文法のサイズを g* とする
 深さ (2/3) log n 以上で生成される画像のサイズは、1, 2×2,
4×4, … なので、mk補題より異なる画像の個数は
( 23 log n)
2n  g  2n  2g  2n  4g   2n  2
*

4/ 3
*
*
g *  O( g *n4 / 3 )
よって、実行中に生成される異なる規則の個数
O(n
4/ 3
)  O( g n
* 4/ 3
)  O( g n
* 4/ 3
)
木の文法圧縮
[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


特徴:枝にラベル、枝を木構造に書き換える
タグ付き木



1個の葉にのみタグ(印): 枝の両端 ⇔ 根とタグ
タグつき葉は、後で他の木の根と融合
生成規則:タグなし枝→タグなし木
タグなし枝
タグあり枝
タグあり枝→タグあり木
EOTG: 例1
文法
導出過程
文法
導出過程
EOTG: 例2
文法
導出過程
オイラー文字列



木を深さ優先探索
探索した順に頂点のラベルを並べる
ただし、戻る時のラベルは A の様に区別する
命題: T1 と T2 が同型 iff es(T1)=es(T2)
ただし、根のラベルは無視
SEOTG: Simple Elementary Ordered Tree Grammar


(S)EOTGの規則はオイラー文字列で表現可
タグ ⇔ x : x は部分木に置換される
EOTG, SEOTGの性質
文法のサイズ: 右辺に現れる木の枝数の合計
補題: サイズ m のEOTGは、サイズ 3m 以下の
SEOTGに変換可能
定理: 与えられた木がEOTGから生成可能かどうか
は多項式時間で判定可能
圧縮においては、1個の木のみを生成する文法のみを
対象 ← 与えられた木を圧縮したい
オイラー文字列を作ってから文法圧縮すると、必ずしも木文法は得られない
圧縮アルゴリズム:
TREE-BISECTION
TREE-BISECTION (1)

木を再帰的に分割
同型な部分木が出てきたら同じラベルを割り当てる

T が枝 A のみの場合



T がタグなし木の場合



A→a という規則を追加して終了 (a は枝 A のラベル)
T を T1, T2 に分割。ただし、|T1|≦(1/2)|T|+1、かつ、 T1 はタグつき
T2 を T3, T4 に分割。ただし、|T3|, |T4|≦(3/4)|T|+1
T がタグつき木の場合



T を T1, T2 に分割。ただし、|T1|≦(1/2)|T|+1、かつ、 T1 はタグつき
T2 を T3, T4 に分割。 T3, T4 のいずれかのみがタグつき木
T3 がタグつき木なら、 |T3|≦(1/2)|T|+1
(逆も同様)
(|T4|は制約されないが、タグなし木なので次ステップで必ず小さくなる)
多項式時間で動作するのは、ほぼ明らか
TREE-BISECTION (2)
枝1本のみ
タグなし木
タグあり木
TREE-BISECTIONの解析
mk-補題(1)
mk-補題 [Lehman & Schelat 02]
文字列 s がサイズ m の CFG により生成されたとすると、
s に現れる長さ k の文字列のうち、異なるものは mk 個以下。
オイラー文字列を用いて順序木に拡張
補題: 木 T がサイズ m の EOTG により生成されたとすると、
es(T) に現れる長さ k の文字列のうち、異なるものは 2mk 個以下。
証明: サイズ m のEOTG は、サイズ 2m の CFG に変換可能
 例:
AxA  BB CxC  A  BB C A  C
mk-補題(2)
命題:m*を最小EOTGのサイズとすると、アルゴリズム中で現れる
サイズ k の木の種類は高々
2m* (2k  2) 
( 2 k  2) 1
*
*
(
2
m
k
)(
2
m
((2k  2)  k1 ))

1
k1 1
証明: サイズ k の木 ⇒ 長さ 2k-2 の文字列。ただし、途中にタグが
入る場合は、長さ k1 と 長さ (2k-2)-k1 の文字列の組み合わせ。
その他の補題
補題: 大きさ n の木を生成するEOTGのサイズは
(logn)
補題: TREE-BISECTION の再帰の深さは O(log n)
補題: 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α 以下の木の種類は
( 2 k  2 ) 1
 *

*
*
* 2
4
2
m
(
2
k

2
)

(
2
m
k
)(
2
m
((
2
k

2
)

k
))

O
((
m
)

n
)



1
1 
k 1 
k1 1

n

よって、アルゴリズム中に現れる異なる木の種類は
O((m )  n
* 2

4
1
n
log n)
α=1/6, m* が O(n1/6) とおいて
O(m  n
*
( 5 / 6)
n
( 5 / 6)
log n)
(次数制約つき)無順序木への拡張

TREE-BISECTIONの変更点
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]

画像データ、木構造データの近似率の改善は研究課題
ダウンロード

文法圧縮 - 京都大学