      論文

 を圧縮データ索引として利用できる．残念ながらこの最適化
データ圧縮の理論に基づく効率的 問題は
困難であるが，近似的解法についてはよい結果が知ら
れている．
な索引構造

入力長を とするとき，最適解に対する近似率  を達         成するいくつかのアルゴリズム
   が知られており，圧縮  
率の理論的観点からは，これらはほぼ最適と見なしてよい．ただし，いずれも接尾辞木  の構築などで   領域を必要とする
岸上 直也
田中 洋平 ため，これらの手法は規模耐性が低い．一方，理論的保証はない
ものの，実用的にはコンパクトな  を高速に求めることが可
坂本 比呂志能であるため， や    をはじめ，多くの圧縮法が提案されている     ．
これらの  圧縮は，最適性または規模耐性のいずれかの点で欠点がある．これに対して，  で提案された  圧縮
法は，アルファベットや変数がテキスト中に最初に出現する位置
本研究では，アルファベット還元と呼ばれるデータ圧縮法を応 情報のみを使用する単純な手法に基づき，最適解に対する近似率
用した，圧縮データそのものを索引とする高速・省スペースなデー £ 
 を保証する．ここで £ は，

タ構造を提案する．アルファベット還元とは，特別な作業領域を必を満たすの最大回数を表し，   のような巨大な数£   に過ぎないため，実用的には定数と考えて要としない理論的に最適な圧縮法であり，テキスト中の共通する に対しても部分文字列を同じ文字によって符号化するという特性を持つ．本 よい．したがって，これは準最適な圧縮と見なせる．そこで，こ研究では，この特性を応用して，符号化された文字とグラフラベ の  からテキストに関する情報をすばやく取り出すことがでリングによる補助情報のみから元の部分文字列の出現を高速に判 きれば，省スペースかつ高速な索引として利用できる．
定する手法を提案し，予備的な実験によってその有効性を示す．
これまでの圧縮法が，テキスト中の部分文字列に対する何らかの索引を必要としていたのに対して，  のアルゴリズムは，圧縮を行うための作業用領域として，それまでに生成した  の変数以外の領域を必要としないため，飛躍的に省スペースである    
ことが保証できる．本研究で提案する圧縮データ索引は，この圧
縮アルゴリズムに基づいている．
 の  圧縮では，アルファベット還元  と呼ばれる文字の変換を利用している．ここでその概略を述べる．テキストの番目の文字とその直前の文字との単純な演算 例えば加算 によってある文字を決める．この文字をテキストの 番目の文字のラベルと呼ぶ． を動かすことによって，テキストと同じ長さのラベルの列ができる．ここで重要なことは，テキストに文字  が複数出現するとき，それらの左隣の文字が同じならば，それらの  のはじめに
ラベルは必ず一致するということである．同様にこのラベル列を
本研究では，圧縮されたデータに対する軽量・高速なパターン テキストと見なして同じ計算を行うと，今度は長さ  の文字列が検索手法を提案する．ここで対象とする検索は，完全な部分文字 一致するという情報を次のラベルに埋め込むことができる．この列の一致を判定することであり，テキスト とパターン  が与 計算を繰り返すことで，テキスト中の任意の長さの部分文字列にえられたとき， が に出現するか否かを判定する問題や  が 関する情報をラベルに埋め込むことができる．この計算は隣り合に出現する場所および回数を出力する問題のことである．した う文字同士の単純な演算にすぎないため，補助的なデータ構造やがって，正規表現やミスマッチを許した近似照合などは本研究の 部分文字列に関する情報を一切必要としない．  の  圧縮
では，この埋め込まれた情報を利用することで効率的に同一部分対象外である．
本研究で提案する圧縮法は，  圧縮と呼ばれる枠組みに含 文字列の置換が可能になる．
圧縮データからパターンを検索しようとするとき，テキストのまれる．  圧縮では，あるテキストが与えられたとき，そのテキストのみを生成する制限された文脈自由文法   を考え， 中身が何らかの意味でシャッフルされている場合，原テキストを部
そのような  のうちできるだけ小さなものを見つけることが 分的に復号する必要がある．本提案手法に用いる圧縮法は，テキ目標である．例えば，開始記号  から始まる  の規則   スト中に現れるパターンを出現位置によらず保存するという性質          は，テキスト   のみを生 を持っている．この性質はより正確には，テキスト中のパターン成する最小の  である．ここで，テキストに出現する文字を  の任意の二つの出現が，  および  のように圧縮される
アルファベットと呼び，この例における     のような置換 ことを意味する．ここで， はある一文字の変数であり，    
はパターン  に対して十分に短い文字列を表す．
文字を変数と呼ぶ．
この関係は，テキスト中にパターン  が出現するための必要十もし，最適な  圧縮が効率的に計算できたり，  を展開することなく元テキストに関する情報を取り出すことができれば， 分条件であるため，この性質を用いて圧縮データに対する索引が構築できる．その基本アイディアは，以下のように説明できる．テ£ 九州工業大学大学院情報工学府
キスト中にパターン  が出現するには，辞書に変数  が含まれる    
ことが必要であり， の残りの接頭辞・接尾辞 すなわち     
Ý 九州工業大学大学院情報工学府
に対して同様の検索を行うことで，辞書へのアクセスのみで  の      
出現を確定できる．また， は  の十分長い部分文字列  を十分
Þ 凸版印刷株式会社西日本事業本部に小さい自然数としたとき， のおよそ  に相当する長さ を      Ü 正会員 九州工業大学大学院情報工学研究院および科学技術振興機構
符号化していることが保証できるため，残りの接尾辞・接頭辞に対して上記の再帰的なパターン検索を行うことで， の長さの対  

