A Unifying Framework for Compressed Pattern Matching

Presentation on theme: "A Unifying Framework for Compressed Pattern Matching"— Presentation transcript:

1 A Unifying Framework for Compressed Pattern Matching
Takuya Kida, Masayuki Takeda, Ayumi Shinohara, Yusuke Shibata, Setsuo Arikawa String Processing and Information Retrieval ‘99 竹田研究室 博士課程１年の喜田です。 それでは「A Unifying Framework for Compressed Pattern Matching」についての発表を始めたいと思います。 この論文は先月下旬にメキシコで開かれました文字列処理と情報検索の国際会議String Processing and Information Retrieval ’99(SPIRE’99)で発表したものです。 竹田研究室 博士課程一年　喜田 拓也

2 発表内容 圧縮テキスト上での文字列照合問題について 辞書式データ圧縮について Collage systemについて
今回の研究で得られたこと まとめ 発表の内容はこのようになっています。 まず、我々の研究テーマであります「圧縮テキスト上での文字列照合」について説明します。 今回のメインのトピックはCollage systemとそれに対する文字列照合アルゴリズムです。 そして最後にまとめという流れです。

3 文字列照合問題 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. compress 修士１年の方の中には「文字列照合問題（パターンマッチング）」という言葉を始めて聞く人もいるかと思います。 手短に説明しますと、文字列照合問題とは、パターンとテキストと呼ばれる二つの文字列が与えられたときに、テキスト中に含まれるパターンの出現を見つけ報告するという問題です。 この例の場合、このパターン文字列はテキストのこれらの位置に出現するということを出力します。 この文字列照合問題を解決するアルゴリズムとしては、Knutu-Morris-Pratt法やBoyer-Moore法、Shift-And法など、すでにいくつかの手法が提案されていまして、どれもテキストの長さに比例した時間で問題を解くことが出来ます。 ただし、それはテキストが素のまま保存されている場合に限ります。 もしテキストが圧縮して保存されている場合にはどのようにすればよいでしょうか。

4 圧縮テキスト上の文字列照合問題 原テキスト 普通の 文字列照合機械 展開 圧縮テキストに対する 文字列照合機械 圧縮テキスト 圧縮テキスト
すぐに思いつく方法としては、一度もとのテキストに展開してから照合を行うという方法が考えられます。 しかしこの方法では展開するだけ余分なコストがかかります。 そこでどうにかして圧縮テキストを展開せずに、直接文字列照合できれば、より高速に照合が行えると考えられます。 これが圧縮テキスト上の文字列照合問題です。 圧縮テキスト

5 これまでの研究(1) 年 研究者 圧縮法 1988 Eliam-Tsoreff and Vishkin run-length 1992
Amir, Landau, and Vishkin two-dimensional run-length 1992 Amir and Benson two-dimensional run-length Amir, Benson, and Farach 1994 two-dimensional run-length 1994 Manber original compression scheme 1995 Farach and Thorup LZ77 1996 Gasieniec, et al. LZ77 1996 Amir, Benson and Farach LZW 1997 Karpinski, Rytter, and Shinohara straight-line programs 1997 Miyazaki, Shinohara, and Takeda straight-line programs この分野の研究は、８８年の論文に始まり、この１０年間ですでに多くの圧縮法に対するパターン照合アルゴリズムが提案されてきました。 データ圧縮に一度でも興味を持たれた方はご存知だと思いますが、現在主流な圧縮プログラムの基礎となっているLZ77法やLZW法についての照合アルゴリズムが96年ごろに提案されています。 この中でも特に我々が注目したのがこのAmir, Benson, Farachによるアルゴリズムでした。 98年我々は、Amirたちのアイデアをもとに、よりシンプルで実用性に富んだアルゴリズムを提案しました。 このアルゴリズムは複数のパターンを同時に照合可能で、しかもテキスト中に含まれるすべての出現位置を報告することができます。 1997 Takeda finite state encoding 1998 Fukamachi, Shinohara, and Takeda Huffman encoding 1998 Kida, et al. LZW 1998 Shibata byte pair encoding

6 Dictionary based methods
これまでの研究(2) 年 研究者 圧縮法 1998 de Moura, Navarro, Ziviani, and Baeza-Yates Word based encoding 1999 Shibata, Takeda, Shinohara, and Arikawa ほんと、速いよ。 Antidictionaries 1999 Kida, Takeda, Shinohara, and Arikawa LZW 1999 Navarro and Raffinot LZ family 1999 Shibata, et al. Byte pair encoding こちらはごく最近の研究成果です。 これら印のついた論文で提案されたアルゴリズムは、実用的にも有益であることが分かっています。 特にこのアルゴリズムは、圧縮されていないテキストを照合するよりも高速に照合できることが分かっています。 Kida, et al. 1999 Dictionary based methods (Collage system)

