Suffix arrayの効率的な構築法

スポンサーリンク

概要

論文の詳細を見る
Suffix arrayは文字索引の一種であり, suffix treeに比べ単純でコンパクトなデータ構造を用いて実装できる.文字列処理に対して多くの優れた性質を持つsuffix arrayだが, 特に大規模なテキストに対しては索引構築に多大な記憶量と計算コストを必要とし実用上の問題なっている.我々は, 高速かつコンパクトなsuffix array構築法を提案する.そのキーとなるアイデアは, 任意のsuffix間の関係ではなく, 隣接するsuffix間の関係のみを利用する点にある.このアルゴリズムを二段階ソート法と呼ぶ.514MBの毎日新聞記事を含む様々なデータセットを用いた評価実験により, 我々のアルゴリズムはQuicksortの約6倍高速であり, また, 今までで最も高速なアルゴリズムとして知られているSadakaneの方法に対し2〜3倍高速であることを示す.
一般社団法人情報処理学会の論文
2000-02-15

著者

関連論文

スポンサーリンク