Collage System 圧縮テキストパターン照合のための統一的枠組み 九州大学大学院システム情報科学研究科情報理学専攻 喜田 拓也 竹田 正幸 篠原 歩 柴田 裕介 有川 節夫 発表内容 九州大学大学院システム情報科学研究科情報理学専攻の喜田拓也です。 それでは「圧縮テキストパターン照合のための統一的枠組み」について発表を始めたいと思います。 テーマは先と同じく「圧縮テキスト上でのパターン照合」ですが、こちらはかなり理論的興味に基づいた話になります。本発表の内容はこのようになっています。 これまでの研究との違い 辞書式データ圧縮について Collage systemについて Collage systemに対する文字列照合アルゴリズム 今回の研究で得られたこと まとめ

これまでの研究(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

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 こちらはごく最近の研究成果です。 今回発表する内容の詳細は文字列処理と情報検索の国際会議SPIRE’99で。 Kida, et al. 1999 Dictionary based methods (Collage system) SPIRE’99

今回の研究の概要 圧縮方法 A 照合アルゴリズム A 従来： 圧縮方法 B 照合アルゴリズム B 圧縮方法 C 照合アルゴリズム C 統一的枠組み 圧縮方法 A 今回の我々の仕事を図示すると、このようになります。 先ほどの年表からわかるように、従来は各々の圧縮方に対して別々の照合アルゴリズムが提案されてきました。 しかし我々はいくつかの研究成果を経て「Amirらのアイデアはより一般的なものに拡張できるのではないか」という考えに至り、統一的枠組み-Collage system-を提案しました。 そしてその枠組みに対する照合アルゴリズムを開発することにより、さまざまな圧縮法に適用可能な統一的照合アルゴリズムを得ることができました。 次にCollage systemの説明に入る前に、辞書式データ圧縮の仕組みについての簡単な説明をさせていただきます。 今回： 統一的枠組みに対する 照合アルゴリズム 圧縮方法 B 圧縮方法 C

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

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 : 列の並びの個数

Collage systemの定義 [ j ]Xi D : 変数定義の列（辞書構造に相当） X1 = expr1 ; ・・・ 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 ] （前切り落とし） （後切り落とし）

Collage systemの例 ab ba ababab bab babba [ 3 ] (( abbabbababba D : X7 )3 ) [ 3 ] (( 前3文字 切り取り 3回 繰り返し T(X7) 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 は下の文字列を表現していることになります。 X7 に注目してください。 X7 の右辺を展開していくと、このような木構造を作ることができます。 この木の高さをheightで表します。 最も木が高い変数のheightをDのheightとします。 S : X3 , X6 , X4 , X7 height(X7) = 4 abbabbababba height(D) = 4

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 X1 = a; D: X4 = X1 ・ X2; abD X2 = b; 先ほどのBPE圧縮をCollage systemで表現するとこのようになります。 X1からX3までは使用されている文字を、 X4 とX5はそれぞれ、未使用文字のDとEに対応しています。 Sはこの文字列をそのまま変数に置き換えたものになっているのがわかります。 X5 = X4 ・ X3; DcE X3 = c; S : X4 , X5 , X2 , X5 , X3 , X5 , X1 , X3 , X2

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 :

Collage systemに対する文字列照合 O( (||D||+|S|)・height(D) + m2 + r ) 時間 O( ||D|| + m2 ) 領域を用いて で解決できる。もし切り取り操作がない場合は、 O( ||D|| + |S| + m2 + r ) 時間 で解決できる。 ||D|| : Dで定義される変数の個数 |S| : 列の並びの個数 m : パターンの長さ r : テキスト中のパターンの出現個数 それではCollage systemに対する文字列照合の説明に移ります。 結果から先に申しますと、O( ||D|| + m2 ) 領域を用いてO( (||D||+|S|)・height(D) + m2 + r ) 時間で解決でき、もし切り取り操作がない場合はO( ||D|| + |S| + m2 + r ) 時間で解決できます。 ここで、mはパターンの長さでr はテキストに出現するパターンの個数です。

1 1 2 2 3 4 4 3 4 5 1 1 abababba アルゴリズムの基本的アイデア a b パターン：π= a b a b b 1 2 4 5 b 3 7 : goto 関数 : failure 関数 アルゴリズムの基本的なアイデアは、先に発表した柴田のものと同じです。 すなわちKMPオートマトンが一文字ずつ遷移するのに対して、変数が表す文字列に対応する遷移の連続を一回の遷移で模倣することです。 このアイデアを実現するためには二つの問題があります。 ひとつはそのような状態遷移が定数時間で行えるかということ。 もうひとつはこのように飛び越してしまったパターンの出現を適切に出力できるかということです。 状態： 1 1 2 2 3 4 4 3 4 5 1 1 abababba テキスト： S ： Xi1 Xi2 Xi3 Xi4

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

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) )時間かかる

部分文字列連結問題 例： COPACABANA OPA , CABAN OPACABAN ある文字列の二つの部分文字列を連結した文字列が、その文字列の部分文字列かどうか、また部分文字列だったならその位置を答える問題。 例： COPACABANA それでは部分文字列連結問題についてですが、これはこのように一つの文字列とその二つの部分文字列が入力として与えられたとき、これらを連結した文字列がもとの文字列の部分文字列になっているかどうかを答える問題です。 OPA , CABAN OPACABAN 連結 2文字目から始まる 部分文字列

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) 時間で問題を解決。

Outputの実現 [ j ]Xi 集合 Output( q, Xk) について、Xk が... a O(1) 時間で枚挙可能 Xi と Xｊ の Output の情報をもとに O(l ) 時間で列挙できる Xi ・ Xｊ ( Xi ) j O(l ) 時間で列挙できる 次にOutputに関してですが、これもJumpと同じく、切り落としの場合のみ木の高さ倍だけ時間がかかることがわかっています。 [ j ]Xi Xi [ j ] 枚挙するのに O( l ・height(Xi) ) 時間かかる

アルゴリズムの概要 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の変数の並びを前から順に読み込んでいき、パターンの出現があればここで報告し、そののち次の状態を決定します。

今回の研究によって得られた知見 切り取り操作がない場合 : O( ||D|| + m2 ) 領域 O( ||D|| + |S| + m2 + r ) 時間 1998 Kida, et al.（LZW）: O( n + m2 ) 領域 O( n + m2 + r ) 時間 今回の研究で得られた結果は、我々の過去の結果に見事に符合しています。 これはLZW圧縮法においてこの||D|| + |S| というのは圧縮テキスト長nに相当します。 またCollage systemにより、圧縮テキスト上のパターン照合に適した圧縮法とそうでない圧縮法を明確に区分することができました。 今後の課題としては、この知見をもとにより圧縮上のパターン照合に適した圧縮法を開発することが挙げられます。 以上です。 切り取り操作がない 切り取り操作がある LZ88, LZW, Huffman, BPE, Run-length等 LZ77, LZSS等

まとめ 様々な辞書式圧縮法の統一的枠組みとしてCollage systemを提案した。 O( (||D||+|S|)・height(D) + m2 + r ) 時間 O( ||D|| + m2 ) 領域 （切り取りなしの場合） O( ||D|| + |S| + m2 + r ) 時間