九州大学大学院システム情報科学研究科 情報理学専攻 竹田研究室 博士課程３年 喜田 拓也 圧縮テキストに対する文字列照合 九州大学大学院システム情報科学研究科 情報理学専攻 竹田研究室 博士課程３年 喜田　拓也

研究背景 コラージュシステムと照合アルゴリズム 複数パタンへの拡張 実験結果とまとめ

文字列照合問題 テキストT中に含まれるパタンの出現を求める問題 KMP法[Knuthら(1974)]， BM法[BoyerとMoore (1977)] ビットパラレル手法[Abrahamson(1987)][Baeza-YatesとGonnet(1992)] パタン compress 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]. テキストT

圧縮テキストに対する文字列照合問題 目標２ 目標１ 復号 文字列照合 アルゴリズム 転送 文字列照合 アルゴリズム 転送 転送 二次記憶装置上 テキスト データ 主記憶装置上 文字列照合 アルゴリズム 転送 目標１ 二次記憶装置上 圧縮テキスト 主記憶装置上 文字列照合 アルゴリズム 復号 転送 主記憶装置上 二次記憶装置上 圧縮テキスト 転送 主記憶装置上 圧縮文字列照合 アルゴリズム

本分野における研究 圧縮方法 照合アルゴリズム Run-length Eilam-Tzoreff & Vishkin (1988) 圧縮方法 照合アルゴリズム Run-length Eilam-Tzoreff & Vishkin (1988) Run-length (two dim) Amir et al. (1992, 1997); Amir & Benson (1992) LZ77 family Farach & Thorup (1995); Gąsieniec, et al. (1996); Klein & Shapira (2000) LZ78 family Amir et al. (1996); Kida et al. (1998, 1999); Navarro & Tarhio (2000); Kärkkäinen et al. (2000); LZ family Navarro et al. (1999) Straight-line programs Karpinski et al. (1997); Miyazaki et al. (1997); Hirao et al. (2000) Huffman Fukamachi et al. (1998); Klein & Shapira (2001); Miyazaki et al. (1998) Finite state encoding Takeda (1997) Word based encoding Moura et al. (1998) Pattern substitution Manber (1994); Shibata et al. (1998) Antidictionary based Shibata et al. (1999)

コラージュシステムで表現された テキストに対する 照合アルゴリズム コラージュシステムとは 辞書式圧縮法によって圧縮されたテキストを表現するための形式的体系 コラージュシステム LZW圧縮テキスト LZ78圧縮テキスト LZ77圧縮テキスト コラージュシステムで表現された テキストに対する 照合アルゴリズム ここで、 X3 からX7 まではそれぞれ、このような文字列に対応しています。 すなわちこのS は下の文字列を表現していることになります。 これが原テキストで、S が圧縮テキストです。 X7 に注目してください。 X7 の右辺を展開していくと、このような木構造を作ることができます。 この木の高さをheightで表します。 最も木が高い変数のheightをDのheightとします。 このheight は後で説明する提案アルゴリズムの時間計算量に関係があります。

研究背景 コラージュシステムと照合アルゴリズム 複数パタンへの拡張 実験結果とまとめ

a b ab ab ba b c aba bc abab LZW圧縮法 3 5 6 2 1 2 4 4 b a c a b c a b a テキスト b 8 a c 9 12 10 11 3 5 6 2 1 2 4 4 変換後の列 a b c 1 2 3 辞書木 = {a,b,c} a 5 b 4 a 6 b 7

辞書式圧縮法 辞書式圧縮法の手順 テキスト 圧縮テキスト テキスト中の文字列を辞書に登録 辞書を用いてテキストを符号化 符号化 符号化列 文字列の切り出し

abbabbaabababbabaabababbab Collage systemの例 X1 = a ; X2 = b ; X3 = X1・X2 ;　　　（連接） ab D : X4 = X2・X1 ;　　　（連接） ba X5 = ( X3 )3 ;　　　（繰り返し） ababab X6 = [ 3 ]X5 ;　　　 （切り落とし） bab ||D|| = 6 X6.u ここで、 X3 からX7 まではそれぞれ、このような文字列に対応しています。 すなわちこのS は下の文字列を表現していることになります。 これが原テキストで、S が圧縮テキストです。 X7 に注目してください。 X7 の右辺を展開していくと、このような木構造を作ることができます。 この木の高さをheightで表します。 最も木が高い変数のheightをDのheightとします。 このheight は後で説明する提案アルゴリズムの時間計算量に関係があります。 S : X3 X6 X4 X5 X2 X3 X1 X5 X4 X2 |S| = 10 abbabbaabababbabaabababbab

