Collage System: A Unifying Framework for

Pattern Matching on Compressed Texts
圧縮テキストに対する文字列照合
学位申請者
九州大学大学院システム情報科学研究科情報理学専攻
喜田拓也
1/38
研究背景
研究背景
コラージュシステム
コラージュシステム上の照合アルゴリズム
圧縮テキストに対する近似文字列照合問題
まとめ
2
文字列照合問題


テキストT 中に含まれるパタンの出現を求める問題
KMP法[Knuthら(1974)]， BM法[BoyerとMoore (1977)]
ビットパラレル手法[Abrahamson(1987)][Baeza-YatesとGonnet(1992)]
パタン compress
テキストT
3/38
We introduce a general framework which is suitable to capture an
essence of compressed pattern matching according to various
dictionary based compressions. The goal is to find all occurrences of a
pattern in a text without decompression, which is one of the most
active topics in string matching. Our framework includes such
compression methods as Lempel-Ziv family, (LZ77, LZSS, LZ78, LZW),
byte-pair encoding, and the static dictionary based method. Technically,
our pattern matching algorithm extremely extends that for LZW
compressed text presented by Amir, Benson and Farach [Amir94].
圧縮テキストに対する文字列照合問題
目
テキスト
標
データ
文字列照合
アルゴリズム
転送
２
二次記憶装置上
主記憶装置上
圧縮テキスト
目
標転送
１
二次記憶装置上
文字列照合
アルゴリズム
復号
主記憶装置上
主記憶装置上
圧縮テキスト
転送
二次記憶装置上
4/38
主記憶装置上
圧縮文字列照合
アルゴリズム
本分野における研究
圧縮方法
照合アルゴリズム
Run-length
Run-length (two dim)
LZ77 family
Eilam-Tzoreff & Vishkin (1988)
Amir et al. (1992, 1997); Amir & Benson (1992)
Farach & Thorup (1995); Gąsieniec, et al. (1996);
Klein & Shapira (2000)
Amir et al. (1996); Kida et al. (1998, 1999);
Navarro & Tarhio (2000); Kärkkäinen et al. (2000);
Navarro et al. (1999)
Karpinski et al. (1997); Miyazaki et al. (1997);
Hirao et al. (2000)
Fukamachi et al. (1998); Klein & Shapira (2001);
Miyazaki et al. (1998)
Takeda (1997)
Moura et al. (1998)
Manber (1994); Shibata et al. (1998)
Shibata et al. (1999)
LZ78 family
LZ family
Straight-line programs
Huffman
Finite state encoding
Word based encoding
Pattern substitution
Antidictionary based
5/38
コラージュシステム(collage system)とは

辞書式圧縮法によって圧縮されたテキストを表現する
ための形式的体系
LZ77圧縮テキスト
LZ78圧縮テキスト
LZW圧縮テキスト
6/38
コラージュシステムで表現された
テキストに対する
照合アルゴリズム
コラージュシステム
研究背景
コラージュシステム
コラージュシステム上の照合アルゴリズム
圧縮テキストに対する近似文字列照合問題
まとめ
7
LZW圧縮法
a b ab ab ba b c aba bc abab
テキスト
変換後の列
12 4
辞書木
= {a,b,c}
4
0
a
1
b
a
b
4
8/38
5
a
b b
6
7
b
11
5 23
2
c
3
c
9
10
a
8
6
12
a
9
11
辞書式圧縮法

辞書式圧縮法の手順


テキスト中の文字列を辞書に登録
辞書を用いてテキストを符号化
符号化
符号化列
テキスト
辞書
文字列の切り出し
9/38
圧縮テキスト
コラージュシステムの例
X1 = a ;
X2 = b ;
X3 = X1・X2 ;
D : X4 = X2・X1 ;
X5 = ( X3 )3 ;
X6 = [ 3 ]X5 ;
||D|| = 6
（連接） ab
（連接） ba
（繰り返し） ababab
（切り落とし） bab
X6.u
S : X3 X6 X4 X5 X2 X3 X1 X5 X4 X2
|S| = 10
abbabbaabababbabaabababbab
10/38
コラージュシステムの定義