多比良 嘉成£Ü   ÝÞ         Æ             !    
  "! !      !# $! %&     !      '  (' !  !
# $   '!   &   ' %  !  %  & $     !    ! '! &  & %



日本データベース学会論文誌

  
!!" 年  月      論文
数に相当する時間でこれらの変数のチェックを行うことができる．
実際の検索時間は，これに圧縮された  の複雑さに関連する係数が掛かるが，それは原テキストに対して十分小さく，その解析については本論の中で説明する．結論として，本手法により，全体をテキスト長にほぼ無関係な時間で行うことができる．本研
究ではこの処理を高速に実行するための索引構造を提案し，アルゴリズムによって置換された各変数がどの程度のパターンを復号
しているかを予備的な実験によって測定することで本研究の有効性を確かめる．

5
4
3

3

2
1

2
1

1

3

2
1

4

઒ᗐ⊛䈭䉝䊦䊐䉜䊔䉾䊃ᧁ

1

2
1

1

3

2
1

1

2
1

1

2
1

1

2
1

1

1

a1 a2 a3 a4 a5 a6 a7 a8 a9 a10 a11 a12 a13 a14 a15 a16 a17 a18 a19 a20 a21 a22 a23 a24 a25 a26 a27 a28 a29 a30 a31 a32

landmarks䉝䊦䊐䉜䊔䉾䊃ㆶర䈮䉋䉎
landmark䈱⸘▚ 圧縮アルゴリズム

w = a1 a2 a3 a5 a9 a17 a16 a8 a4 a2 a1 a4 a8 a16 a17 . . .
w
1st 䊤䊔䊦
w = 31 22 43 65 89 10 111 98 74 52 31 44 68 8161017. . .

この節では，提案手法の基礎となる圧縮アルゴリズムについて述べる．このアルゴリズムはアルファベット還元  と呼ばれる文字の変換規則に基づいている．

2nd 䊤䊔䊦
w = 41 52 43 65 49 8 41 58 94 52 71 24 68 416 817 . . .

final 䊤䊔䊦w = 71 62 73 65 79 6 71 68 84 92 41 74 68 716 617 . . .

 アルファベット還元*'    

 アルファベット還元|в| ҅ 32
҅ 10
҅ 8
҅ 6

図

