Collage System: A Unifying Framework for

圧縮テキストに対する文字列照合
九州大学大学院システム情報科学研究科
情報理学専攻竹田研究室博士課程３年
喜田拓也
1/29
研究背景
研究背景
コラージュシステムと照合アルゴリズム
複数パタンへの拡張
実験結果とまとめ
2
文字列照合問題


テキストT中に含まれるパタンの出現を求める問題
KMP法[Knuthら(1974)]， BM法[BoyerとMoore (1977)]
ビットパラレル手法[Abrahamson(1987)][Baeza-YatesとGonnet(1992)]
パタン compress
テキストT
3/29
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/29
主記憶装置上
圧縮文字列照合
アルゴリズム
本分野における研究
圧縮方法
照合アルゴリズム
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/29
コラージュシステムとは

辞書式圧縮法によって圧縮されたテキストを表現する
ための形式的体系
LZ77圧縮テキスト
LZ78圧縮テキスト
LZW圧縮テキスト
6/29
コラージュシステムで表現された
テキストに対する
照合アルゴリズム
コラージュシステムと
照合アルゴリズム
研究背景
コラージュシステムと照合アルゴリズム
複数パタンへの拡張
実験結果とまとめ
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
b b
6
7
11
8/29
5
a
b
5 23
2
c
3
c
9
10
a
8
6
12
a
9
11
辞書式圧縮法

辞書式圧縮法の手順


テキスト中の文字列を辞書に登録
辞書を用いてテキストを符号化
符号化
符号化列
テキスト
辞書
文字列の切り出し
9/29
圧縮テキスト
Collage systemの例
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/29
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
X3
X1
X2
height(X7) = 4
height(D) = max{height(X) | XF(D)}
F (D) ： D 中のトークンの集合
11/29
X1
LZWのCollage system
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 の先頭の文字
12/29
LZSSのCollage system
S:
Xq+1 Xq+2・・・Xq+n
D:
X1 = a1 ; X2 = a2 ; ・・・ Xq = aq ;
Xq+1 = ((
[ j1]
m
1
)
) b1;
[ j2]
[i
]
m
2
Xq+2 = (( Xl(2) Xl(2)+1 ・・・ Xr(2)) )
b 2;
[i1]X
l(1) Xl(1)+1 ・・・ Xr(1)
2
・
・
・
Xq+n = ((
[in]X
l(n) Xl(n)+1 ・・・ Xr(n)
={a1, ..., aq}
ただし 0  ik, jk, mk で bj 
13/29
[ j n]
m
n
)
)
b n;
Collage systemに対する文字列照合
パタン= 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 ：
14/29
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
15/29
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)| ) 時間で枚挙できる．

文字列 X.u 中の  の出現位置の集合Occ(, X.u)を求める





16/29
X= a
X=Y・Z
X=( Y ) j
X=[ j ]Y
X= Y [ j ]
→ O(1) 時間
→ O(|Occ(, X.u)|) 時間
→ 連結の場合の結果から O(|Occ(, X.u)|) 時間
→ O(|Occ(, X.u)|+height(Y ) ) 時間
→ O(|Occ(, X.u)|) 時間
提案アルゴリズムの計算量
定理
コラージュシステム〈D, S 〉で表現されたテキストに対する
文字列照合問題は，
O( ||D|| + ||2 ) 領域を用いて
O( ( ||D|| + |S| )・height(D) + ||2 + r ) 時間で解決できる．
Dが切り落とし操作を含まない場合は，
O( ||D|| + |S| + ||2 + r ) 時間で解決できる．
r はパタンの出現個数
17/29
得られた知見
O( (||D||+|S|) ・height(D) + ||2 + r ) 時間
LZ77 LZSS
O( ||D|| + |S| + ||2 + r ) 時間
LZ78
O( ||D|| + ||2 ) 領域
18/29
LZW
BPE
Sequitur
r はパタンの出現個数
複数パタンへの拡張
研究背景
コラージュシステムと照合アルゴリズム
複数パタンへの拡張
実験結果とまとめ
19
アイデア
 ={aba,ababb,abca,bb} についてのAho-Corasick照合機会
{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 is a prefix of X.u}
(
20/29
o はAC照合機会の出力関数)
Output(q, X) の枚挙
Output( q, X) の枚挙  Occ( , X.u) の枚挙
トークンX について場合わけ