コラージュシステムとは，組〈D, S 〉
D : トークン割当の集合（辞書に相当）

X1 = expr1 ; X2 = expr2 ; ・・・ ; Xn = exprn
各 exprk は以下のいずれか
 a
a ∈Σ∪{ε}
一文字割当
 Xi ・ Xｊ
i, j は整数で， i, j < k 連結
j
 ( Xi )
i, j は整数で， i < k
繰り返し
[ j ]X

i, j は整数で， i < k
前切り落とし
i
[j]
 Xi
i, j は整数で， i < k
後切り落とし
||D|| = n : D中のトークンの個数

X.u ：トークン X が表す文字列


S : D で割当てられたトークンの列（符号列に相当）


11/38
Xi1 Xi2 ・・・Xil
( Xi は D中のトークン)
|S| = l : トークンの列の長さ
height(D) の定義
D : X1 = a ;
X2 = b ;
X3 = X1・X2 ;
X4 = X2・X1 ;
X5 = ( X3 )3 ;
X6 = [ 3 ]X5 ;
X7 = X6・X4
X7
X6
X4
X5
X2
X1
X3
X1
X2
height(X7) = 4
height(D) = max{height(X) | XF(D)}
F (D) ： D 中のトークンの集合
12/38
LZWのコラージュシステム
S : Xi1 Xi2・・・Xin
D : X1 = a1;
X2 = a2;
・
・
・
Xq = aq;
Xq+1 = Xi1 bi2;
Xq+2 = Xi2 bi3;
・
・
・
Xq+n-1 = Xin-1 bin
={a1, ..., aq}
ただし bj は Xj .u の先頭の文字
13/38
LZSSのコラージュシステム
S : Xq+1 Xq+2・・・Xq+n
D : X1 = a1 ; X2 = a2 ; ・・・ Xq = aq ;
[ j1]
[i
]
m
1
1
Xq+1 = (( Xl(1) Xl(1)+1 ・・・ Xr(1)) ) b1;
Xq+2 = ((
[i2]X
l(2) Xl(2)+1 ・・・ Xr(2)
[ j2]
m
2
)
)
b2;
・
・
・
[ jn]
[i
]
m
n
n
Xq+n = (( Xl(n) Xl(n)+1 ・・・ Xr(n)) )
bn
14/38
={a1, ..., aq}
ただし 0  ik, jk, mk で bj 
文法変換による圧縮（Kiefferら(2000)）
テキストT
grammar
transformer
文脈自由文法 GT
grammar
encoder
011100110011100111110111
S → ACBBEA
A → D1
B → C1
C → 0D
D → 0E
E → 11
D : X1 = 0 ;
X2 = 1 ;
X3 = X2・X2;
X4 = X1・X3;
X5 = X1・X4;
X6 = X5・X2;
X7 = X4・X2
E
D
C
B
A
S : X7 X5 X6 X6 X3 X7
圧縮テキスト
15/38
コラージュシステム上
の照合アルゴリズム
研究背景
コラージュシステム
コラージュシステム上の照合アルゴリズム
圧縮テキストに対する近似文字列照合問題
まとめ
16
コラージュシステムに対する文字列照合
パタン= a b a b b についての KMPオートマトン
: goto 関数
{a}
0
a
1
b
2
a
3
b
Jump( 4 , Xi4) = 1
4
b
5
: failure 関数
Output( 4 , Xi4) = {3}
状態： 0
1
2
3
4
3
4
5
1
a
b
a
b
a
b
b
a
テキスト：
S ：
17/38
Xi1 Xi2
Xi3
Xi4
関数Jump の構成の計算量
補題
関数Jump( j ,X) は，O( ||D|| + ||2 ) 領域を用いて
O( ||D||・height(D) + ||2 ) 時間で構成でき，
O(1)時間で値を返す．
Dが切り落とし操作を含まない場合は，
O( ||D|| + ||2 ) 時間で構成できる．
Jump( 4 , X5) = 1
状態： 4
5
1
3
4
テキスト：
a
b
b
a
S ：
X5
18/38
O(1) 時間
関数Output の構成の計算量
補題
集合Output( j, X) の要素を枚挙する手続きは，
O( ||D|| + ||2 ) 領域を用いて
O( ||D||・height(D) + ||2 ) 時間で構築でき，
O( height(D) + |Output( j, X)| )時間で枚挙できる．
Dが切り落とし操作を含まない場合は，O( ||D|| + ||2 )
時間で構築でき，O( |Output( j, X)| ) 時間で枚挙できる．
19/38
提案アルゴリズムの計算量
定理
コラージュシステム〈D, S 〉で表現されたテキストに対する
文字列照合問題は，
O( ||D|| + ||2 ) 領域を用いて
O( ( ||D|| + |S| )・height(D) + ||2 + r ) 時間で解決できる．
Dが切り落とし操作を含まない場合は，
O( ||D|| + |S| + ||2 + r ) 時間で解決できる．
20/38
r はパタンの出現個数
得られた知見
O( (||D||+|S|) ・height(D) + ||2 + r ) 時間
LZ77 LZSS
O( ||D|| + |S| + ||2 + r ) 時間
LZ78
LZW
BPE
Sequitur
O( ||D|| + ||2 ) 領域
21/38
r はパタンの出現個数
複数パタンへの拡張