テキストに最初から含まれる文字をアルファベットと呼び，それらの集合を  で表す．それらの文字とは別に，アルゴリズムが置換のために生成する文字は変数と呼んで区別する．今，アルファ
ベットと変数を含む文字の集合に対して，それらの文字すべてを同様にアルファベット還元を行うことで，整数列に含まれる整数
葉として持つ完全平衡  分木を考え，それをアルファベット木との種類を十分に小さくできる．この還元の様子を図  に示す．整呼ぶ．図 にサイズの場合のアルファベット木を示す．置換数列に含まれる整数の種類が十分小さく  以下に なるまでこのによる新しい変数が生まれるたびにアルファベット木の葉が増え還元を繰り返したとき，左右の値よりも大きい整数値を取る文字ていくが，ここでは簡単のため，あらかじめ十分に大きなサイズを  !"# と呼ぶ．の木を固定しておくことにする．また，葉に割り当てる変数の順
以降では，テキストの圧縮法を説明する．この圧縮法では，与番は任意でよい．
えられた文字列を 種類の部分文字列に分解し，    のよ
この木によって，任意の文字の組     に対して，   をうに同じ文字が連続しない部分については，前述のアルファベッ
文字  と  のアルファベット木における最近共通祖先の高さとして定める．例えば図 によると，    に対しては，    ト還元を適用して圧縮し，     のように同じ文字が連続する部である．以下，簡単のために，文字  と整数  を同一視する．こ 分については，左端から  文字ずつをある変数に置き換えていく．
れを用いて，  に対するアルファベット還元   を以下の圧縮アルゴリズムの概略
ように定義する．ここで，  はテキスト  の 番目の文字を図  に圧縮アルゴリズムの概略を示し，各 $%& でどのよう表し，    は  の  番目の文字から  番目の文字までの部分文
な処理を行うかを説明する．
字列を表す．
$%&  与えられたテキスト  を         の形に        であるときは，        に対して           または        分解する．ここで各  は，同じ文字が連続する  の形かそれ以外の不連続形で分解される極大な部分文字列である．例えば   と定め，  であるときは，       に対して
         または            のときの分解は    となる．
$%&  の形の分解に対して，出現するすべての ' "!長  と定める．
この定義は，   の場合，すなわち同じ文字が連続する場 さ  の部分文字列 を一文字で置換して，   の生成規則を合については未定義であるが，ここではまだそのような一般の文 作る．ただし， が奇数の場合は，最後の一文字はそのまま残さ
字列は考えなくてよい．この関数    によって，文字の集合 れる．したがって， は      または      のいずれか      から構成される同じ文字が連続しない文字列が，その に変換される．
$%& 不連続形の部分文字列を圧縮する．まず文字列中の部分集合         から構成される元の文字列と同じ長さの整数列に還元される．このとき，還元後の文字列 整数列  !"# を計算し，その左隣の文字とで構成される ' "! を適も同じ文字が決して連続しないことが容易にわかる．したがって， 当な変数によって置換する．ただし，その  !"# が最左文字
この操作は再帰的に実行可能である．この変換をアルファベット ならばこの操作はスキップする．すべての  !"# が置き換えられると，次に，それ以外の置き換えられなかった ' "! を左還元と呼ぶ．
この還元によって変換された整数列を新たな文字列と見なして 側優先で適当な変数で置換していく．ここで適当な変数とは，現在置換しようとしている ' "! の置換すべき変数がすでに辞書に登録されていれば，常にそれに従うということを意味する．
4
$%& これまでに別々に置き換えた文字列を連結してひとつ3
lca(a2,a4)の文字列にして，
$%& からの処理を，文字列がそれ以上圧縮で= lca(a4,a2) = 2
きなくなるまで繰り返す．
1
このアルゴリズムによって文字列が実際にどのように圧縮されているかを図 に示す．この図で示されている文字列は， 
a1 a2 a3 a4 a5 a6 a7 a8 a9 a10 a11
((



()(


  で定義されるフィボナッチ文字列で  චಽ䈮ᄙ䈇䉻䊚䊷䊉䊷䊄あり，圧縮アルゴリズムのベンチマークとして利用されている．例え
図
アルファベット木ば，   の場合のフィボナッチ文字列は   ())))))))(となる．図  に示されている構文木の内部頂点が各 ' "! を置換した変数を表している．この例から，同じ部分文字列がなるべ)*' )  

日本データベース学会論文誌

  
!!" 年  月      論文౉ജᢥሼ೉ w

Phase 112ㅪ⛯ᢥሼㇱಽ䈱ಽഀ

w1

...

w2

wm
10

ㅪ⛯ᢥሼ䈱࿶❗

Phase 2... A X㱍B Y

㱎C Z ...

X’

㱍

Y’

㱎

Z’

...

X’

...

Y’

㱍’

Z’

㱎’

landmarks䈱⸘▚䈫ਇㅪ⛯ㇱಽ䈱࿶❗

