A Unifying Framework for Compressed Pattern Matching Takuya Kida, Masayuki Takeda, Ayumi Shinohara, Yusuke Shibata, Setsuo Arikawa String Processing and Information Retrieval ‘99 竹田研究室 博士課程一年 喜田 拓也 発表内容 1. 2. 3. 4. 5. 6. [2/30] 圧縮テキスト上での文字列照合問題について 辞書式データ圧縮について Collage systemについて Collage systemに対する文字列照合アルゴリズム 今回の研究で得られたこと まとめ 文字列照合問題 パターン: compress テキスト: [3/30] We introduce a general framework which is suitable to capture an essence of compressed pattern matching compress according to various dictionary based compress compressions. The goal is to find all occurrences of a pattern in a text without decompression, which is one of the most active compress topics in string matching. Our framework includes such compression methods as Lempel-Ziv family, (LZ77, LZSS, compress 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. compress 圧縮テキスト上の文字列照合問題 普通の 文字列照合機械 展開 原テキスト 圧縮テキスト 圧縮テキストに対する 文字列照合機械 圧縮テキスト [4/30] これまでの研究(1) 年 研究者 圧縮法 1988 1992 1992 1994 1994 1995 1996 1996 1997 1997 Eliam-Tsoreff and Vishkin Amir, Landau, and Vishkin Amir and Benson Amir, Benson, and Farach Manber Farach and Thorup Gasieniec, et al. Amir, Benson and Farach Karpinski, Rytter, and Shinohara run-length two-dimensional run-length two-dimensional run-length two-dimensional run-length Miyazaki, Shinohara, and Takeda 1997 Takeda 1998 Fukamachi, Shinohara, and Takeda 1998 Kida, et al. 1998 Shibata original compression scheme LZ77 LZ77 LZW straight-line programs straight-line programs finite state encoding Huffman encoding LZW byte pair encoding これまでの研究(2) 年 研究者 圧縮法 1998 de Moura, Navarro, Ziviani, and Baeza-Yates Word based encoding 1999 Shibata, Takeda, Shinohara, and Arikawa ほんと、 Antidictionaries and 1999 Kida, Takeda, Shinohara, 速い Arikawa LZW よ。 1999 Navarro and Raffinot 1999 Shibata, et al. 1999 Kida, et al. LZ family Byte pair encoding Dictionary based methods (Collage system) 今回の研究の目的 従来: 今回: 圧縮方法 A 照合アルゴリズム A 圧縮方法 B 照合アルゴリズム B 圧縮方法 C 照合アルゴリズム C 圧縮方法 A 圧縮方法 B 圧縮方法 C [7/30] 統 一 的 枠 組 み 統一的枠組みに対する 照合アルゴリズム 辞書式データ圧縮 符号化 原テキスト 語の切り出し 圧縮 符号化列 辞書構造 原テキストからどのように語を切り出すか どのような辞書構造を用いるか どのようにビット列の割り当てるか [8/30] Collage System Definition and Several Examples Collage systemの定義 Collage system とは組〈D, S 〉 D : 変数定義の列(辞書構造に相当) X1 = expr1 ; X2 = expr2 ; ・・・ Xn = exprn ; S : D で定義された変数の列(圧縮テキストに相当) S := Xi1 , Xi2 ,・・・, Xil ( Xi ∈D ) ||D|| = n : Dで定義される変数の個数 |S| = l : 列の並びの個数 [10/30] Collage systemの定義 D : 変数定義の列(辞書構造に相当) X1 = expr1 ; X2 = expr2 ; ・・・ Xn = exprn ; ここで exprk とは、 a ・ ・ Xi ・ Xj ・ ( Xi ) j ・ [ j ]Xi [j] ・ Xi [11/30] a ∈Σ∪{ε}, (一文字代入) i, j は整数で、 i, j < k, (連結) i, j は整数で、 i < k, (繰り返し) i, j は整数で、 i < k, i, j は整数で、 i < k, (前切り落とし) (後切り落とし) Collage systemの例 D: X1 = a ; X2 = b ; X3 = X1・X2 ; X4 = X2・X1 ; X5 = ( X3 )3 ; X6 = [ 3 ]X5 ; X7 = X6・X4 ; T(X7) 前3文字 切り取り ab ba ababab bab babba S : X3 , X6 , X4 , X7 abbabbababba X7 X6 3回 X4 X5 X2 X1 X1 X2 a b )3 ) b a 繰り返し X3 [ 3 ] (( height(X7) = 4 height(D) = 4 Collage systemの例 (Byte pair encoding) テキスト: abD DcE D: X1 = a; X2 = b; X3 = c; ababcbabccabcacb D D cb D cc D cacb D E b E c E acb X4 = X1 ・ X2; X5 = X4 ・ X3; abD DcE S : X4 , X5 , X2 , X5 , X3 , X5 , X1 , X3 , X2 [13/30] Collage systemの例 (LZSS[gzip]) 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)) ) b2; [i1]X l(1)・Xl(1)+1 ・・・ Xr(1) 2 ・ ・ ・ [ j n] [i ] m n n Xq+n = (( Xl(n)・Xl(n)+1 ・・・ Xr(n)) ) b n; S : Xq+1 , Xq+2 ,・・・, Xq+n [14/30] Our Algorithm Pattern Matching Algorithm on a Collage System Collage systemに対する文字列照合 Collage system 上での圧縮文字列問題は、 O( ||D|| + m2 ) 領域を用いて O( (||D||+|S|)・height(D) + m2 + r ) 時間 で解決できる。もし切り取り操作がない場合は、 O( ||D|| + |S| + m2 + r ) 時間 で解決できる。 ||D|| : |S| : m : r : Dで定義される変数の個数 列の並びの個数 パターンの長さ テキスト中のパターンの出現個数 アルゴリズムの基本的アイデア パターン:π= a b a b b 0 a 1 b 2 a 3 Knuth-Morris-Pratt(KMP) automaton 状態: 0 1 2 テキスト: a b S : Xi1 Xi2 [17/30] b 7 4 b 5 : goto 関数 : failure 関数 3 4 3 4 5 1 a b a b b a Xi3 Xi4 Jump と Output 関数 Jump( j, u) = δKMP( j, u) • 文字列 u に対応する遷移の連続を模倣する • 定義域はQ×D O(1) 時間 集合 Output( j, u) ={1≦i≦|u| | P = P[1: j]・u[1: i] の接尾辞} • 状態 j に対応するパターンの接頭辞と u を 連結した文字列中に現れるパターンの出現 位置の集合 O( |Output(j,u)| ) 時間 [18/30] Jumpの実現 Jump( q, Xk) について Xk が... O(1) 時間で求まる a Xi ・ Xj 長さ m パターン文字列について 部分文字列連結問題が O(1) で 解決できるなら O(1) 時間 ( Xi ) j O(1) 時間で求まる [ j ]X i Xi [19/30] [j] O( height(Xi) )時間かかる Outputの実現 集合 Output( q, Xk) について、Xk が... O(1) 時間で枚挙可能 a Xi ・ Xj ( Xi ) j O(l ) 時間で列挙できる [ j ]X 枚挙するのに O( l ・height(Xi) ) 時間かかる i Xi [20/30] Xi と Xj の Output の情報をもとに O(l ) 時間で列挙できる [j] アルゴリズムの概要 pattern P and Collage system: 〈D, S 〉 ( S := Xi1 , Xi2 ,・・・, Xin ) Output. All occurrences of the patterns. Input. /* 辞書 D パターンPについて前処理を行う */ preprocess(D); l:=0; q:=0; for j:=1 to n do begin for each dOutput(q, Xij) do report ‘pattern occurs at position l+d ’; q:= Jump(q, Xij); /* 飛ばし読み遷移 */ l:= l + |Xij |; /* オフセット計算 */ end 部分文字列連結問題 例: ある文字列の二つの部分文字列を連結した 文字列が、その文字列の部分文字列かどう か、また部分文字列だったならその位置を 答える問題。 COPACABANA OPA , CABAN [22/30] 連結 OPACABAN 2文字目から始まる 長さ8の部分文字列 (のSuffix trieにおけるノード番号) 部分文字列連結問題の解決法 Suffix trie を用いれば O(m2) 時間領域の前処 理を必要とし、問い合わせに O(m) 時間かかる。 問い合わせにかかる時間を O(1) にするために、 2次元の表を構築すると O(m4) 時間領域の前 処理が必要となる。 O(m2) 時間領域の前処理で、 O(1) 時間で問題を解決。 [23/30] 新手法 A -- … -- … -- … -- -- … -- … 2 … … … 4 … … … … CABAN COPACABANA [24/30] O(m) A … OPA … COPACABANA … O(m2) O(m) O(m2) … 文字列: COPACABANA -- 新手法 k パターン: i 与えられた部分文字列: [25/30] 新手法実現に必要なもの パターン文字列に対するSuffix trie。 パターン文字列を逆順に並べた文字列に対す るSuffix trie。 境界k を求めるための表(Boundary(x,y))。 パターンP の部分文字列P[i, j]に対応する Suffix trieのノードを求めるための表。 これらのデータ構造はすべて O(m2)時間領域で準備できる。 [26/30] Concluding Remarks Conclusion and Future Works 今回の研究によって得られた知見 切り取り操作がない場合 : O( ||D|| + m2 ) 領域 O( ||D|| + |S| + m2 + r ) 時間 1998 Kida, et al.(LZW): O( n + m2 ) 領域 O( n + m2 + r ) 時間 切り取り操作がない LZ78, LZW, Huffman, BPE, Run-length等 [28/30] 切り取り操作がある LZ77, LZSS等 まとめ 様々な辞書式圧縮法の統一的枠組みとして Collage systemを提案した。 Collage systemの枠組みにおける一般的な圧 縮テキスト上の文字列照合アルゴリズムを示 し、その計算量を評価した。 O( (||D||+|S|)・height(D) + m2 + r ) 時間 O( ||D|| + m2 ) 領域 (切り取りなしの場合) O( ||D|| + |S| + m2 + r ) 時間 [29/30] 今後の課題 [30/30] 前処理の計算量を減らせるか。 O(m2) O(m) 複数パターンを同時に照合できるアルゴリズムに 改良する。 近似文字列照合が可能なアルゴリズムを開発する。 圧縮テキスト上の文字列照合に適した圧縮方を新 たに開発する。
© Copyright 2024 ExpyDoc