文書データベースへの効率的な索引付けとその更新に関する研究  [in Japanese] Efficient Indexing and Updating of Text Databases  [in Japanese]

計算機の性能の向上や, インターネットの普及により, 我々が扱うデータの量は急速に増加している.そしてそれに伴い, 大きなデータの中から必要なデータを探し出す機会も多くなっている.しかし, 扱うデータの量が増えるにつれて検索に必要な時間計算量や空間計算量も増加するため, より効率の良い検索アルゴリズムが求められている.一般に, 文字列検索を行う際にはあらかじめ対象となるファイルに対して索引付けを行って検索しやすくしている.そこで, 本研究では複数のファイルを格納した文書データベースに対して, 圧縮接尾辞配列を用いた索引付けを行うことにより, 時間的にも空間的にも効率が良く, 検索漏れが生じない文字列検索アルゴリズムを提案する.

Because of the performance improvement of computers and popularization of the Internet, the amount of data is rapidly increasing. However, as the volume of data is increasing, the time and space complexities of searching and indexing them are increasing. Therefore, more efficient search algorithms are required. In general, we index target files in advance when we perform a string search so that we can search it quickly. In this study, we index the whole document database that stores multi-documents by compressed suffix array. We propose a text search algorithm which is efficient in both time and space.