height(D) の定義 X7 X6 X4 X5 X3 X1 X2 X1 = a ; X2 = b ; D : X7 = X6・X4 ; すなわちこのS は下の文字列を表現していることになります。 これが原テキストで、S が圧縮テキストです。 X7 に注目してください。 X7 の右辺を展開していくと、このような木構造を作ることができます。 この木の高さをheightで表します。 最も木が高い変数のheightをDのheightとします。 このheight は後で説明する提案アルゴリズムの時間計算量に関係があります。 height(X7) = 4 height(D) = max{height(X) | XF(D)} F (D) ： D 中のトークンの集合

LZWのCollage system S : Xi1 Xi2・・・Xin D : X1 = a1; Xq+1 = Xi1 bi2; Xq = aq; Xq+n-1 = Xin-1 bin; ={a1, ..., aq} ただし bj は Xj .u の先頭の文字

LZSSのCollage system S : Xq+1 Xq+2・・・Xq+n D : X1 = a1 ; X2 = a2 ; ・・・ Xq = aq ; Xq+1 = (( [i1]Xl(1) Xl(1)+1 ・・・ Xr(1))m1)[ j1] b1; Xq+2 = (( [i2]Xl(2) Xl(2)+1 ・・・ Xr(2))m2)[ j2] b2; ・・・ Xq+n = (( [in]Xl(n) Xl(n)+1 ・・・ Xr(n))mn)[ jn] bn; ={a1, ..., aq} ただし 0  ik, jk, mk で bj 

Collage systemに対する文字列照合 パタン= a b a b b についての KMPオートマトン : goto 関数 : failure 関数 a 1 2 4 5 b 3 {a} Jump( 4 , Xi4) = 1 Output( 4 , Xi4) = {3} 3 4 状態： 1 1 2 2 3 4 4 3 4 5 1 1 テキスト： abababba S ： 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 O(1) 時間 3 4 状態： 4 5 1 テキスト： abba S ： X5

関数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)を求める X= a → O(1) 時間 X=Y・Z → O(|Occ(, X.u)|) 時間 X=( Y ) j → 連結の場合の結果から O(|Occ(, X.u)|) 時間 X=[ j ]Y → O(|Occ(, X.u)|+height(Y ) ) 時間 X= Y [ j ] → O(|Occ(, X.u)|) 時間

提案アルゴリズムの計算量 定理 コラージュシステム〈D, S 〉で表現されたテキストに対する文字列照合問題は， O( ||D|| + ||2 ) 領域を用いて O( ( ||D|| + |S| )・height(D) + ||2 + r ) 時間で解決できる． Dが切り落とし操作を含まない場合は， O( ||D|| + |S| + ||2 + r ) 時間で解決できる． r はパタンの出現個数

得られた知見 O( (||D||+|S|) ・height(D) + ||2 + r ) 時間 O( ||D|| + |S| + ||2 + r ) 時間 LZ77 LZSS 切り取り操作がある LZ78 Sequitur LZW BPE 切り取り操作がない O( ||D|| + ||2 ) 領域 r はパタンの出現個数

研究背景 コラージュシステムと照合アルゴリズム 複数パタンへの拡張 実験結果とまとめ

アイデア {a,b} a b a b b c a b b Jump( q, X) = AC( q, X.u)  ={aba,ababb,abca,bb} についてのAho-Corasick照合機会 {a,b} a b a b b 1 2 3 4 5 {ababb,bb} {aba} c 6 a 7 : goto function : failure function { } : output {abca} b 8 9 b {bb} Jump( q, X) = AC( q, X.u) Output( q, X)={|v|,    o(AC(q, v)), v is a prefix of X.u} (AC はAC照合機会の遷移関数) ( o はAC照合機会の出力関数)

Output(q, X) の枚挙 Y.u Z.u Output( q, X) の枚挙  Occ( , X.u) の枚挙 X=YZ について Occ*( , Y.uZ.u) の枚挙の場合 Y.u Z.u どの周期 ? 単一パタンの 場合 複数パタンの 場合

