Pattern Matching on Compressed Texts

Presentation on theme: "Pattern Matching on Compressed Texts"— Presentation transcript:

1 Pattern Matching on Compressed Texts
圧縮テキストに対する文字列照合 学位申請者 九州大学大学院システム情報科学研究科情報理学専攻 喜田　拓也

2 研究背景 コラージュシステム コラージュシステム上の照合アルゴリズム 圧縮テキストに対する近似文字列照合問題 まとめ

3 文字列照合問題 テキスト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

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

5 本分野における研究 圧縮方法 照合アルゴリズム 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)

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

7 コラージュシステム 研究背景 コラージュシステム コラージュシステム上の照合アルゴリズム 圧縮テキストに対する近似文字列照合問題 まとめ

8 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

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

10 abbabbaabababbabaabababbab
コラージュシステムの例 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

11 コラージュシステムの定義 X.u ： トークン X が表す文字列 コラージュシステムとは，組〈D, S 〉
X1 = expr1 ; X2 = expr2 ; ・・・ ; Xn = exprn 各 exprk は以下のいずれか a a ∈Σ∪{ε} 一文字割当 Xi ・ Xｊ i, j は整数で， i, j < k 連結 ( Xi ) j i, j は整数で， i < k 繰り返し [ j ]Xi i, j は整数で， i < k 前切り落とし Xi [ j ] i, j は整数で， i < k 後切り落とし ||D|| = n : D中のトークンの個数 X.u ： トークン X が表す文字列 S : D で割当てられたトークンの列（符号列に相当） Xi1 Xi2 ・・・Xil ( Xi は D中のトークン) |S| = l : トークンの列の長さ

12 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 中のトークンの集合

13 LZWのコラージュシステム S : Xi1 Xi2・・・Xin D : X1 = a1; Xq+1 = Xi1 bi2; X2 = a2;
Xq = aq; Xq+n-1 = Xin-1 bin ={a1, ..., aq} ただし bj は Xj .u の先頭の文字

14 Xq+1 = (( [i1]Xl(1) Xl(1)+1 ・・・ Xr(1))m1)[ j1] b1;
LZSSのコラージュシステム 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 

15 文法変換による圧縮（Kiefferら(2000)）
grammar transformer テキストT 文脈自由文法 GT grammar encoder 圧縮テキスト X1 = 0 ; X2 = 1 ; D : X5 = X1・X4; X4 = X1・X3; X3 = X2・X2; E D C B A X6 = X5・X2; X7 = X4・X2 S : X7 X5 X6 X6 X3 X7 S → ACBBEA A → D1 B → C1 C → 0D D → 0E E → 11

16 研究背景 コラージュシステム コラージュシステム上の照合アルゴリズム 圧縮テキストに対する近似文字列照合問題 まとめ

17 コラージュシステムに対する文字列照合 Xi1 Xi2 Xi3 Xi4 a b 3 4 1 1 2 2 3 4 4 3 4 5 1 1
パタン= 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

18 関数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

19 関数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)| ) 時間で枚挙できる．

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

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

22 複数パタンへの拡張 入力： テキスト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 ) 時間 m はに含まれるパタンの長さの総和 r はパタンの出現個数

23 アイデア {a,b} a b a b b c a b b Jump( q, X) = AC( q, X.u)
 ={aba,ababb,abca,bb} についてのACオートマトン {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 は X.u の接頭辞} (AC はACオートマトンの遷移関数) ( o はACオートマトンの出力関数)

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

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

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

27 研究背景 コラージュシステム コラージュシステム上の照合アルゴリズム 圧縮テキストに対する近似文字列照合問題 まとめ

28 近似文字列照合問題 CARRIAGE MARRIAGE MASSAGE

29 近似文字列照合問題 MARRIAGE MASS AGE テキスト中のパタンとの編集距離が k 以内の文字列の出現を求める問題 編集距離
文字列 x に文字の挿入・削除・置換の操作を施して文字列 y へ変換するために要する最小操作回数 d MARRIAGE MASSAGE CARRIAGE MARRIAGE MASS AGE 削除 置換 d=1 k=2 d=3

30 近似文字列照合アルゴリズム 動的計画法 オートマトンに基づく手法 ビットパラレル手法 フィルタリング手法 L はマシン依存
Sellers (1980) O(mN) 時間 O(m) 領域 Ukkonen (1985) 平均O(kN) 時間 O(m) 領域 オートマトンに基づく手法 Ukkonen (1985) O( min(3m, m(2m||)k) ) 個の状態数 ビットパラレル手法 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 詳しい人

31 圧縮テキスト上の近似文字列照合 Kärkkäinenら(2000)のアルゴリズム 提案アルゴリズム r はパタンの出現個数
動的計画法を使った近似文字列照合アルゴリズムに基づく 最悪時 O(mkn+r ) 時間、平均 O(k2n+r ) 時間 LZ78圧縮テキスト上で動作 提案アルゴリズム 非決定性オートマトンの動作をビットパラレル手法で模倣するBaeza-Yates & Navarro (1999) のアルゴリズムを拡張 最悪時 O(mk3n / L) 時間 制限されたCollage system上で動作 → LZ78/LZW上で動作 n は圧縮テキストの長さ m はパタンの長さ r はパタンの出現個数

