6/11

配列解析アルゴリズム特論 渋谷
圧縮
渋谷
東京大学医科学研究所ヒトゲノム解析センター
（兼）情報理工学系研究科コンピュータ科学専攻
http://www.hgc.jp/~tshibuya
本日の話題
配列解析アルゴリズム特論 渋谷
文字列圧縮アルゴリズムのいろいろ
統計的手法
Huffman code
Tunstall
Golomb
Arithmetic code
PPM
辞書的手法
LZ77, LZ78, LZW
Block sorting
Sequitur
接尾辞配列の圧縮
圧縮とは
配列解析アルゴリズム特論 渋谷
2種類の戦略
Lossless圧縮： 完全に復元可能 （本講義）
Lossy圧縮: 画像などで、完全に復元できなくてもよい。
何を圧縮するか？
本講義では文字列が対象
情報源のモデルを考える必要性
何故圧縮できるか？
情報に「重複」があるから
情報源のエントロピー
モデル
A 32%
C 22%
G 15%
T 31%
ATGCCGTAATAACGATCAATACTAGCC...
出力例
エントロピーとは （おそらく学部の復習？）
配列解析アルゴリズム特論 渋谷
 情報「量」にあるべき性質
 非負
 確率が小さい事象は「びっくり度」が大きい
 足し算できる
 I(p·q) = I(p) + I(q)
 そんなわけで情報量は
イチローがヒットをうつ： 0.372
松井がヒットをうつ：
0.299
比較
 I(p) = − log2(p)
 単位は「ビット」
 確率 0.5 の事象は１ビットで表現可能！
エントロピー
 エントロピー
 情報量の期待値
1
 H(p1, p2, p3, ... , pn) = − Σpi log pi
 性質
 pi =1ならばH=0
 一番Hが高いのはpi =1/nのとき
 情報源に対する圧縮率の期待値の下限
 圧縮率はエントロピーに近づくと嬉しい
 「正しい」情報源のモデルを考えることも重要
 モデルによってはエントロピーの計算自体が難しいことも
0
片方の確率
1
２つの事象に対する
エントロピー
関連した２つの情報源のエントロピーの解析
配列解析アルゴリズム特論 渋谷
同時に２つの事象A, Bがあるとする
H(A,B) = −Σp(ai,bi) log p(ai, bi)
するとその性質
ATGCCT...
∈ {ai }n
CTTGGA...
∈ {bi }n
こんなかんじ
H(A,B) = H(B,A)
H(A), H(B) ≤ H(A,B) ≤ H(A) + H(B)
関連のある質問を２つするのは損
A: ヒットを打った
B: ヒットを打たなかった
T/F
T/F
情報としては同じなのでH(A,B) = H(A) = H(B)
A: ヒットを打った
B: 桶屋が儲かった
T/F
T/F
ほぼ関係ないのでH(A,B) ~H(A)+H(B)
A: ヒットを打った
B: 勝った
T/F
T/F
その中間
条件付エントロピー
配列解析アルゴリズム特論 渋谷
Aがaiの時のBのエントロピー
H(B|ai) = −Σjp(ｂj|ai) log p(ｂj|ai)
条件付エントロピーはその期待値
0: 完全に相関
H(B|A) = −Σi,jp(ai,bj) log p(ｂj|ai)
性質
H(A,B) = H(A) + H(B|A)
H(B|A) ≥ 0
H(B) ≥ H(B|A)
下２つは H(A), H(B) ≤ H(A,B) ≤ H(A) + H(B) というエントロピー
の性質から導くことができる
相互情報量
I(A;B) = H(B) − H(B|A) = H(A) − H(A|B)
どれくらい情報に重なりがあるか？
Relative Entropy (Kullback-Leibler Distance)
配列解析アルゴリズム特論 渋谷
2つの確率事象の差異を見る指標
本当の情報源はPなのに、何を間違えたかQだと思ったとき
に（たとえばそう思って圧縮したときに）損をする量
P, Qを逆にした時の値は異なる
 対象性が必要な場合は両者の平均を距離として扱うことも多い