7

1

b

...
...

269
267

260

264

259

b

a

261
260

257

b

a

a

260

257

b

a

259

a

b

265
260

257

a

b

a

a

b

260
257

259

a

b

a

a

257

b

a

a

図 + フィボナッチ文字列 ,部分- の圧縮結果*' +        

く同じ変数で置換されている様子がわかる．
文献  で示されているように，あるテキスト  に現れる部分
文字列の異なる出現           に対して，    と   のランドマークの位置は  の部分は完全に一致し，   £  である．ランドマークが一致している部分は完全に同じ£変数への置き換えが行われ， を十分に大きくしてもと見なしてよい．このことは，圧縮アルゴリズムの毎ループごとに成り立つので，ある有理数     が存在して，    と   の構文木における最大共通部分木の大きさは，少なくとも    以上であると保証できる．次の節では，このアルゴリズ
ムによって構築された  を利用した，パターン検索のための圧縮データ索引を提案する．

  による圧縮データ索引

本節では，  圧縮を用いた圧縮データ索引と検索手法について述べる．この基本アイディアは，テキスト  の圧縮辞書によってパターン  を同様に圧縮し，その変数列を  の圧縮データの中に順序を保って埋め込めるか否かによって， の出現を決定することにある．
前節の圧縮アルゴリズムで構築した  ! について以下の性質が成り立つ．ここで，    は文字列  における   から   までの部分文字列を表す    ．



b

b

b

b2 b

1

a

b

a

b

b

. 構文木と /0

b

1

b

a

a2
b

b

)       £ とする．このとき，    が同じ変数に置き換えられる．

*'        

261

b

61

     となる十分に長い部分文字列  が存在して， 圧縮アルゴリズムの概略

264

1

7

*' .      
定理

図

b

11

2

6

2

図

typical compression
rules

ㄉᦠ䈱಴ജ

Phase 4

2

a

11

6

6

Phase 31012

この定理は， に含まれる隣り合う  !"# は常に  文字以
内に接近していることおよび   が  !"# であるか否かはその左側の高々 £   文字以内の文字だけで決定されることか
ら容易に導かれる．
£
定理 で  の長さは十分に長いと説明しているが，これはを定数と見なすと，  *   であることを意味している．したがって， が変数  に置き換えられているとき，    の出現を， の ! における出現によって絞り込むことができる．以下，
      の接頭辞 および接尾辞  が  に隣接して現れるかを調べればよい．この   が十分に短い文字列であれば，それを展開して検索すればよく，そうでないならば，それらの文字列に対して定理 を繰り返して用いることで，以下の処理に還元できる．
テキスト  とパターン  に対して       であることと以下は等価である．すなわちある変数の列          が存在して，         であり， の ! による構文木   において          が隣接して出現する．ここで， は を展開して得られるアルファベット文字列であり，  が  の構文木 において隣接するとは， の最後の文字と   の最初の文字が  において隣接することを表す．
定理 より，各  は十分長い文字列を符号化しているので，任意の  に対して，    となる．したがって，! から直接        の隣接出現が判定できれば，テキスト中のパターン
 の出現を    に近い時間で検出できる．
以下では，この隣接出現の検索のアイディアを図によって説明する．図  はあるテキストの構文木とその +, 表現である．テ
キスト中に出現するパターン  を囲みによって表している．この は圧縮の特性により， の出現によらず十分長い文字列を符号化した変数  を必ず含む．ここで，残りの接尾辞  を符号化した変数  がすぐ隣に出現すれば  が出現したことがわかる．
この問題は，任意の変数   を根とする部分木が構文木内で隣接するか否かを解く問題に帰着できる．まず， の最右先祖を以下のように定義する．構文木は  分木であるので，すべての枝は左右の順序を持ち，それぞれに属する枝を左辺および右辺と呼ぶ．ここで， の先祖で左辺をちょうど一回たどって到達できるノードのうち  に最も近いノードを  の最右先祖と呼ぶ．直感
的には，最右先祖とは自分の右側にある最も近い先祖である．
この最右先祖の概念を用いて，ノードの隣接関係を以下のように簡潔に表すことができる．

日本データベース学会論文誌

  
!!" 年  月      

論文
12

X

12

10

X’

11

10

11

11

10

Y
6

7

2

A
B

b

図

1 部分木の隣接関係

