類似文字列検索におけるLCP配列を用いた索引の提案

情報処理学会

この論文をさがす

抄録

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

収録刊行物

キーワード

詳細情報 詳細情報について

問題の指摘

ページトップへ