» ただし、そこに理論的な正当性があるわけではないことに注意
必ず正の値をとる
 情報源の推定を間違えないことが、最高の圧縮率を達成する条件
p( x )
D ( p || q) = ∑ p( x ) log
q( x )
x
通信路・圧縮超入門
配列解析アルゴリズム特論 渋谷
圧縮
0.9
0
0
情報の出し手
情報の受け手
0.1
1
1
情報量の少ない文章（０ばっかり、など）
を送るのはもったいない
情報量が1000ビットであれば、1000ビット送るだけでよい筈！→Huffman符号など
 通信路符号化
0
情報の出し手
1
0.9
0.1
0.1
0.9
0
情報の受け手
1
間違いが起こる通信路でできる
だけ正確に情報を送るには？
両サイドの相互情報量分のビット数は送ることができる筈！→Hamming符号など
２種類の戦略
配列解析アルゴリズム特論 渋谷
統計的手法
文字の使用頻度の偏りに基づく
Huffman code
Tunstall
Golomb
Arithmetic code
PPM
...
辞書的手法
「よく出てくる語」を辞書化する
LZ77, LZ78, LZW
Block sorting
Sequitur
...
Huffman Code (1)
配列解析アルゴリズム特論 渋谷
考え方
確率の高い事象は短いコードで表す
文字のビット数は変更可能
Model
A
C
G
T
12.5%
12.5%
25%
50%
4文字なので普通に
表現すれば2ビットで
1文字を表現できる
entropy = 1.75bit
Code
100
101
11
0
理想的な場合
期待値としては1文字あたり
1.75ビットで表現される
→圧縮できた（しかも理想的）
Huffman Code (2)
配列解析アルゴリズム特論 渋谷
計算時間： O(s log s)
s: アルファベットサイズ
ヒープを用いる
888
0
1
381
507
0
0
1
283
0
C
155
205
224
1
128
H
118
106
91
1
0
F
0
1
B
21
176
1
0
0
57
J
36
D
1
0
G
1
49
E
47
I
85
1
A
44
頻度
一番頻度の低い２つをまとめる
Huffman Code (3)
配列解析アルゴリズム特論 渋谷
性質
Prefix code (Instantaneous code)
あるコードが他のコードのprefixになっていない
文字のコード化だけで圧縮する場合、最適
エントロピー的にもいい線を行っている
H(X)≦L＜H(X)+1
 確率piの長さが
log(1 / pi )以下となっているため
k文字まとめれば、
 H(X)≦L＜H(X)+1/k
AAAA
AAAC
AAAG
AAAT
AACA
...
0.47%
0.37%
0.35%
0.41%
0.32%
Adaptive Coding (Feller-Gallager-Knuth)
配列解析アルゴリズム特論 渋谷
 ハフマン符号はそのままでは一度全テキストは見ないと
文字の出現頻度がわからない
 出現頻度表を更新しながら圧縮する
 初出の文字に対応する頻度０の葉を一つ用意する
 更新はルートから該当ノードまでのパス長に比例した時間で可
能
 デコードも同様に表を更新しながらデコードする
0
0
形を調整
new
00を出力
new
頻度１の新しいノード
Shanon-Fano 符号
配列解析アルゴリズム特論 渋谷
トップダウンに作ろうとした符号
出現頻度でソート
できるだけ半分に近いように分割し、片方に０、もう片方に１
を割り当てる
H(X)≦L＜H(X)+1 は満たす
ただしハフマン符号と異なり、最適とは限らない
A
T
0.7
0.11
G
0.1
C
N
0.07
0.02
Huffman Codingの欠点
配列解析アルゴリズム特論 渋谷
出現確率に大きな偏りがあるとうまく扱えない
H(S)≦平均長＜H(S)+p+0.086 （p: 最大出現確率）
ほとんどが０、といったコードなどではあまり圧縮で
きない
Tunstall Code
配列解析アルゴリズム特論 渋谷
逆にソース側の長さを可変とする方法もある
a
a
a
a
001
a
b
000
a
b
b
100
b
b
101
b
a
110
b
111
011
010
さらにHuffman 符号と組み合わせることが可能
0がたくさん続くような01列の圧縮
配列解析アルゴリズム特論 渋谷
Run-length coding
ＦＡＸ画像など
０１０１０００１１０００００１０１００００００００１００１０００１０００１
１ １ ３
０ ５
１ ８
２ ３
３
 Golombコード