Occ*(, abcabcabc) の枚挙 ={abcabc, cabb, abca} 1 2 3 の接尾辞 a b c abbaabcc baab abcc cc abb 部分文字列とは！ bc bca bcabc 1 a nil 3 1 c a b O(m2) 時間領域の前処理ののち O(|Occ*( , Y.uZ.u)|) 時間で解決 ca nil nil nil px 接尾辞 接頭辞 1 c a b abca 1 nil nil (px, py) 3 py の接頭辞 m は  中のパタンの長さの総和

Occ(, (Y.u)k ) の枚挙 1 GST Y.u {1, 3, 6} 単一パタンの場合の手続きに帰着させる X=Y k Y.uY.u が  中のパタンの部分文字列ならば，X.u 中に Y.u2 をまたいで出現するパタンのリストをGSTのノードに付加する． Y.u2 となる部分文字列の個数は O(m) 個  O(m2) 領域 Y.u X=Y k Y.u 1 接尾辞木 GST (Y.u)2 は 1の部分文字列で |Y.u| は 1の周期 (3, 6 についても同様) {1, 3, 6} {1, 3, 6} m は  中のパタンの長さの総和

アルゴリズムの計算量 r はパタンの出現個数 定理 コラージュシステム〈D, S 〉で表現されたテキストに対する複数パタンの文字列照合問題は O( ( ||D|| + |S| )・height(D) + m2 + r ) 時間， O( ||D|| + m2 ) 領域で解決できる． もし D が切り落とし操作を含まない場合， O( ||D|| + |S| + m2 + r ) 時間で解決できる． m は  中のパタンの長さの総和 r はパタンの出現個数

研究背景 コラージュシステムと照合アルゴリズム 複数パタンへの拡張 実験結果とまとめ

実験結果（LZW圧縮法） CPU時間（秒） 目標１ パタンの長さ 1.4 1.2 1.0 0.8 compressにKMPを組込んだもの AlphaStation XP1000 (Alpha21264: 667MHz) Tru64 UNIX V4.0F Genbank（DNA塩基配列）17.1Mbyte 1.2 1.0 0.8 compressにKMPを組込んだもの CPU時間（秒） 目標１ gunzipにKMPを組込んだもの 0.6 提案アルゴリズム 0.4 0.2 非圧縮テキストをKMPで照合 5 10 15 20 25 30 パタンの長さ * compress はUNIXのLZW圧縮の圧縮ツール * gunzip はUNIXのLZ圧縮の復号ツール

実験結果（非圧縮テキスト上のアルゴリズムとの対比） 0.00 0.05 0.10 0.15 0.20 0.25 AlphaStation XP1000 (Alpha21264: 667MHz) Tru64 UNIX V4.0F Genbank（DNA塩基配列） 17.1Mbyte 非圧縮テキストをAgrepで照合 CPU時間（秒） 非圧縮テキストをKMPで照合 目標２ BPE圧縮テキストに対する照合 5 10 15 20 25 30 * BPEはByte Pair Encoding圧縮法 パタンの長さ * KMPはKnuth-Morris-Pratt法 * AgrepはWu&Manberが開発した検索ツール

実験結果（非圧縮テキスト上のアルゴリズムとの対比） パタンの長さ 0.0 0.3 0.4 0.5 0.8 0.1 0.2 0.6 0.7 CPU時間（秒） AlphaStation XP1000 (Alpha21264: 667MHz) Tru64 UNIX V4.0F Medline（英文テキスト） 60.3Mbyte 非圧縮テキストをKMPで照合 BPE圧縮テキストに対する Boyer-Moore型のアルゴリズム を用いた照合（Shibataら[2000]） BPE圧縮テキストに対する照合 非圧縮テキストをAgrepで照合 5 10 15 20 25 30 * BPEはByte Pair Encoding圧縮法 * KMPはKnuth-Morris-Pratt法 * AgrepはWu&Manberが開発した検索ツール

まとめ Collage systemを提案 Collage system上の文字列照合アルゴリズムを開発 実験結果 単一パタンに対するアルゴリズム O( (||D||+|S|) ・height(D) + ||2 + r ) 時間，O( ||D|| + ||2 ) 領域 複数パタンに対するアルゴリズム O( (||D||+|S|) ・height(D) + m2 + r ) 時間，O( ||D|| + m2 ) 領域 実験結果 LZW圧縮テキスト 通常用いられる文字列照合法に比べ約2倍高速 Byte pair encoding (BPE)圧縮テキスト 非圧縮テキストに対する照合よりも約1.8～3.7倍高速 圧縮率が良いテキストに対してAgrepより高速