今日さまざまな文書が電子化され,データベース化されている.例えば新聞記事,辞書,書籍,遺伝子配列などがある.また,インターネットの発達によりホームページや電子メールなどの大量の文書が存在する.そしてこれらの大量の文書からの高速な検索,またそれらの文書の保存や転送のコスト削減のための圧縮が重要になってきている.

　本論文では大量の文書データからの検索およびその文書の圧縮の効率化のための統一的な手法を提案する.本論文で扱う検索・圧縮方法は全て接尾辞配列というデータ構造と関連がある.接尾辞配列は検索のためのデータ構造であり,これはブロックソート法というテキストの圧縮法の中でも用いられている.これらは共に有望な検索法・圧縮法であり,さまざまな研究が行われている.

　大量の文書からの検索には現在は転置ファイルと呼ばれるデータ構造が広く使われているが,ディスク容量を節約するために文書単位の検索しか行えない場合が多く,文単位などの詳細な検索は行われていない.また,検索の索引は単語単位に作られているため,日本語のように単語の区切りが分かりにくい場合には検索に漏れが生じる場合がある.さらに,遺伝子配列のように単語に分かれない文字列を扱うことができない.

　本論文では転置ファイルよりも詳細な検索を行える接尾辞配列を用いる.接尾辞配列は転置ファイルよりもサイズが大きいが,大容量のディスクが利用可能な現在ではサイズは問題にはならない.しかし接尾辞配列の構成については,今までのアルゴリズムでは非常に時間がかかるため大きなサイズの文書を扱うことができない.

　本論文でははじめに文字列の接尾辞をソートする省メモリで高速なアルゴリズムを提案する.これにより,非常に長い文字列に対する接尾辞配列の作成時間およびブロックソート法での圧縮時間を短縮することができる.時間計算量は最悪でもO(n log n)であり,また平均の比較回数は整数のquick sortの場合よりもO(n log log n)増えるだけである.実験によりこのアルゴリズムはロバストで,多くの場合に他のいくつかのソートアルゴリズムよりも高速であることがわかった.この高速なアルゴリズムにより,ブロックソート法で一度に多くの文書が圧縮できるようになり,圧縮率も向上できる.また,このアルゴリズムはブロックソート圧縮法の高速化だけではなく,gzipの圧縮アルゴリズムに用いることができ,圧縮に用いる辞書のサイズが大きいときの圧縮速度を改善できる.

　ブロックソート法は圧縮速度,圧縮率,メモリ効率などで優れているが,本研究ではもう1つの特徴として,ブロックソート法で圧縮された文書から接尾辞配列を線形時間で生成できることを発見した.そして,この性質を利用した文書の圧縮と索引の構成を統一した検索システムを提案する.この考えを用いれば,CD-ROMなどに保存された大量の圧縮文書から,その中から検索するための索引を高速に構成することができる.また,この圧縮法はWeb検索エンジンで用いる文書の収集に適している.ロボット型の検索エンジンではWeb文書をロボットと呼ばれるプログラムが収集し,索引を作成するが,文書の収集速度を上げるために分散Webロボットが提案されている,これは,ロボットをネットワーク的に離れた場所にある複数のサーバで動かし,各サーバの近くにある文書を収集し,それらをまとめて圧縮して検索サーバに送ることで,細いネットワークでのボトルネックを解消するものである.この時の文書の圧縮にブロックソート法を用いれば,サーバで復元する際に文書とその接尾辞配列を復元できるため,サーバが索引を構成する負荷を減らすことができる.

　次に,圧縮文書からの接尾辞配列の生成アルゴリズムを拡張した,転置ファイルを圧縮するための単語ブロックソート圧縮法を提案する.転置ファイルは接尾辞配列とは異なり任意の文字列の検索が難しくなるが,接尾辞配列よりもサイズが小さく,検索速度も速いため,多くの検索システムで利用されている.単語ブロックソート法で圧縮されたファイルからは,文書自身とそこから検索するための索引の両方を復元できる.圧縮率はgzipよりも良く,復元速度は転置ファイルを一から構成するよりも速い.また,ブロックソート圧縮法で用いられるBW変換を,文書索引の圧縮に都合がいいように変更した修正BW変換を提案する.これにより,単語の大文字小文字を区別しないなどの検索に用いる索引を圧縮文書から生成することができる.