7 今回の研究の目的 圧縮方法 A 照合アルゴリズム A 従来： 圧縮方法 B 照合アルゴリズム B 圧縮方法 C 照合アルゴリズム C
統一的枠組み 圧縮方法 A 統一的枠組みに対する 照合アルゴリズム 圧縮方法 B 圧縮方法 C 今回： この年表からわかるように、従来は各々の圧縮方に対して別々の照合アルゴリズムが提案されてきました。 これに対し、今回我々は各圧縮法を統一的に記述できるCollage systemという枠組みを提案し、そしてその枠組みに対する照合アルゴリズムを開発しました。 このことによって、この枠組みで表現できる任意の圧縮法に適用可能な照合アルゴリズムを得たことになります。 それではCollage systemの説明に入りたいと思いますが、その前に辞書式データ圧縮の仕組みについて、少しだけ説明させてください。

8 辞書式データ圧縮 原テキスト 圧縮 符号化列 辞書構造 原テキストからどのように語を切り出すか どのような辞書構造を用いるか
語の切り出し 辞書式データ圧縮では、まず原テキストから繰り返し使用される語を切り出し、それらをなんらかの辞書構造に蓄えます。 そして登録された語に符号を割り当て、その情報をもとに原テキストを符号化します。 最終的に、この辞書構造と符号化列が圧縮データとして保存されます。 各圧縮法の違いとは、原テキストからどのように語を切り出していくか、どのような辞書構造を使用するか、そしてどのように符号化すなわちどのようなビット列を語に割り当てるかという違いです。 データ圧縮の観点からいうとこれらの違いは重要な問題ですが、圧縮テキスト上の文字列照合の観点から見るとこれらの違いはあまり本質的ではありません。 文字列照合に必要なのは、この符号化列と、各符号がどんな文字列に対応しているかという情報だけです。 それではCollage systemの説明に入りましょう。 原テキストからどのように語を切り出すか どのような辞書構造を用いるか どのようにビット列の割り当てるか

9 Collage System Definition and Several Examples

10 Collage systemの定義 Collage system とは組〈D, S 〉 D : 変数定義の列（辞書構造に相当）
X1 = expr1 ; ・・・ X2 = expr2 ; Xn = exprn ; S : D で定義された変数の列（圧縮テキストに相当） S := Xi1 , Xi2 ,・・・, Xil ( Xi ∈D ) Collage systemはこのように組〈D, S 〉で定義されます。 ここで、D は辞書式データ圧縮における辞書構造に相当します。 S はD で定義された変数の並びであり、圧縮テキストに相当するものです。 ここでD における変数定義には次のようにします。 ||D|| = n : Dで定義される変数の個数 |S| = l : 列の並びの個数

11 Collage systemの定義 ・ ・ ・ ・ [ j ]Xi ・ D : 変数定義の列（辞書構造に相当） X1 = expr1 ;
・・・ X2 = expr2 ; Xn = exprn ; ここで exprk とは、 ・ a a ∈Σ∪{ε}, （一文字代入） ・ Xi ・ Xｊ i, j は整数で、 i, j < k, （連結） 変数を定義する式の右辺はこれら五つの表現を許すことにします。 まず一番上は一文字代入。 次に変数の連結。これは各々の変数が表している文字列を連結することを意味します。 その次が繰り返しで、これはこの変数が表している文字列を j 回繰り返した文字列を表します。 残りは切り落としです。これは変数Xi が表している文字列の前後をj 文字切り落とした文字列を表現します。 それではCollage systemの例をいくつか見てみましょう。 ・ ( Xi ) j i, j は整数で、 i < k, （繰り返し） ・ [ j ]Xi i, j は整数で、 i < k, Xi [ j ] （前切り落とし） （後切り落とし） ・

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

13 Collage systemの例 （Byte pair encoding）
a b a b c b a b c c a b c a c b テキスト： abD D D c b D c c D c a c b DcE D E b E c E a c b D: X1 = a; X2 = b; X4 = X1 ・ X2; X5 = X4 ・ X3; X3 = c; S : X4 , X5 , X2 , X5 , X3 , X5 , X1 , X3 , X2 abD DcE 実際の圧縮法での例を挙げます。 あまりメジャーではないですが、分かりやすい例としてBPE圧縮をCollage systemで表現してみます。 BPE圧縮法はテキスト中に最も頻出する文字のペアを、未使用の文字に置き換えることでテキストを圧縮していきます。 この例では、まずabをDに置き換え、次にDcをEに置き換えています。 そしてこれが圧縮テキストとなります。 これをCollage systemで表現すると、このようになります。 X1からX3までは使用されている文字を、 X4 とX5はそれぞれ、未使用文字のDとEに対応しています。 Sはこの文字列をそのまま変数に置き換えたものになっているのがわかります。

