抄録

RD-001
LCP配列を用いた類似文字列検索のための可変長N-gram抽出手法の効率化

可変長N-gramを索引語に用いる類似文字列検索の既存研究では、索引語の抽出および索引語辞書の保持を多分木により実現しているため、索引構築時の時間計算量および空間計算量が大きく，またパラメータチューニングのたびに木構造を作り直さなければならないという問題がある．
そこで、本研究では、多分木と同等の情報を持つLCP配列を用いて、パラメータチューニングに柔軟に対応できる，可変長N-gramによる索引をO(n)で構築する手法を提案する。