32 LZW圧縮法に対する実験結果 CPU時間（秒） 許容される最大の編集距離 k 10 20 30 1 2 3 4 5 40 50 60 70
10 20 30 1 2 3 4 5 許容される最大の編集距離 k CPU時間（秒） 40 50 60 70 80 Intel Pentium III 550MHz (RAM: 64Mb; Linux) Wall Street Journal の記事（英文テキスト）10Mbyte パタンの長さ＝10 提案アルゴリズム Kärkkäinenらのアルゴリズム 復号後に[Myers98]で照合

33 圧縮テキストに対する近似文字列照合の高速化
フィルタリング手法（Filtration technique; Wu and Manber, 1992） パタンを k+1 個の小片に分割 各小片を複数パタン文字列照合アルゴリズムで照合 小片が出現した近辺を通常用いられる近似文字列照合アルゴリズムを用いて検査 テキスト: ACCCTGTTTAGATCACGGCACTACTGTAAAC 分割後の小片: TAAAT, CACGG, CATACT k = 2 の場合 パタン: TAAATCACGGCATACT 圧縮テキストに対してフィルタリング手法を適用 圧縮テキスト上の複数パタン文字列照合アルゴリズムが必要 圧縮テキストを部分的に復号する必要がある

34 圧縮テキスト上の複数パタン照合アルゴリズム
Aho-Corasick型 T. Kida, M. Takeda, A. Shinohara, M. Miyazaki, and S. Arikawa, Multiple pattern matching in LZW compressed text. 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. ビットパラレル型 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.

35 LZW圧縮法における実験結果 CPU時間（秒） 許容される最大の編集距離 k 1 2 3 4 5 6 7
Intel Pentium III 550MHz (RAM: 64Mb; Linux) Wall Street Journal の記事（英文テキスト）10Mbyte パタンの長さ＝10 復号後にフィルタリング手法で照合 復号後に[Myers98]で照合 圧縮テキストにフィルタリング/AC 圧縮テキストにフィルタリング/BM 圧縮テキストにフィルタリング/BP * ACはAho-Corasick型の圧縮テキスト上の 　複数パタン文字列照合アルゴリズム * BPはBit-parallel型のアルゴリズム[Navarro+99] * BMはBoyer-Moore型のアルゴリズム[Navarro+00]

36 LZW圧縮法における実験結果 CPU時間（秒） 許容される最大の編集距離 k 7 6 5 4 3 2 1 1 5 10 15
圧縮テキストにフィルタリング/AC 6 復号後にフィルタリング手法で照合 5 圧縮テキストにフィルタリング/BM 圧縮テキストにフィルタリング/BP CPU時間（秒） 4 復号後に[Myers98]で照合 3 2 Intel Pentium III 550MHz (RAM: 64Mb; Linux) Wall Street Journal の記事（英文テキスト）10Mbyte パタンの長さ＝30 1 1 5 10 15 許容される最大の編集距離 k

37 LZW圧縮法における実験結果 CPU時間（秒） 許容される最大の編集距離 k 8 7 6 5 4 3 2 1 1 5 10 15
Intel Pentium III 550MHz (RAM: 64Mb; Linux) DNA塩基配列　10Mbyte パタンの長さ＝30 7 6 5 CPU時間（秒） 圧縮テキストにフィルタリング/BM 4 復号後にフィルタリング手法で照合 3 復号後に[Myers98]で照合 2 圧縮テキストにフィルタリング/AC 1 圧縮テキストにフィルタリング/BP 1 5 10 15 * ACはAho-Corasick型の圧縮テキスト上の 　複数パタン文字列照合アルゴリズム 許容される最大の編集距離 k * BPはBit-parallel型のアルゴリズム[Navarro+99] * BMはBoyer-Moore型のアルゴリズム[Navarro+00]

38 まとめ コラージュシステムを提案 コラージュシステム上の文字列照合アルゴリズムを開発 実験結果 単一パタンに対するアルゴリズム
O( (||D||+|S|) ・height(D) + ||2 + r ) 時間，O( ||D|| + ||2 ) 領域 複数パタンに対するアルゴリズム 近似文字列照合アルゴリズム ビットパラレル手法に基づくアルゴリズム→O(k3||n /L) 時間 フィルタリング手法による高速化 実験結果 LZW圧縮テキスト 通常用いられる文字列照合法に比べ約2倍高速 近似文字列照合－kが小さい場合に最高約3倍高速 Byte pair encoding (BPE)圧縮テキスト 非圧縮テキストに対する照合よりも約1.8～3.7倍高速 圧縮率が良いテキストに対してAgrepより高速