14 Collage systemの例 （LZSS[gzip]）
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; ・・・ LZSSはLZ77の改良アルゴリズムで、gzipの基本アルゴリズムとして知られています。 かなり複雑な記述ですが、このように一般的にCollage systemで表現することが可能です。 ここでは、記述の簡便のために複数の変数定義の表現をひとつの変数定義で書き表していますが、 これを元々のCollage systemの定義にそって分解することは簡単です。 具体的に変数の割り当てがどのようになるかは、与えられるテキストと圧縮法に依存します。 繰り返しになりますが、圧縮テキスト上での文字列照合という観点からは、テキストがどのような方法で圧縮されるかは本質的ではありません。 圧縮後の符号列と、その各符号がどのような文字列に対応しているかということとが重要です。 Xq+n = (( [in]Xl(n)・Xl(n)+1 ・・・ Xr(n))mn)[ jn] bn; Xq+1 , Xq+2 ,・・・, Xq+n S :

15 Pattern Matching Algorithm
Our Algorithm Pattern Matching Algorithm on a Collage System それではCollage systemに対する文字列照合の説明に移りたいと思います。

16 Collage systemに対する文字列照合
O( (||D||+|S|)・height(D) + m2 + r ) 時間 O( ||D|| + m2 ) 領域を用いて で解決できる。もし切り取り操作がない場合は、 O( ||D|| + |S| + m2 + r ) 時間 で解決できる。 ||D|| : Dで定義される変数の個数 |S| : 列の並びの個数 m : パターンの長さ r : テキスト中のパターンの出現個数 結果から先に申しますと、O( ||D|| + m2 ) 領域を用いてO( (||D||+|S|)・height(D) + m2 + r ) 時間で解決でき、もし切り取り操作がない場合はO( ||D|| + |S| + m2 + r ) 時間で解決できます。 ここで、mはパターンの長さでr はテキストに出現するパターンの個数です。 また||D|| + |S|というのは圧縮テキスト長に相当することに注意してください。 すなわちこのアルゴリズムは、切り取り操作がない場合、ほぼ最適な時間計算量といえます。

17 3 4 1 1 2 2 3 3 4 4 3 4 5 1 1 abababba アルゴリズムの基本的アイデア a b
1 2 4 5 b 3 Knuth-Morris-Pratt(KMP) automaton 7 : goto 関数 : failure 関数 アルゴリズムの基本的なアイデアは、非常に単純です。 すなわちKMPオートマトンが一文字ずつ遷移するのに対して、変数が表す文字列に対応する遷移の連続を一回の遷移で模倣することです。 KMPオートマトンとはすごろくのようなもので、テキストを一文字ずつ読み取り、状態を遷移していき、一番最後の状態にたどり着いたらパターン文字列が見つかったと報告します。 つまりSがこのようになっていた場合、上の遷移に対して、このように飛び飛びの遷移を実現しようというのが我々のねらいです。 ただし、このアイデアを実現するためには二つの問題があります。 ひとつは任意の入力に対し、このような飛ばし読み状態遷移が定数時間で行えるかということ。 もうひとつはこのように飛び越してしまったパターンの出現を適切に出力できるかということです。 3 4 状態： 1 1 2 2 3 3 4 4 3 4 5 1 1 abababba テキスト： S ： Xi1 Xi2 Xi3 Xi4

18 Jump と Output 関数 Jump( j, u) = δKMP( j, u) 集合 Output( j, u)
定義域はQ×D O(1) 時間 集合 Output( j, u) ={1≦i≦|u| | P = P[1: j]・u[1: i] の接尾辞} これらの問題を解決するために、このような関数Jumpと集合Outputを定義する必要があります。 関数Jumpは飛ばしよみ状態遷移関数で、集合Outputは飛ばし読みの途中に含まれるパターンの出現位置をその要素に持ちます。 要はこの関数Jumpが定数時間で値を返し、集合Outputを列挙する手続きがその集合の要素数に比例した時間で走ることができればよいわけです。 状態 j に対応するパターンの接頭辞と u を 連結した文字列中に現れるパターンの出現 位置の集合 O( |Output(j,u)| ) 時間

