圧縮接尾辞配列を用いた文字列アルゴリズム
スポンサーリンク
概要
- 論文の詳細を見る
全文検索のための索引である接尾辞配列は, 他の全文検索索引と比較すると省スペースであるが, 転置ファイルのような単語索引と比較するとサイズが大きい.この問題を解決するために圧縮接尾辞配列が提案されたが, 検索にはテキスト自身も必要であるため, 索引サイズはテキストよりも小さくならない. 本稿では圧縮接尾辞配列を用いた検索アルゴリズムを, テキスト自身が不要になるように変更する.また, テキスト全体やその一部を圧縮接尾辞配列から復元するアルゴリズムを提案する.これにより, テキストの圧縮と高速な検索の両立が可能となる.
- 2000-09-21