高速復元可能な接尾辞配列圧縮法

摘要

大規模文字列データに対する高速な文字列検索は接尾辞配列[8]（SA）を用いて実現できるが，SArnには多くの容量が必要になってしまう．SAを圧縮する様々な方法が提案されているが，本論文では出現頻度のrn高いフレーズの検索が既存の圧縮法に比べて高速な圧縮法を提案する．提案手法では，SAをブロックに分割し，rnそのブロック内でソートを行い，差分をとったものを保存し，検索時は差分からソート後のSAを取り戻し，区rn間内をすべて逐次的に検索する．これで検索フレーズのすべての出現位置を得ることができる．実験により，特rnに検索フレーズの頻度が高い場合，多くの入力データで提案手法の性能が既存の方法より優れていることを示す．