著者

韓 永楷 定兼 邦彦 宋 永健

出版者

一般社団法人電子情報通信学会

雑誌

電子情報通信学会技術研究報告. COMP, コンピュテーション (ISSN:09135685)

巻号頁・発行日

vol.104, no.55, pp.1-7, 2004-05-13

---

文字列検索のためのデータ構造としては接尾辞本,接尾辞配列などが有名であるが,これらにはデータ構造の必要とする記他領域が大きいという欠点がある.近年GrossiとVitterによって提案された圧縮接尾辞配列は検索速度を落とすことなく接尾辞配列を圧縮したものであり,サイズは長さnの文字列に対してO(nlog|A|)ビット(Aはアルファベット)である.これは文字列のサイズの線形となっている.圧鎔接尾辞配列を構築するアルゴリズムとして,Honらの提案したO(nlog|A|)ビットの一時的な記他領域を使用するO(nloglogUI)時間アルゴリズムが存在する,これは領域に関しては最適だが時間に関しては最適ではない,本論文ではアルファベットサイズが小さいとき(log|A| = O((log log n)^<1-ε>))に0(n)時間で動くアルゴリズムを提案する.