情報検索のためのコンパクトなデータ構造とその動的更新に関する研究

点击翻译按钮获取中文摘要

大量データ処理のための領域効率のよいアルゴリズムとデータ構造の開発を行った.まず,文字列の高速検索を行うデータ構造として,すでに圧縮接尾辞配列が提案されているが,それを構築する省メモリなアルゴリズムを開発した.このアルゴリズムは定数サイズアルファベット上の文字列に関しては時間・領域ともに最適であり,定数サイズではない場合にも従来手法より高速である.具体的には,アルファベットサイズをΣ,文字列長をnとしたとき,O(n log Σ)領域,O(n log n)時間である.また,このアルゴリズムよりも時間はかかるが,圧縮率の高い文字列についてはさらに省スペースなアルゴリズムも考案した.計算量は,O(n log n)時間である(HOは文字列の次数0のエントロピー).次に,複数の文字列の検索が可能なデータ構造を提案した.これは文字列の挿入・削除を高速に実行でき,検索も高速である.また,文字列だけでなく,一般の数列を表現するデータ構造についても考察した.このデータ構造は,数字の更新(増加),数列の和,検索を効率よく行え,必要な領域はほぼ最適である.さらに,圧縮接尾辞配列のデータ構造として二次記憶での実装や分散環境に適したものを提案した.これにより,より大量のデータに対する検索を高速に行えるようになった.