　接尾辞配列や転置ファイルからの単語の検索に関しては,文書が大量にあるため検索結果も大量になり,その中から必要なものを見つけることが困難になっているという問題が発生している.これは,検索時に指定した単語を全て含む文書でも,文書中の離れた位置にたまたま現れているときにはそのような文書はユーザの望む文書ではないことが多いということである.これを解決する一つの方法として,近接検索という方法がある.これは複数指定した単語が近くに現れている場所を検索するというものである.本論文ではこの近接検索を一般化したものを定義し,その高速なアルゴリズムを提案する.

　これらのアルゴリズムにより,文書の転送時間,索引の構成時間,検索精度などの検索システムのいくつかの問題が解決され,大量の文書からの精密な検索が可能となる.

　本論文は大量の文書データからの検索および文書の圧縮を効率化する問題が,接尾辞配列というデータ構造に深く関わっていることを見出し,接尾辞配列を構成する高速のアルゴリズムを設計・実装しそれを応用することにより,文書の転送時間,索引の構成時間,検索精度などの検索システムのいくつかの問題を解決し,大量の文書からの精密なかつ効率的な検索が可能となることを理論的解析と計算機実験により実証している.

　第一章では,文書の検索と圧縮について,関連研究を引きながら問題点を同定し,本論文での結果の位置付けをしている.第二章は,第三章以下の議論のための準備にあてられている.

　第三章では,本論文の中心となっている文字列の接尾辞配列を構成するアルゴリズムについて論じている.このアルゴリズムは,最悪時間計算量がO(n log n)であること,また平均の比較回数は文書データのエントロピーに依存するものであるが,整数のquick sortの場合よりもO(n log log n)増えるだけであることが証明されている.これは理論的に,これまで最も優れていると考えられていたBentley-Sedgewickなどのアルゴリズムに優るものである.また,実験により本論分のアルゴリズムは,多くの場合に他のいくつかのアルゴリズムよりも高速であることを実証している.特に,Web検索におけるhtmlファイルに対して接尾辞配列を構成する場合に,他のどのアルゴリズムよりもはるかに高速であり,最も実用的なアルゴリズムと言える.これにより,非常に長い文字列に対する接尾辞配列の作成時間を短縮することが可能となっている.

　第四章では,この接尾辞配列の高速な構成法により,LZ77をはじめとしたいくつかの圧縮アルゴリズムを統一的に改良することに成功している.第五章では,文書の圧縮にブロックソート法という圧縮法を適用することが考えられている.ブロックソート法は圧縮速度,圧縮率,メモリ効率などで優れており,第七章では,ブロックソート法で圧縮された文書から接尾辞配列を線形時間で生成できることが論じられている.この性質を利用すれば,サーバで圧縮文書を復元する際に文書とその接尾辞配列を復元できるため,サーバが索引を構成する負荷を減らすことができる.さらに第五章では,圧縮文書からの接尾辞配列の生成アルゴリズムを拡張した,転置ファイルを圧縮するための単語ブロックソート圧縮法が考案されている.転置ファイルは接尾辞配列とは異なり任意の文字列の検索が難しくなるが,接尾辞配列よりもサイズが小さく,検索速度も速いため,多くの検索システムで利用されている.本論文では単語ブロックソート法で圧縮されたファイルから,文書自身とそこから検索するための索引の両方を復元できることが示されている.圧縮率はgzipよりも良く,復元速度は転置ファイルを一から構成するよりも速いことが示されている.また,ブロックソート圧縮法で用いられるBW変換を,文書索引の圧縮に適するように改良した修正BW変換が考案されている.これにより,単語の大文字小文字を区別しないなどの検索に用いる索引を圧縮文書から生成することが可能となっている.

　第六章は,接尾辞配列の構成法を近接検索へ応用したものである.接尾辞配列や転置ファイルからの単語の検索に関しては,文書が大量にあるため検索結果も大量になり,その中から必要なものを見つけることが困難になっているという問題がある.これは,検索時に指定した単語を全て含む文書でも,文書中の離れた位置にたまたま現れているときにはそのような文書はユーザの望む文書ではないことが多いということであるが,これを解決する一つの方法として,複数指定した単語が近くに現れている場所を検索するという考えがある.本論文では,この近接検索を一般化したものを定義し,その近接検索のための高速なアルゴリズムを構築している.これは,本論文の接尾辞配列の構成アルゴリズムがhtmlファイルのような反復文字列の多い文書に対して極めて高速であることから,Webの検索に非常に強力な検索エンジンと考えられる.

　なお,本論文の第五章〜七章は,今井浩氏との共同研究であるが,論文提出者が主体となって分析及び検証を行ってもので,論文提出者の寄与が十分であると判断する.

　したがって,博士(理学)の学位を授与できると認める.