入力：テキストT, パタンの集合
非圧縮テキストに対するAho-Corasick(AC)オートマトンを模倣



O( (||D||+|S|) ・height(D) + m2 + r ) 時間
O( ||D|| + m2 ) 領域
Boyer-Moore(BM)型の照合アルゴリズム



Shibataら(2000)のアルゴリズムを拡張
O( (||D||+|S|) ・height(D) + m|S| + m2 + r ) 時間
O( ||D|| + m2 ) 領域
m はに含まれるパタンの長さの総和
22/38
r はパタンの出現個数
アイデア
 ={aba,ababb,abca,bb} についてのACオートマトン
{a,b}
0
a
b
1
2
a
b
3
4
b
{ababb,bb}
{aba}
c
b
8
b
6
a
5
7
{abca}
9
{bb}
: goto function
: failure function
{ } : output
(AC はACオートマトンの遷移関数)
Jump( q, X) = AC( q, X.u)
Output( q, X)={|v|,    o(AC(q, v)), v は X.u の接頭辞}
(
23/38
o はACオートマトンの出力関数)
実験結果（LZW圧縮法）
1.4
AlphaStation XP1000
(Alpha21264: 667MHz)
Tru64 UNIX V4.0F
目
標
１
CPU時間（秒）
1.2
Genbank（DNA塩基配列）
17.1Mbyte
1.0
0.8
compress(LZW)にKMPを組込み
gunzip(LZ77)にKMPを組込み
0.6
提案アルゴリズム
0.4
ビットパラレルによる高速化
0.2
0
非圧縮テキストをKMPで照合
5
10
15
20
25
パタンの長さ
24/38
30
* compress はUNIXのLZW圧縮の圧縮ツール
* gunzip はUNIXのLZ圧縮の復号ツール
実験結果（非圧縮テキスト上のアルゴリズムとの対比）
CPU時間（秒）
0.25
AlphaStation XP1000
(Alpha21264: 667MHz)
Tru64 UNIX V4.0F
0.20
Genbank（DNA塩基配列）
17.1Mbyte
0.15
非圧縮テキストをKMPで照合
0.10
目 0.05
標
２
0.00
25/38
BPE圧縮テキストに対する照合
5
10
15
20
25
パタンの長さ
30
* BPEはByte Pair Encoding圧縮法
* KMPはKnuth-Morris-Pratt法
* AgrepはWu&Manberが開発した検索ツール
実験結果（非圧縮テキスト上のアルゴリズムとの対比）
0.8
AlphaStation XP1000
(Alpha21264: 667MHz)
Tru64 UNIX V4.0F
CPU時間（秒）
0.7
Medline（英文テキスト）
60.3Mbyte
0.6
0.5
非圧縮テキストをKMPで照合
0.4
BPE圧縮テキストに対する照合
0.3
非圧縮テキストをAgrepで照合
0.2
BPE圧縮テキストに対する
Boyer-Moore型のアルゴリズム
を用いた照合（Shibataら[2000]）
0.1
0.0
26/38
5
10
15
20
25
パタンの長さ
30
* BPEはByte Pair Encoding圧縮法
* KMPはKnuth-Morris-Pratt法
* AgrepはWu&Manberが開発した検索ツール
圧縮テキストに対する
近似文字列照合問題
研究背景
コラージュシステム
コラージュシステム上の照合アルゴリズム
圧縮テキストに対する近似文字列照合問題
まとめ
27
近似文字列照合問題
CARRIAGE
MARRIAGE
MASSAGE
28/38
近似文字列照合問題


