九州大学集中講義2010

集中講義（九州大学数理学研究院）
バイオ構造データに対する数理モデルと
アルゴリズム（３）
＋数理談話会
木構造および画像データの文法圧縮
阿久津達也
京都大学化学研究所
バイオインフォマティクスセンター
内容







背景
文法圧縮
EOTG (Elementary Ordered Tree Grammar)
圧縮アルゴリズム TREE-BISECTION
アルゴリズムの解析
画像データの文法圧縮
結論と課題
[Akutsu, Tech. Rep., SIGFPAI, 2010]
[Hayashida et al., AST 2010]
背景
研究の目的

人間の設計図


意外に少ない



パソコンゲームより少ないかも
細胞は60兆個もある
ここに全てが書かれているはず



３２億文字 ⇒ CD-ROM 1枚
臓器、脳、顔の作り方、知能、本能
でも、どう書かれているか、ほとんどわかっていない
人間の設計図がCD-ROM 1枚

データ圧縮の数理的原理があるはず！
文法圧縮
文法圧縮



与えられた文字列を一意に生成する最小の文脈自由
文法を計算（もしくは近似）
例 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
文法圧縮の木構造への拡張


困難性の証明 [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：例２
文法
導出過程
オイラー文字列



木を深さ優先探索
探索した順に頂点のラベルを並べる
ただし、戻る時のラベルは 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から生成可能かどうか
は多項式時間で判定可能
圧縮においては、１個の木のみを生成する文法のみを
対象 ← 与えられた木を圧縮したい
圧縮アルゴリズム：
TREE-BISECTION
BISECTION



[Lehman & Schelat 2002]
文字列を2iとなる場所で再帰的に分割
分割の度に生成規則を追加
同じ文字列が出てきたら同じラベルを割り当てる
mk補題

サイズ m の文法により生成される文字列中
の長さ k の部分列で異なるものは高々 mk 個
略証：各非終端記号により始めてカバーされる
長さ k の部分列の個数は高々 k 個。全部で
高々 m 個の規則があるので補題が成立。
灰色の配列で S により始めてカ
バーされるのは k 個。
それ以外は T1 か T2 によりカバ
ーされる。
BISECTIONの解析



簡単のため、もとの文字列の長さを n=2h と仮定（h=log n）
文法のサイズ＝２×（異なる文字列の個数）
再帰の深さが h/2 になるまでに生成される文字列の個数
1  2  22  23   2(log n / 2)  O( n )

最小の文法のサイズを m* とする
 深さ h/2 以上で生成される文字列の長さは、1, 2, 4, …, k/2
なので、mk補題より異なる文字列の個数は
m  2m  4m   2
*

*
*
(log n / 2)
m  O(m
*
よって、実行中に生成される異なる文字例の個数は
O( n )  O(m
*
n )  O(m
*
n)
*
n)
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)
枝１本のみ
タグなし木
タグあり木
アルゴリズムの解析
mk-補題（１）
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-補題（２）
命題：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)近似
画像データの文法圧縮
画像データに対する文法圧縮

対象とする文法

４分割型
下図のような、より複
雑な文法にも拡張可
 アルゴリズム：
QUADSECTION


BISECTIONの拡張
近似率の解析

補題：サイズ g の文法により生成される文字
列中のサイズ k×h の部分画像で異なるもの
は高々 2ngk 個（n はもとの画像の最大辺。k≧h）


定理
QUADSECTION
の近似率は O(n4/3)
d次元の場合は
d 2 /(d 1)
O(n
) 近似
結論と課題
結論





CFGを順序木に拡張した EOTG を提案
与えれた木を生成するEOTG計算アルゴリズム
TREE-BISECTION を提案
O(n5/6)近似であることを証明
無順序木への拡張
画像圧縮アルゴリズムQUADSECTIONを提案
今後の課題





TREE-BISECTION の改良
無順序木の場合の次数制約の解除
文字列に対する他の近似技法の木への応用
木以外のグラフ構造に対する（近似率の保証
つき）文法圧縮アルゴリズムの開発
神経系や循環器系ネットワークの圧縮

Download Report