b

b



- " は  の最右先祖
- # から左辺だけをたどって  に到達可能

6

2

a

virtual sink

b

6

7

1

b

b

2

a

b

1

b

b

0

0

Gleft

Gright

図2/0 の分解*' 2         定理  を根とする部分木が，構文木内でこの順番に隣接することと以下を満たすある変数 " とその右の子供 # が存在する
ことは等価である．

7

1

0

*' 1

12

a

のとき，テキストの前処理にかかる時間および領域はそれぞれ， £  および % £  である．ここで % は，圧縮
アルゴリズムが生成した  に含まれる異なる変数の個数であり，$ はその  を +, で表現したときの最大次数である．

この定理における二つのパラメータ % $ は，テキストサイズ
この関係を一般的に表したものが図  である．  が隣接す に対して十分に小さいと考えてよい．実際， の圧縮が容易であるためには図のような矢印で表された経路が存在すればよい．構 れば圧縮の最適解である % は十分に小さく，また  がランダムに
文木中の任意のノードに対して，その最右先祖は唯一であるので， 近く圧縮ができない場合には，ほとんど置き換えが起こらないた
それを前処理して覚えておくことで，構文木が与えられた場合の めやはり % は小さい．また $ は  の構文木中のある変数の出現回数と考えられるが，これはパターンが長くなるにつれて急激  の隣接関係の判定は定数時間で可能である．
しかしながら，本研究で目指す圧縮索引では，構文木は実際に に小さくなる．以上のことから，本研究で提案するデータ構造はは図  中の右側に描かれている +, のように，いくつかのノー テキストに前処理を施さない照合アルゴリズムよりも高速で，部ドが縮約されているため，ある変数  の最右先祖は唯一ではない． 分文字列に対する索引を構築する従来の手法よりも省スペースで+, 構造においても隣接関係を簡単に判定するために，得られ あると予想できる．次節ではこの見積もりを予備的な実験によった +, を二つに分解することを考える．まず，+, ! に唯一の て検証する．
シンクを付け加えたものを作り，この ! を二つの部分グラフに分割する．一方は，! の各ノードの左辺のみからなる ! であり，
実験
他方は，右辺のみからなる !
である．圧縮アルゴリズムは常本研究の実験は，&.'/! +/  "& 0 -12，3に ' "! を文字に置き換えるので，! の任意のノードはちょう
メモリ上の 4' 5% 6'%. において行った．
ど二つの子を持つ．したがって，! は必ず唯一の !  !
に
図  は，前々節で定義されたフィボナッチ文字列の圧縮率を 2'7
分割される．この分解の様子を図  に示す．と比較した結果である．横軸のパラメータは定義の漸化式の反復+, 上でも図  のような隣接関係を判定するために，まず，+, における変数  の最右先祖 " のひとつが確定したと仮定 回数を表しており，この値が大きくなるにつれてデータサイズは指数的に増加することがわかる．
する．!  !
は一番下のノードが根であることに注意する
本研究で採用したアルファベット還元法による  圧縮は，ほと，構文木における " の右の子供 # は !
における " の親ぼ最適な圧縮であるのに対して， 2'7 では一定以上の入力サイズであり，構文木において # から  へ左辺のみをたどって到達可以降は圧縮率が急激に悪化していることがわかる．これは， 2'7
能であることと ! において  が # の先祖であることは等価
が高速に実行できるように，履歴情報を格納する領域サイズをあである．木構造の先祖子孫関係は定数時間で計算可能ß であるの
らかじめ固定しているためである．この領域を入力の数倍程度確で，結局この問題は，+, 上で  の最右先祖 " をどのように見保すれば  圧縮と同等の圧縮率を達成できる可能性があるが，つけるかという問題に帰着できる．
それでも 2'7 等の従来の圧縮法は，前節で示した  圧縮が持構文木において， からその最右先祖 " に到達する直前にはつ構造を保存する特性がないため，索引として利用するためには必ず左辺をたどっており，それ以外ではすべて右辺をたどっていデータを展開したり補助情報の追加が必要である．したがって，こるので，このようなノード " 全体は，!
における  の子孫の意味でも本研究の手法が優れている．
¼¼
を " とすると ! において " の子供すべてと同じである．こ次に，前節で示したパターン検索の時間を見積もるための予備のような処理は木構造を一度だけ巡回すれば計算可能である．同的実験結果を示す．テキスト  を圧縮した結果を +, ! とす様に最左先祖も定義され，ノード  の左の隣接関係も定数時間でる．パターン  がテキスト  に出現することは， を  の辞書判定可能となる．以上により，本提案手法に対して以下の定理をで圧縮したときに決定される極大な変数列         が !得る．に隣接関係の順序を保って埋め込み可能であることと等価である．
二つの変数のグラフ内における隣接関係は定数時間で判定可能で定理
テキスト     にパターン      が出現あるので，パターン検索の時間は の大きさと各  の出現回数£
するか否かを， $ 時間で判定可能である．こ に依存する．
ß 木構造の定数時間判定アルゴリズムについては  などが詳しい．
まず のサイズを見積もる．図  のアルゴリズムのループ 回

