情報処理学会 第77回全国大会講演要旨

従来，全文検索に用いられる圧縮接尾辞配列は省スペースであるが，順序木の節点数に応じて検索時間が増大する．一方で，ダブル配列は節点間の遷移をO(1)で実現するデータ構造である．そのため，検索時間は検索キーの文字数にのみ依存する．だが圧縮接尾辞配列に比べて，記憶サイズは大きくなる．
従来のダブル配列は自然言語処理分野において利用される事例が多かったが，全文検索へ応用したダブル配列構造は発表されていない．そこで本論文では，DAWGを用いてダブル配列を構築し，全文検索を行う手法を提案する．また，大規模な英文やDNA配列におけるサイズおよび検索速度に関して，圧縮接尾辞配列や従来のダブル配列との比較を行う．