テキスト中のパタンとの編集距離が k 以内の文字列の
出現を求める問題
編集距離
 文字列 x に文字の挿入・削除・置換の操作を施して
文字列 y へ変換するために要する最小操作回数 d
CARRIAGE
d=1
MARRIAGE
k=2
置換
MASSAGE
d=3
29/38
MARRIAGE
削除
MASS AGE
近似文字列照合アルゴリズム

動的計画法



オートマトンに基づく手法


Ukkonen (1985) O( min(3m, m(2m||)k) ) 個の状態数
ビットパラレル手法




Sellers (1980) O(mN) 時間 O(m) 領域
Ukkonen (1985)
平均O(kN) 時間 O(m) 領域
Wu & Manber (1992) O( k m/L N) 時間領域
Baeza-Yates & Navarro (1996) O( k(m-k)/L N) 時間領域
Myers (1998) O( m/L N) 時間領域
フィルタリング手法

Wu and Manber (1992)
詳しい人
L はマシン依存
N はテキストの長さ
m はパタンの長さ
k は許容するエラーの数
G. Navarro
A Guided Tour to Approximate String Matching
ACM Computing Surveys, 33(1):31-88,2001
30/38
圧縮テキスト上の近似文字列照合

Kärkkäinenら(2000)のアルゴリズム




動的計画法を使った近似文字列照合アルゴリズムに基づく
最悪時 O(mkn+r ) 時間、平均 O(k2n+r ) 時間
LZ78圧縮テキスト上で動作
提案アルゴリズム



非決定性オートマトンの動作をビットパラレル手法で模倣する
Baeza-Yates & Navarro (1999) のアルゴリズムを拡張
最悪時 O(mk3n / L) 時間
制限されたCollage system上で動作 → LZ78/LZW上で動作
n は圧縮テキストの長さ
m はパタンの長さ
31/38
r はパタンの出現個数
LZW圧縮法に対する実験結果
80
Intel Pentium III 550MHz
(RAM: 64Mb; Linux)
Wall Street Journal の記事
（英文テキスト）10Mbyte
パタンの長さ＝10
CPU時間（秒）
70
60
50
40
提案アルゴリズム
30
20
Kärkkäinenらのアルゴリズム
10
復号後に[Myers98]で照合
0
1
2
3
4
5
許容される最大の編集距離 k
32/38
圧縮テキストに対する近似文字列照合の高速化

フィルタリング手法（Filtration technique; Wu and Manber, 1992）



パタンを k+1 個の小片に分割
各小片を複数パタン文字列照合アルゴリズムで照合
小片が出現した近辺を通常用いられる近似文字列照合アルゴリ
ズムを用いて検査
k = 2 の場合
パタン: TAAATCACGGCATACT
分割後の小片: TAAAT, CACGG, CATACT
テキスト:

33/38
ACCCTGTTTAGATCACGGCACTACTGTAAAC
圧縮テキストに対してフィルタリング手法を適用