!



#

日本データベース学会論文誌

  
!!" 年  月      論文

ᐔဋዷ㐿㐳㩿㪙㫐㫋㪼㪀

あたりの処理では，  !"# のズレはパターン  の左右の定数㪩㪼㫌㫋㪼㫉㫊
䊐䉞䊗䊅䉾䉼ᢥሼ೉高々 文字 以内に収まる．このことから， に  が出現するな㪈㪇㪇㪇㪇㪇㪇㪇
らば，! はある変数  を含み  は  のように圧縮され，
は  の少なくとも  以上の部分文字列を符号化している．ここ㪈㪇㪇㪇㪇㪇㪇
で， は   とは無関係の十分小さい自然数である．この  は具㪈㪇㪇㪇㪇㪇
体的に見積もることができるが，本論文では詳細は省略する．
このように   に対して定まる最長の文字列を符号化してい㪈㪇㪇㪇㪇
る変数  をパターン  のコアと呼ぶ．同様に，        は㪈㪇㪇㪇 の接頭辞・接尾辞に対して定まるコアの列である．有理数 
は入力とは無関係の定数であるので，    である．
㪈㪇㪇
次に の実測値がパターン長の対数に近いことを圧縮の実験結㪈㪇果によって示す．前述のように，アルゴリズムによる  !"#
㪈のズレは，パターンの定数長の接尾辞・接頭辞に限られる．した㪈㪊㪌㪎㪐 㪈㪈 㪈㪊 㪈㪌 ᷓ䈘㪈㪎がって，圧縮の構文木における任意の変数が，その高さの指数に比例した文字列を符号化しているならば，コアが符号化している 
図
コアの平均展開長
文字列が十分に長く結果として    であるといえる．
以上のことを，圧縮の実験結果から得られた構文木を解析する
ことで裏付ける．図 8 は，各コアが符号化している部分文字列長とそのコアの構文木中の高さの関係を示したものである．実験は，フィボナッチ文字列と自然言語テキスト ロイターニュース記事
に対して行った．テキストのアルファベットサイズに違いがある
ためそれぞれのデータで傾きが異なるが，いずれの場合もほぼ直線と見なせる．これは，構文木中の高さ & における変数 コア が，
平均  の長さの部分文字列を符号化していることを意味する．
ここで， はテキスト中のアルファベットに依存する定数である．
この結果から，実用的にも    であることが実験によって裏付けられた．
最後に，提案手法による検索性能を他手法と比較した結果を示す．ただし，現時点では前節の定理  によってパターンの出現を
コアの隣接関係のみで判定するアルゴリズムを実装できていない．
そこで本実験では，パターンのコアをひとつ確定してその周辺部分を展開して 9: オートマトンで照合することによってパターンの出現を確定している．図  がその結果である．実験に使用したデータは，  で公開されているイネゲノムの塩基配列を繋図
検索時間の比較
げた約 :3 のテキストである．このテキストからランダムに切り出した，長さ 〜 の比較的長い部分文字列をパターンに指定し，パターンの出現を判定するために掛かった時間を測定した．比較対象は，短いパターンに対しては最高速の圧縮文字列照合である 9: 3;< 法 8 とパターンが長くなると平均して高速になる 3:1 法  である．3:1 法に符号化を組み込ん 時間が徐々に増加しており，パターン長が 93 を超えるあたりだ手法
 も存在するが，今回の実験のようにパターンが十分に で 3:1 法に逆転されていることがわかる．これは，本来は必要のない余分な展開と照合を繰り返すことによるオーバーヘッドが長い場合には 3:1 法と差がなくなるため今回は割愛する．
