著者

伊東 秀夫

出版者

一般社団法人情報処理学会

雑誌

情報処理学会論文誌データベース(TOD) (ISSN:18827799)

巻号頁・発行日

vol.41, no.1, pp.31-39, 2000-02-15

被引用文献数

3

---

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 algorithm which is known as the fastest one.