19 Jumpの実現 Jump( q, Xk) について Xk が... [ j ]Xi a O(1) 時間で求まる
部分文字列連結問題が O(1) で解決できるなら O(1) 時間 Xi ・ Xｊ 結果だけを言います。 まずJumpについて、入力された変数Xkが一文字代入のときは明らかにO(1)で答えられます。 問題はそれ以外です。 連結の場合は、この「部分文字列連結問題」がO(1)で解決できるならO(1)で答えられます。 この部分文字列連結問題はあとで説明します。 繰り返しの場合は、連結の場合の結果を用いることでO(1)で済むことが証明できます。 切り落としの場合のみ、Xiの木の高さに比例した時間かかります。 何故そうなるかを簡単に説明すると、文字列を切り落とすことにより Xiが持つJumpの情報がどのように修正されるかを木を手繰ることによって調べる必要があるからです。 ( Xi ) j O(1) 時間で求まる [ j ]Xi Xi [ j ] O( height(Xi) )時間かかる

20 Outputの実現 [ j ]Xi 集合 Output( q, Xk) について、Xk が... a O(1) 時間で枚挙可能
Xi と Xｊ の Output の情報をもとに O(l ) 時間で列挙できる Xi ・ Xｊ ( Xi ) j O(l ) 時間で列挙できる 次にOutputに関してですが、入力された変数Xkが一文字代入のときは明らかにO(1)で枚挙できます。 連結の場合は、XiとXjのOutputの情報をもとにO(l)時間で列挙できます。 ここでl はXkに含まれるパターン文字列の個数です。 繰り返しの場合も、連結の時の結果からO(l)時間で列挙できることが証明できます。 切り落としの場合のみ、枚挙するのにheight倍だけかかります。 この理由もJumpの時と同じで、Xiの中に出現するパターンが、Xkにおいても出現するかどうかを調べるために、Xiの木のノードを手繰っていく必要があるからです。 [ j ]Xi Xi [ j ] 枚挙するのに O( l ・height(Xi) ) 時間かかる

21 アルゴリズムの概要 Input. pattern P and Collage system: 〈D, S 〉
( S := Xi1 , Xi2 ,・・・, Xin ) Output. All occurrences of the patterns. /* 辞書 D パターンPについて前処理を行う */ preprocess(D); l:=0; q:=0; for j:=1 to n do begin for each dOutput(q, Xij) do report ‘pattern occurs at position l+d ’; q:= Jump(q, Xij); /* 飛ばし読み遷移 */ l:= l + |Xij |; /* オフセット計算 */ end 以上JumpとOutputを用いると、照合アルゴリズムはこのような簡単なプロシージャとして書くことが出来ます。 つまりSの変数の並びを前から順に読み込んでいき、パターンの出現があればここで報告し、そののち次の状態を決定します。

22 （のSuffix trieにおけるノード番号）
部分文字列連結問題 ある文字列の二つの部分文字列を連結した文字列が、その文字列の部分文字列かどうか、また部分文字列だったならその位置を答える問題。 例： COPACABANA それでは次に、先ほど棚上げしておいた部分文字列連結問題について説明します。 これはこのように一つの文字列とその二つの部分文字列が入力として与えられたとき、これらを連結した文字列がもとの文字列の部分文字列になっているかどうかを答える問題です。 この例ではOPA, CABANはどちらもこの文字列の部分文字列で、これらを連結したOPACABANももとの文字列の部分文字列です。 OPA , CABAN OPACABAN 連結 2文字目から始まる 長さ８の部分文字列 （のSuffix trieにおけるノード番号）

23 O(m2) 時間領域の前処理で、 O(1) 時間で問題を解決。
部分文字列連結問題の解決法 Suffix trie を用いれば O(m2) 時間領域の前処理を必要とし、問い合わせに O(m) 時間かかる。 問い合わせにかかる時間を O(1) にするために、２次元の表を構築すると O(m4) 時間領域の前処理が必要となる。 部分文字列といえばSuffix trieということで、Suffix Trieを用いればO(m)時間で答えを返すことが出来ます。 しかしそれでは都合が悪いのでO(1)時間で答えられるようにするためにルックアップテーブルを作ることを考えます。 長さｍの文字列の部分文字列の個数はO(ｍ2)なのでそのような2次元の表はO(ｍ4)の大きさになり、 O(ｍ4)時間領域の前処理が必要となります。 これに対し、我々はO(ｍ2)時間領域の前処理を行うことで、部分文字列連結問題をO(1)時間で答えられるテクニックを論文の中で示しました。 O(m2) 時間領域の前処理で、 O(1) 時間で問題を解決。

