1C-6
類似文字列検索におけるLCP配列を用いた索引の提案
○木村光樹（東大），高須淳宏，安達 淳（国立情報学研）
可変長N-gramを索引語に用いる類似文字列検索の既存研究では，
索引語の抽出および索引語辞書の保持を多分木により実現してい
るため，索引構築時の時間計算量および空間計算量が大きいとい
う問題がある．そこで，本研究では，多分木と同等の情報を持つ
LCP配列を用いて，可変長N-gramによる索引を構築する手法を提
案する．LCP配列とは，接尾辞配列上で隣接する接尾辞の最長一致
する接頭辞長を要素とする配列であり，また，構築はO(n)で可能で
あるため，索引構築の時間的，空間的コストを削減できる．