抄録
Suffix arrayは文字索引の一種であり, suffix treeに比べ単純でコンパクトなデータ構造を用いて実装できる.文字列処理に対して多くの優れた性質を持つsuffix arrayだが, 特に大規模なテキストに対しては索引構築に多大な記憶量と計算コストを必要とし実用上の問題なっている.我々は, 高速かつコンパクトなsuffix array構築法を提案する.そのキーとなるアイデアは, 任意のsuffix間の関係ではなく, 隣接するsuffix間の関係のみを利用する点にある.このアルゴリズムを二段階ソート法と呼ぶ.514MBの毎日新聞記事を含む様々なデータセットを用いた評価実験により, 我々のアルゴリズムはQuicksortの約6倍高速であり, また, 今までで最も高速なアルゴリズムとして知られているSadakaneの方法に対し2〜3倍高速であることを示す.
The Suffix array is a string indexing structure and a memory efficient alternative of the suffix tree. It has myriad virtues on string processing. However, it requires large memory and computation to build suffix arrays for large texts. We propose an efficient algorithm for sorting suffixes. One of the key ideas is to use specific relationships between an adjacent suffix pair. We call this algorithm the Two-Stage Suffix Sort. Our experiments on several text data sets (including 514MB japanese newspapers) demonstrate that our algorithm is about 6 times faster than the popular sorting algorithm Quicksort, and 2 to 3 times faster than Sadakane's algorithms which is known as the fastest one.