図  のデータから，パターン長が 93 以降で提案手法の検索 大きくなりすぎるためである．実際，それらの時間がほとんど掛からない短いパターンに対しては他手法よりも高速であることがわかる．したがって，変数の隣接関係のみでパターンを検知する
改良を加えることで，より広範囲な優位性を期待できる．

*'     !    " #  )*' )     㪈㪇㪇㪇㪇㪇

" おわりに䉰䉟䉵䋨㪢㪙䋩

㪈㪇㪇㪇㪇
㪈㪇㪇㪇
㪈㪇㪇

ర䊁䉨䉴䊃
ర䊁䉨䉴䊃
࿶❗ᓟ䋨㪚㪝㪞䋩
࿶❗ᓟ䋨㪾㫑㫀㫇䋩

gzip

㪈㪇
㪈

CFG

㪇㪅㪈
㪈 㪋 㪎 㪈㪇 㪈㪊 㪈㪍 㪈㪐 㪉㪉 㪉㪌 㪉㪏 㪊㪈 㪊㪋 㪊㪎 㪋㪇㫅

図  圧縮率の比較 ,対 '3*'          $

本研究では，データをあらかじめ圧縮することで検索を効率的に行う枠組みに対して一手法を提案した．圧縮に基づく手法は，
4&) データのように複雑な編集が頻繁に行われるデータに対しては不向きであるが，特許データや遺伝子データのようにほぼ追加や削除のみが行われる静的なデータに対しては類似部分の発見等の応用が見込まれる．
また，パターンが数キロバイト程度の長いものになると，コアが符号化する部分文字列もそれに比例して長くなるため，パターンの出現とそのコア 個の出現がほぼ一致する．なぜならば，十分に長いパターンが  回以上出現する可能性は極めて低く，同様にそのコアも十分な長さを持っているからである．このコアの長さは，前節の実験データによるとパターン長の約  ％になっている．したがって，本手法はある 4&) ページや特許 件分の文書