ソース
頻度
０００００
０００１
００１
０１
１
１２１
４５
２１
１５
１０
Huffman符号化
Arithmetic Code (1)
配列解析アルゴリズム特論 渋谷
[0,1)の実数は01列で表すことが可能
0.0
1.0
Arithmetic Code (2)
配列解析アルゴリズム特論 渋谷
考え方
文字列を２つの実数からなる範囲に対応させる
確率の高い文字列は大きい範囲で→表すのに必要なビット
数が少なくなる
実数とは別に文字数を記憶しておく必要がある
aa
a
aba
abaa
0.0
ab
b
abb
abab
0111
011
1.0
Decoding Arithmetic Codes
配列解析アルゴリズム特論 渋谷
３つのステップ
比較
文字出力
スケーリング（対象となる区間を[0.1)に拡大する）
aa
a
aba
abaa
0.0
ab
b
abb
abab
0111
011
1.0
Adaptive Arithmetic Coding
配列解析アルゴリズム特論 渋谷
最初はすべての文字を等確率、とおき、2文字目以
降はそれを更新していく、ということが簡単に可能
デコードも可能
もっと賢く予測といえばマルコフモデル→ＰＰＭ圧縮
きわめて高い圧縮率を誇る
処理速度は遅い
A
C
1
2
1
1
2
G
T
1
2
3
1
1
2
1
PPM (Prediction with Partial Matching)
配列解析アルゴリズム特論 渋谷
 長さm以下の部分文字列に対し、次に来る文字を予測
 新しい「出現」時は、より短い部分文字列からの予測率を用いる
 区別するための記号(ESC)を用意
 ESCの頻度はすでに表れたことのある文字の種類の数
 いろんなバリエーションが存在：例えばPPMAでは単に１とおく
 初めての出現文字の並びの場合にはすべての文字が等確率に出現、と
仮定
 頻度表はデコード時にも作成できるので、記憶する必要はない