X=YZ について Occ*( , Y.uZ.u) の枚挙の場合
Y.u
どの周期 ?
Z.u
単一パタンの
場合
複数パタンの
場合
21/29
Occ*(, abcabcabc) の枚挙
={abcabc, cabb, abca}
1
a
a
a
a
2
3
の接尾辞
b
b
b
b
c a b c a b c
bc
bca
bcabc
部分文字列とは！
c a b c a
c a b cabbaabcc
1
c a b
3
1
a
nil
c a b c a baab
b c
O(m2) 時間領域の前処理ののち
c a b c a
abccO(|
ca Occ*( ,
nil Y.uZ.u)
nil |) 時間で解決
nil
px
c a b cabb
接尾辞
c a b
cc
接頭辞
1 a b c a b c
1
abca
nil
nil
(px, py)
a
b
c
a
3
py
a b c
a b
の接頭辞
m は  中のパタンの長さの総和
22/29
Occ(, (Y.u)k ) の枚挙

単一パタンの場合の手続きに帰着させる


Y.uY.u が  中のパタンの部分文字列ならば，X.u 中に Y.u2 をまた
いで出現するパタンのリストをGSTのノードに付加する．
Y.u2 となる部分文字列の個数は O(m) 個  O(m2) 領域
Y.u
X=Y
接尾辞木
GST
Y.u
Y.u
{
{11,,3,3, 6} 6}
k
1
(Y.u)2 は 1の部分文字列で
|Y.u| は 1の周期
(3, 6 についても同様)
m は  中のパタンの長さの総和
23/29
アルゴリズムの計算量
定理
コラージュシステム〈D, S 〉で表現されたテキストに対する複数パタン
の文字列照合問題は
O( ( ||D|| + |S| )・height(D) + m2 + r ) 時間，
O( ||D|| + m2 ) 領域で解決できる．
もし D が切り落とし操作を含まない場合，
O( ||D|| + |S| + m2 + r ) 時間で解決できる．
m は  中のパタンの長さの総和
r はパタンの出現個数
24/29
実験結果とまとめ
研究背景
コラージュシステムと照合アルゴリズム
複数パタンへの拡張
実験結果とまとめ
25
実験結果（LZW圧縮法）
1.4
AlphaStation XP1000
(Alpha21264: 667MHz)
Tru64 UNIX V4.0F
目
標
１
CPU時間（秒）
1.2
Genbank（DNA塩基配列）
17.1Mbyte
1.0
0.8
compressにKMPを組込んだもの
gunzipにKMPを組込んだもの
0.6
提案アルゴリズム
0.4
0.2
0
非圧縮テキストをKMPで照合
5
10
15
20
25
パタンの長さ
26/29
30
* compress はUNIXのLZW圧縮の圧縮ツール
* gunzip はUNIXのLZ圧縮の復号ツール
実験結果（非圧縮テキスト上のアルゴリズムとの対比）
CPU時間（秒）
0.25
0.20
Genbank（DNA塩基配列）
17.1Mbyte
0.15
非圧縮テキストをKMPで照合
0.10
非圧縮テキストをAgrepで照合
目 0.05
標
２
BPE圧縮テキストに対する照合
0.00
27/29
AlphaStation XP1000
(Alpha21264: 667MHz)
Tru64 UNIX V4.0F
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
28/29
5
10
15
20
25
パタンの長さ
30
* BPEはByte Pair Encoding圧縮法
* KMPはKnuth-Morris-Pratt法
* AgrepはWu&Manberが開発した検索ツール
まとめ


Collage systemを提案
Collage system上の文字列照合アルゴリズムを開発



複数パタンに対するアルゴリズム
2
2
 O( (||D||+|S|) ・height(D) + m + r ) 時間，O( ||D|| + m ) 領域
実験結果


29/29
単一パタンに対するアルゴリズム
2
2
 O( (||D||+|S|) ・height(D) + || + r ) 時間，O( ||D|| + || ) 領域
LZW圧縮テキスト
 通常用いられる文字列照合法に比べ約2倍高速
Byte pair encoding (BPE)圧縮テキスト
 非圧縮テキストに対する照合よりも約1.8～3.7倍高速
 圧縮率が良いテキストに対してAgrepより高速

Download Report