日本データベース学会論文誌

  
!!" 年  月      論文など比較的長いパターンの検索に対して高速であり，この性能はテキストサイズに対して頑健である．
提案手法では，テキスト  にパターン  が出現するか否かを判定する問題に対して， $  時間で計算可能な圧縮デー
タ索引を示した．現在，理論的に最も効率がよい圧縮索引は，文献  で提案されている = に基づく圧縮索引である．= とは，本研究と同様に '  "# の形に制限された規則のみからなる  のある部分クラスである．この圧縮データとパトリシ
アトライなどのデータ構造を組み合わせることで，この手法では   (& % 時間で検索を行うことが可能としている．こ
こで，( はパターン  の出現回数，& は = の構文木の高さを表す．仮に (  とした場合，検索時間は   &%  となるが，  でも述べられているように，テキストサイズが巨大になると% の影響が大きくなり実用的な手法でなくなる．実際，このアルゴリズムは実装されていない．一方，本研究で提案した手法の検索時間は，パターンが存在するか否かの単純なものに限るが，
 £ $
 時間で実行可能である．このうち最も影響が大きい項は $ であるが，この値はパターン長の増加と共に急激に小さくなるので，本研究はパターンが十分に長い問題に対しては他手法と比較して優位性があると考えられる．またこの見積もり
は，実際にアルゴリズムを実装して圧縮文字列照合法と比較する
ことによっても裏付けることができた．また，$ は  の出現回数と関連するパラメータであるが，コアの平均展開長の測定実験から， がある程度の長さを持つ場合には $ は  と比較して十分小さいと考えてよい．したがって，検索のためにデータ全体を走査しないため，従来の圧縮パターン照合による手法よりも高速に検索可能であり，また，本手法は圧縮データそのものが索引となっているため，接尾辞木や接尾辞配列等の従来の索引構造と比較して要求される記憶領域が小さい．これらのことは，ベンチマーク
等の予備実験からある程度確認できたが，今後は完全なパターン検索を実装し，他の検索手法との性能比較を行うことで，本研究の優位性を示したい．

［謝辞］

本研究は，>=? 戦略的創造研究推進事業 さきがけ および >=?
地域イノベーション創出総合支援事業 シーズ発掘試験 の支援を受けた．また，適切なコメントを頂いた皆様に感謝します．

［文献］

%

 :- $"'#" ;- &$! +- '/ @- ' "$A :- ")
$#" ,- @%  ,- =$'  ,- =$& .- ?$& %! &%. "!!" 7" ) &!-         B  - / &  - C"" - =& D' &E& ?&E. !7"&%%' 0%' =."' $.'& " "!%-       - "! &  =- :/.$/#"'%$- ?$& =."' ; '. +'%.F& :.F$' " ) &! 4'.$ : C&%-         +- /%G& -          !  !7/.&" =F'&F& !7/..'  3' A- !
)"' & 0'C&"%'.A "&%% 88 ?$& H.&".'  @'F& & !& =&I/&F' " J&F.
H@=    
 >- - 9'&K&"  ;-1- L - "!!"3%&&%B &5 %% D 0'C&"%  %% &%% = /"F&&%- 
     BM  ->- "%%   ,- : K.- NO'& +'F.' "A3%&!7"&%%' -        B  - ;- &$!  ,- =$& .- ,77" E'!.'  , "'.$!%
D " "!!"3%& !7"&%%' -        "  #      8 =- :"/A! L- ?# 1- =#! .  :- ?#& .&E.=&%'.'C& "!!" ?"%D "!B !7"&%%'  ..&" :.F$' -            . 77&" - &C' :'  H- 4'..&- !7"&%%'   ;E7 .'  0%' 1'&""F$'F "!!"%-  "!  $ !
PB M  88 >- @/.'  >- ?'&  >- ?"$' - =."' :.F$' 5'.$ =. 77&" ;F ' & =7 '..' -   M  4- @A..&"- ,77 'F.'  D &!7& 'C DF. "'2.'  .
.$& 77" E'!.'  D "!!")%& F !7"&%%' -  "!   B   1- =#! .  =- :"/A! ?- 9'   =- =$'! 
2  - , =7F&=C' ,77" E'!.'  , "'.$! D ""!!"3%&!7"&%%' -    6 -;8+ -77-   8 1- =#! . - , / A '&"?'!& ,77" E'!.'  , "'.$! D " "!!"3%&!7"&%%' - $ #    B   ?-,- 4& F$- , ?&F$'I/& D " 1' $ &"D "!F& +.
!7"&%%' -   "! B 8 8 ;-1- L   >- - 9'&K&"- ;ÆF'&. 0'C&"%  %%
&%% +. !7"&%%'  , "'.$!% 3%&   "&& A=&I/&.' "!!" ?"%D "!M". N&B 5'.$ /. .&E. : & %-        B
 >- 'C  ,- &!7& - , 0'C&"% , "'.$! D " =&
I/&.' +. !7"&%%' -       
H?B8 8 >- 'C  ,- &!7& - !7"&%%'  D H 'C' / =&I/&F&% C' 6"') &@.&' -      B 8多比良 嘉成#$  % 年  月 九州工業大学情報工学部知能情報工学科卒業．現在，
同大学情報工学府情報科学専攻に在学中．データ圧縮の理論を応用した高速情報検索の研究に従事．

岸上 直也& # ' (8 年  月 九州工業大学情報工学部知能情報工学科卒業．現在，
同大学情報工学府情報科学専攻に在学中．データ圧縮の理論に関する研究に従事．

田中 洋平)  & # 年  月 九州工業大学情報工学部知能情報工学科卒業．8
年  月 同大学大学院情報工学府情報科学専攻修士課程修了．在学
中は，データ圧縮とその応用に関する研究に従事．現在，凸版印
刷株式会社 西日本事業本部勤務．

坂本 比呂志'

# *++

九州工業大学大学院情報工学研究院准教授および科学技術振興機
構さきがけ「知の創生と情報社会」研究者 兼任． 88 年九州大学大学院システム情報科学研究科情報理学専攻博士後期課程修了
日本学術振興会特別研究員．博士 理学． 888 年から  年
 月まで九州大学大学院システム情報科学研究科助手．機械学習，
半構造データからの知識獲得および半構造データに対する索引付けに関する研究に従事． 年度人工知能学会論文賞などを受賞．
電子情報通信学会，人工知能学会，日本データベース学会各会員．

日本データベース学会論文誌

  
!!" 年  月