直前の文字
次の文字の頻度
ATGCG
A:2 C:1
ESC: 2
ATGCT
A:7 C:4 G:21 T:3
ESC: 4
ATGGA
G:2
ESC: 1
頻度表を作成する
JBIG1: Binary imageの圧縮
配列解析アルゴリズム特論 渋谷
直前の10bitの「画像」から予測
1
2
3
4
5
6
7
9
10
8
Arithmetic Coding
LZ77 (Ziv-Lempel '77)
配列解析アルゴリズム特論 渋谷
辞書法
一度出てきた単語はまた出てくることが多い
出てきた文字列で一番長く一致する部分をみつけ、その
場所と長さでコーディング
計算方法
接尾辞木を使えば線形時間！
ただしメモリは多く必要
とてもまともなとまとももともとまともなとまとではなかった
４，２
１２，２
４，７
さらにHuffman符号と組み合わせる→LZH,zip,PNG
Shanon-Fano符号と組み合わせる→gzip
LZ78 (Ziv-Lempel '78)
配列解析アルゴリズム特論 渋谷
すべての位置から探すのは大変なので、コードとして
既に使われたものを用いる
すでにコードされたもの＋１文字でコード
位置ではなく位置の差分で
とてもまともなとまとももともとまともなとまとではなかった
4, も
6, ま 3, も
4, と 6, と 8, な
5, と
以前に出てきた場所との差＋1文字でコード
9, か
LZW (Welch)
配列解析アルゴリズム特論 渋谷
先に1文字だけの辞書を用意し、さらに、辞書を先に
作成しておけば、場所だけの記憶でコードできる
辞書はエンコード時に作成できるので、特に覚える必要
はない
高速だが圧縮率はさほど高くない
事前に作成してあるアルファベット表
１：と ２：て ３：も ４：ま ５：な ６：で ７：は ８：た ９：か １０：っ
とてもまともなとまとももともとまともなとまとではなかった
11 13
12
15
14
17
16
19
18
3 3 15
21
20
18
15
23
22
17
14
25
24
6 7 5 9 10 8
27
26
29
28
31
30
gif や tiffで使用
暗黙的なコード
1 2 3 4 1 3 5 1 14
文法型圧縮 (SEQUITUR)
配列解析アルゴリズム特論 渋谷
文脈自由文法で表す＝圧縮になっている
表したものをさらに算術符号（等）で圧縮する
とてもまともなとまとももともとまともなとまとではなかった
Ｓ
Ｄ
Ｃ
Ｂ
Ａ
→
→
→
→
→
とてもＤＢＣＣＤAではなかった
Ｂなと
もと
Ａも
まと
変換した文字列：
とてもＤ（B(A（まと）も）なと）ＢＣ（もと）ＣＤＡではなかった
さらに算術符号で圧縮
Block Sorting [Burrows, Wheeler '94]
配列解析アルゴリズム特論 渋谷
 BWT (Burrows-Wheeler Transform)
 Suffix Array と極めて関連が深い （FM-Index）
 MTF（move to front） coding
 ここまでは全く圧縮されていない状態
 これらを行った後、通常のハフマン符号・算術符号等を用いる
 処理するのに巨大すぎる場合はブロック化→ブロックソーティング
 BW変換するためのメモリ・計算時間に限界
cf.
0:
1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
10: i$
mississippi$
7: ippi$
ississippi$
4: issippi$
ssissippi$
1: ississippi$
sissippi$
0: mississippi$
issippi$
9: pi$
ssippi$
8: ppi$
sippi$
ソート
6: sippi$
ippi$
3: sissippi$
ppi$
5: ssippi$
pi$
i$
接尾辞配列 2: ssissippi$
BWT (Burrows-Wheeler Transform)
配列解析アルゴリズム特論 渋谷
 接尾辞配列：SA[0..n]
 ただし、文字列はサイクル化したものを考える
 文字列の最後に$を入れておけば、通常のSAと特に違いはない
 BWT[i] = T[SA[i]−1]
BWT
サイクル化した全接尾辞
0:
1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
mississippi$
ississippi$m
ssissippi$mi
sissippi$mis
issippi$miss
ssippi$missi
sippi$missis
ippi$mississ
ppi$mississi
pi$mississip
i$mississipp
$mississippi
ソート
10:
9:
6:
3:
0:
11:
8:
7:
5:
2:
4:
1:
接尾辞配列
i 11: $mississippi
p 10: i$mississipp
s 7: ippi$mississ
s 4: issippi$miss
m 1: ississippi$m
$ 0: mississippi$
p 9: pi$mississip
i 8: ppi$mississi
s 6: sippi$missis
s 3: sissippi$mis
i 5: ssippi$missi
i 2: ssissippi$mi
同じ
ＢＷＴの性質
配列解析アルゴリズム特論 渋谷
 似た文字がかたまって出現する
 似た文字列の前は同じ文字が出現しやすいから！
 この性質を利用して圧縮するとかなり小さくできる
 MTF変換＋算術符号等
 この文字列からもとの文字列を復元できる！
BWT
mississippi$
復元
10:
9:
6:
3:
0:
11:
8:
7:
5:
2:
4:
1:
接尾辞配列
i 11: $mississippi
p 10: i$mississipp
s 7: ippi$mississ
s 4: issippi$miss
m 1: ississippi$m
$ 0: mississippi$
p 9: pi$mississip
i 8: ppi$mississi
s 6: sippi$missis
s 3: sissippi$mis
i 5: ssippi$missi
i 2: ssissippi$mi
ＢＷＴの復元
配列解析アルゴリズム特論 渋谷
n 桁のRadix Sortを行うだけ
計算量： O(n2)
実はO(n)にできる！
BWT
i
p
s
s
m
$
p
i Sort
s
s
i
i
i$
$
pi
i
si
i
si
i
mi
i
$m
m
pp
p
p BWTを ip Radix
s 頭に加 ss Sort
s えて ss
is
s
is
s
１文字目が
得られる
i$m
$m
pi$
i$
sip
ip
sis
is
mis
is
$mi
mi
ppi
pi
pp BWTを ipp
si 頭に加 ssi
si えて ssi
iss
ss
iss
ss
２文字目が
得られる
$mississippi
i$mississipp
ippi$mississ
issippi$miss
ississippi$m
mississippi$
pi$mississip
Radix Sortを
ppi$mississi
繰り返して、
sippi$missis
最終的には
sissippi$mis
ssippi$missi
ssissippi$mi
すべてを得る
ことができる
ＢＷＴの線形時間復元
配列解析アルゴリズム特論 渋谷
 （一桁分の）ソートの矢印を逆に辿っていく
 最初の文字がどれに相当するか覚えておく
 ただし、覚えてなくても $ を探してそこから始めればＯＫ
最初の文字からスタート
→を辿りながら、BWT
側の文字を出力
BWT
i
p
s
s
m
$
p
i
s
s
i
i
ソートされた文字
（接尾辞配列の最初の文字）
$
i
i
i
i
m
p
p
s
s
s
s
Bucket Sort
（同じ文字ならば順番は変えない
＝ Radix sortの基本）
MTF(move to front) Coding
配列解析アルゴリズム特論 渋谷
 同じ文字が前回出現してから、何種類の他の文字が出現したか？
 初出の文字は適当に処理
 BWT後の文字列を変換すれば偏りのある数字列になる
 小さい数字が多く現れる
 算術符号その他の適当なアルゴリズムで圧縮すれば、かなり小さくできる
 デコードは簡単
 計算量
 バランス木で表現すればO(n log s)
テキスト
変換した数字
変換表
0
1
2
3
adbdbaabacdadc
03211201133212
aadbdbaabacdadc
bbadbdbbabacdad
ccbaaaddddbacca
ddccccccccdbbbb
出来の悪いウィンドウズのメニューみたいな
適当
BW変換による索引： FM-Index (1)
配列解析アルゴリズム特論 渋谷
 ＢＷ変換を用いて検索もできる！
 逆方向検索： 接尾辞木のWeiner Algorithmの逆suffix linkを辿
ることに相当する
１文字前に着目！
BW変換した
文字列に
Aがいくつあるか
がわかれば、
α の接尾辞配列
上の場所から、
Aαの接尾辞配列
上の場所が
計算できる
文字列 Aα
Aで始まる接尾辞
Cで始まる接尾辞
Gで始まる接尾辞
文字列 α
Tで始まる接尾辞
Suffix Array
FM-Index (2): 例
配列解析アルゴリズム特論 渋谷
BW変換された文字列
Suffixes
starting
with A
#T = 89
#G = 431
#T = 150
C
Suffixes
starting
with C
#G = 455
431
455
89
150
TC
GTC
Suffixes
starting
with G
Suffixes
starting
with T
FM-Index (3)
配列解析アルゴリズム特論 渋谷
位置を知るには？
BW-変換されたテキストのある位置が
元のどの位置に対応するのか（＝すな
わちsuffix arrayの値）は、そこから
decodeを行えばよい
BWTの復元の要領で
ただし、それでは O(n) の時間がかかる
間引きされたsuffix arrayを持っておくと
よい
 z ごとに間引くと、 z 倍のオーバーヘッドが
かかる
BWT
i
p
s
s
m
$
p
i
s
s
i
i
$
i
i
i
i
m
p
p
s
s
s
s
FM-Index (4) : WeinerのPrefix Linkと検索
配列解析アルゴリズム特論 渋谷
 葉のSuffix link（群）を逆にたどる（すなわちPrefix linkを辿る）と
逆順の部分文字列になる、ということと対応している
Suffix tree of 'mississippi$'
mississippi$
ississippi$
ssissippi$
sissippi$
issippi$
ssippi$
sippi$
ippi$
ppi$
pi$
i$
All the
suffixes
これに注目し
ていることと
同じ
$
i
s
p
$
pp$
i$
ssi
pi$
i
ppi$
ssippi$
‘s’で始まる葉
ppi$
i
s
si
ppi$
ssippi$
mississippi$
i
ひとつ前が ‘i’ の
ものは２つ
ssippi$
s
‘s’の前が’i’である葉
‘s’ の前が ‘i’ であるものを探す
FM-Index (5) : 検索に必要なデータ構造
配列解析アルゴリズム特論 渋谷
この時、ＢＷ変換した文字列以外に必要なもの：
なんと、接尾辞配列、元の文字列は保持しなくてよい！！！
すなわち、以下の補助データ構造のサイズが十分小さければ、これ
は極めてコンパクトな索引構造として利用することができる！
さらに、（遅さを気にしなければ）BW変換した文字列は圧縮可能！
 ただし、任意の i に対し i 文字目に、（圧縮率のために速さを犠牲にした
としても）何らかの方法でアクセス可能な圧縮方法でないといけない
各文字が何文字ずつあるか
これを覚えておくことで、
 次のindexを計算できる
 逆に、indexからそれに対応する文字が何か計算できる
ＢＷ変換した文字列BW[0..n]上で（多少遅くてもよいので）
BW[0..i]に文字xがいくつあるか
が計算可能な（なるべく小さな）データ構造
（Rank/Select データ構造）
Rank / Select データ構造
配列解析アルゴリズム特論 渋谷
３つの操作
access(A, i) = A[i]
rankc(A, i) = #j s.t., A[j]=c, j<i
selectc (A, i) = j s.t., rankc(A, j) = i
ナイーブに表を持つと
access
元の文字列を持っているだけでＯＫ
rank
select
a
b
c
b
c
c
a
b
c
1
0
0
1
1
0
1
1
1
1
2
1
1
2
2
1
2
3
A
ナイーブなrank表
いずれも、（文字の種類数）×（文字列長）×（整数のサイズ）のサイ
ズの表で、constant timeを（線形時間の前処理で）実現できる
片方がconstant timeでできれば、他方は二分探索でO(log n)が可能
が、これではＢＷ変換の補助データ構造のサイズが
通常の接尾辞配列のアルファベットサイズ倍、という
巨大なものになってしまう！（それではほとんど意味がない）
小さくする方法： ブロック化による間引き
配列解析アルゴリズム特論 渋谷
０１列の場合（簡単化のため）
wビットずつに分割して、wビットずつの間引きされたrank結果
は覚えておく
2w種類のすべてに関してrankの結果を計算し、保管する
RMQのアルゴリズムと少し類似
すると必要なメモリは
𝑛𝑛
𝑤𝑤
( ) · log 𝑛𝑛 + 2𝑤𝑤 log 𝑤𝑤 bit
𝑤𝑤 = log 𝑛𝑛 とすると これは 𝑛𝑛 + 𝑛𝑛 log log 𝑛𝑛 bit
 接尾辞配列（𝑛𝑛 log 𝑛𝑛 bit）よりは小さそう
 が、BW変換後の文字列 (𝑛𝑛 bit）よりは大きい
rankの計算時間は constant timeで可能
0110101110101100010101100001110100110
ブロック化による間引き その２
配列解析アルゴリズム特論 渋谷
 先ほどのブロック化では、間引いたrankはすべての桁を保持し
ていた（＝大きな数字を覚えていて無駄）
 ２段階ブロック化
 l ビットごとにブロック化（大ブロック）
 先頭のrankはすべて記憶
 途中については、大ブロック先頭からの差分で記憶する
 それぞれのブロックをwビットごとにブロック化
 この中は先ほど（その１）と同様の計算を行う
 すると、それだけで

𝑛𝑛
𝑙𝑙
𝑛𝑛
log 𝑙𝑙 + 2𝑤𝑤 log 𝑤𝑤 bitで格納できる
𝑤𝑤
log 2 𝑛𝑛、𝑤𝑤 = (log 𝑤𝑤)/2 の時、o(n)ビット
log 𝑛𝑛 +
 これは𝑙𝑙 =
→ 無視できる！
0110101110101100010101100001110100110
- select も同様のことが可能だが、通常は２分探索で実現することが多い
- アルファベットサイズが大きい場合も同様のことは可能だが、大きくなってしまう。
Wavelet 木
Wavelet 木（概要）
配列解析アルゴリズム特論 渋谷
rank/selectをアルファベットの２分探索的に行うデータ
構造
それぞれの01列に対し先ほどのデータ構造を作成すれば、
オーバーヘッドはlog(アルファベットサイズ）倍ですむ
ATGCGCGATACTGAT
011010101001101
AC/GT で分類
ACのみ抽出
GTのみ抽出
A/Cで分類
A
1
0
ACCAACA
0110010
0
1
0
1
C
TGGGTTGT
10001101
G
T
G/Tで分類
様々な応用がある！
Yet Another 圧縮索引： 圧縮接尾辞配列
配列解析アルゴリズム特論 渋谷
接尾辞配列を（もう少しストレートに）圧縮するには？
Ψ（プサイ、接尾辞配列上のSuffix Link）を用いることが可能
すなわち、FM-Indexとは完全に逆の考え方！
（FM-Index同様）エントロピーに比例した圧縮が可能
順方向の検索がメインとなる
0:
1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
mississippi$
ississippi$
ssissippi$
sissippi$
issippi$
ssippi$
sippi$
ippi$
ppi$
pi$
i$
ソート
接尾辞配列
10:
7:
4:
1:
0:
9:
8:
6:
3:
5:
2:
i$
ippi$
issippi$
ississippi$
mississippi$
pi$
ppi$
sippi$
sissippi$
ssippi$
ssissippi$
Suffix Array 上の Suffix Link
配列解析アルゴリズム特論 渋谷
プサイ
 Ψ (接尾辞配列上のSuffix Link)
 逆接尾辞配列から簡単に作成可能
 Textは記憶しなくてよい
 必要ならばΨ（とアルファベットリスト）から計算可能なため
Index / All suffixes
0:
1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
mississippi$
ississippi$
ssissippi$
sissippi$
issippi$
ssippi$
sippi$
ippi$
ppi$
pi$
i$
$
Index / Suffix array / suffixes
ソート
0:11:
1:10:
2: 7:
3: 4:
4: 1:
5: 0:
6: 9:
7: 8:
8: 6:
9: 3:
10:5:
11:2:
$
i$
ippi$
issippi$
ississippi$
mississippi$
pi$
ppi$
sippi$
sissippi$
ssippi$
ssissippi$
Ψ
0
7
10
11
4
1
6
2
3
8
9
Ψからのテキストの復元
配列解析アルゴリズム特論 渋谷
一番長い接尾辞がどこにあるかを覚えておいて、そ
こからΨを辿っていくだけで、復元できる
アルファベットがそれぞれ何個あるかは覚えておく
Index / Suffix array / suffixes
i
m
p
s
0:11:
1:10:
2: 7:
3: 4:
4: 1:
5: 0:
6: 9:
7: 8:
8: 6:
9: 3:
10:5:
11:2:
$
i$
ippi$
issippi$
ississippi$
mississippi$
pi$
ppi$
sippi$
sissippi$
ssippi$
ssissippi$
Ψ
0
7
10
11
4
1
6
2
3
8
9
ここから開始
Ψの圧縮
配列解析アルゴリズム特論 渋谷
 アルファベットごとに区切ると単調増加
 差分で覚える
すると、小さい値が非常に多くなり、圧縮しやすくなる
 しかも、似たもののsuffix link先も似ているため類似部分列も多い
→ 圧縮効率も良い！
 cf. 接尾辞木のDAG化
Index / Suffix array / suffixes
i
m
p
s
0:11:
1:10:
2: 7:
3: 4:
4: 1:
5: 0:
6: 9:
7: 8:
8: 6:
9: 3:
10:5:
11:2:
$
i$
ippi$
issippi$
ississippi$
mississippi$
pi$
ppi$
sippi$
sissippi$
ssippi$
ssissippi$
Ψ
0
7
10
11
4
1
6
2
3
8
9
Ψi - Ψi-1
7
3
1
5
1
5
1
Ψの圧縮
配列解析アルゴリズム特論 渋谷
しかし、差分で覚えると、実際の値を計算するのに
時間がかかってしまう
間引いて途中の値を適当に覚えておけばよい
O(n/log n)程度のサイズに間引けば、O(log n)時間で計算
できる、といったかんじ
スピード⇔圧縮率 のトレードオフあり
元の数列： 3 4 7 8 13 24 26 32 37 45 54 61 70 ...
差分：
- 1 4 1 5 9 2 6 5 8 9 7 9 ...
Ψを用いた検索
配列解析アルゴリズム特論 渋谷
SA上のある位置のsuffixはΨから簡単に復元可能
これを利用して二分探索が普通にできる
O(m log n)
Index / Suffix array / suffixes
i
m
p
s
0:11:
1:10:
2: 7:
3: 4:
4: 1:
5: 0:
6: 9:
7: 8:
8: 6:
9: 3:
10:5:
11:2:
$
i$
ippi$
issippi$
ississippi$
mississippi$
pi$
ppi$
sippi$
sissippi$
ssippi$
ssissippi$
Ψ
0
7
10
11
4
1
6
2
3
8
9
ippi$
Ψ（suffix link）をたどっていき、それ
ぞれどのアルファベットの領域にあ
るかをチェックしていく
検索結果の位置を知るには？
配列解析アルゴリズム特論 渋谷
 SA[i]の値がわかればよい
 テキスト全体の復元と同様に
Ψを辿っていけば、計算でき
Index / Suffix array / suffixes
る
0:11: $
1:10: i$
 ただそれだとO(n)時間かかっ
てしまうため、間引いた接尾 i 2: 7: ippi$
3: 4: issippi$
辞配列をもっておけば、その
4: 1: ississippi$
計算時間を短縮できる。
 たとえばO(n / log n)サイズ
にまで間引いておけば大幅
に時間が短縮できる上に、さ
ほどサイズは大きくなくてす
む。
 こうしておけば、テキストを部
分的に復元することもできる
ようになる。
m
p
s
5: 0:
6: 9:
7: 8:
8: 6:
9: 3:
10:5:
11:2:
mississippi$
pi$
ppi$
sippi$
sissippi$
ssippi$
ssissippi$
Ψ
0
7
10
11
4
1
6
2
3
8
9
まとめ
配列解析アルゴリズム特論 渋谷
 文字列圧縮アルゴリズムのいろいろ
 Huffman coding
 Shannon-Fano coding
 Tunstall coding
 Run-length coding
 Golomb coding
 Adaptive Huffman coding
 Arithmetic coding
 PPM
 LZ77, LZ78, LZW
 Sequitur
 Block sorting (BWT+MTF)
 FM-Index, Compressed suffix array
 次回
 文字列上のパタン発見・学習