圧縮テキスト上の複数パタン文字列照合アルゴリズムが必要

圧縮テキストを部分的に復号する必要がある
圧縮テキスト上の複数パタン照合アルゴリズム

Aho-Corasick型


Boyer-Moore型



G. Navarro and J. Tarhio,
Boyer-Moore string matching over Ziv-Lempel compressed text.
Y. Shibata, T. Matsumoto, M. Takeda, A. Shinohara, and S. Arikawa,
A Boyer-Moore type algorithm for compressed pattern matching.
ビットパラレル型


34/38
T. Kida, M. Takeda, A. Shinohara, M. Miyazaki, and S. Arikawa,
Multiple pattern matching in LZW compressed text.
G. Navarro and M. Raffinot,
A general practical approach to pattern matching over Ziv-Lempel
compressed text.
T. Kida, M. Takeda, A. Shinohara, M. Miyazaki, and S. Arikawa,
Shift-And approach to pattern matching in LZW compressed text.
LZW圧縮法における実験結果
Intel Pentium III 550MHz
(RAM: 64Mb; Linux)
Wall Street Journal の記事
（英文テキスト）10Mbyte
パタンの長さ＝10
CPU時間（秒）
7
6
5
復号後にフィルタリング手法で照合
4
復号後に[Myers98]で照合
3
圧縮テキストにフィルタリング/AC
圧縮テキストにフィルタリング/BM
2
圧縮テキストにフィルタリング/BP
1
1
2
3
4
5
許容される最大の編集距離 k
35/38
* ACはAho-Corasick型の圧縮テキスト上の
複数パタン文字列照合アルゴリズム
* BPはBit-parallel型のアルゴリズム[Navarro+99]
* BMはBoyer-Moore型のアルゴリズム[Navarro+00]
LZW圧縮法における実験結果
CPU時間（秒）
7
圧縮テキストにフィルタリング/AC
6
復号後にフィルタリング手法で照合
5
4
圧縮テキストにフィルタリング/BM
圧縮テキストにフィルタリング/BP
3
復号後に[Myers98]で照合
2
Intel Pentium III 550MHz
(RAM: 64Mb; Linux)
Wall Street Journal の記事
（英文テキスト）10Mbyte
パタンの長さ＝30
1
0
1
5
10
15
許容される最大の編集距離 k
36/38
LZW圧縮法における実験結果
CPU時間（秒）
8
Intel Pentium III 550MHz
(RAM: 64Mb; Linux)
DNA塩基配列 10Mbyte
パタンの長さ＝30
7
6
5
圧縮テキストにフィルタリング/BM
4
復号後にフィルタリング手法で照合
3
復号後に[Myers98]で照合
2
圧縮テキストにフィルタリング/AC
1
0
圧縮テキストにフィルタリング/BP
1
5
10
15
許容される最大の編集距離 k
37/38
* ACはAho-Corasick型の圧縮テキスト上の
複数パタン文字列照合アルゴリズム
* BPはBit-parallel型のアルゴリズム[Navarro+99]
* BMはBoyer-Moore型のアルゴリズム[Navarro+00]
まとめ


コラージュシステムを提案
コラージュシステム上の文字列照合アルゴリズムを開発




複数パタンに対するアルゴリズム
近似文字列照合アルゴリズム

ビットパラレル手法に基づくアルゴリズム→O(k3||n /L) 時間

フィルタリング手法による高速化
実験結果


38/38
単一パタンに対するアルゴリズム
2
2
 O( (||D||+|S|) ・height(D) + || + r ) 時間，O( ||D|| + || ) 領域
LZW圧縮テキスト
 通常用いられる文字列照合法に比べ約2倍高速
 近似文字列照合－kが小さい場合に最高約3倍高速
Byte pair encoding (BPE)圧縮テキスト
 非圧縮テキストに対する照合よりも約1.8～3.7倍高速
 圧縮率が良いテキストに対してAgrepより高速

Download Report