大規模テキストに対する Suffix Arrayの効率的な構築法

スポンサーリンク

概要

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

著者

関連論文

スポンサーリンク