24 新手法 O(m) O(m2) O(m2) 文字列： COPACABANA 4 2 A … OPA COPACABANA -- CABAN
どういうことかといいますと、Suffix trieのノード全ての分のマスを縦横用意しなくとも、そのexplicitノードのみのマスだけで十分である、ということなんです。 が、（だれでもいいけど）松本君が「なんのこっちゃ」という顔をしているので、もう少し分かりやすくそのトリックを説明しましょう。 文字列： COPACABANA

25 k i 新手法 パターン： 与えられた部分文字列： これら棒が文字列を表していると思ってください。
また与えられた部分文字列を連結した文字列が、もとの文字列の部分文字列でこの部分に現れているとします。 このとき部分文字列連結問題ではi番目から始まる部分文字列という答えを返さなければなりません。 が、ここでオレンジを少しだけ左に伸ばした部分文字列と青い部分文字列の連結を考えてみましょう。 もしその連結が、このような位置の部分文字列だった場合、返すべき答えは異なりますが、この境目の部分は一致します。 この境目を基準に考えると、オレンジと青の連結を求めるときには、オレンジの代わりに少し伸ばした赤＋オレンジの部分文字列を用いることで境目kの値を求めることができます。 kが求まればそこからこの文字列の長さを引き算することで部分文字列連結問題の答えが分かります。 すなわち前の表のオレンジについてのカラムを除くことができるわけです。 このようにして、結局、表の縦横をそれぞれO(m)まで減らすことができます。

26 これらのデータ構造はすべてO(m2)時間領域で準備できる。
新手法実現に必要なもの パターン文字列に対するSuffix trie。 パターン文字列を逆順に並べた文字列に対するSuffix trie。 境界k を求めるための表（Boundary(x,y)）。 パターンP の部分文字列P[i, j]に対応するSuffix trieのノードを求めるための表。 実際にこのアイデアを照合アルゴリズムに組み込むためには、このような４つのデータ構造を駆使する必要があるので、係数がやや大きくなりますが、定数時間で部分文字列照合問題の問い合わせに答えることができます。 これらのデータ構造はすべてO(m2)時間領域の前処理で準備することができます。 これらのデータ構造はすべてO(m2)時間領域で準備できる。

27 Concluding Remarks Conclusion and Future Works それでは、まとめにはいりたいと思います。

28 今回の研究によって得られた知見 切り取り操作がない場合 : O( ||D|| + m2 ) 領域
O( ||D|| + |S| + m2 + r ) 時間 1998 Kida, et al.（LZW）: O( n + m2 ) 領域 O( n + m2 + r ) 時間 この||D|| + |S| というのは圧縮テキスト長nに相当し、またLZW圧縮は切り落としを含まないCollage systemで表現することが出来ます。 つまり今回の研究で得られた結果は、我々の過去の結果に見事に符合しています。 この計算量はほぼ最適であるといえます。 またCollage systemにより、圧縮テキスト上のパターン照合に適した圧縮法とそうでない圧縮法をこのように明確に区分することができました。 Combinatorial Pattern Matching(CPM’99)という国際会議において、NavarroとRaffinotらが発表した論文のなかに、LZ77よりもLZ78の方が圧縮テキスト上の文字列照合に適しているという考察がありますが、我々の結果も同じことを示しています。 切り取り操作がない 切り取り操作がある LZ78, LZW, Huffman, BPE, Run-length等 LZ77, LZSS等

29 まとめ 様々な辞書式圧縮法の統一的枠組みとしてCollage systemを提案した。
O( (||D||+|S|)・height(D) + m2 + r ) 時間 O( ||D|| + m2 ) 領域 （切り取りなしの場合） O( ||D|| + |S| + m2 + r ) 時間 以上、辞書式圧縮法の統一的枠組みとして、Collage systemを提案しました。 またCollage system上での文字列照合アルゴリズムを示し、その計算涼を評価しました。

30 今後の課題 前処理の計算量を減らせるか。 O(m2)  O(m) 複数パターンを同時に照合できるアルゴリズムに改良する。
近似文字列照合が可能なアルゴリズムを開発する。 圧縮テキスト上の文字列照合に適した圧縮方を新たに開発する。 今後の課題としては、前処理にO(m2)かかっていた部分をO(m)に落とせるかどうか、 複数パターンを同時に照合可能なアルゴリズムに改良できるか、 また近似文字列照合が可能なアルゴリズムの開発、 今回得られた知見に基づく新しい圧縮法の開発などが挙げられます。 以上です。