Suffix arrayの効率的な構築法

• Item type: Trans(1)
• 公開日: 2000-02-15
• タイトル: Suffix arrayの効率的な構築法
• タイトル / 言語: en
• タイトル: An Efficient Method for Construction of Suffix Arrays
• 言語: jpn
• キーワード / 主題Scheme: Other
• キーワード / 主題: 研究論文（論文賞受賞）
• 資源タイプ / 資源タイプ識別子: http://purl.org/coar/resource_type/c_6501
• 資源タイプ: journal article
• 著者所属: リコーソフトウエア研究所
• 著者所属(英): en
• 著者所属(英): Richo Software Rserch Center
• 著者名: 伊東, 秀夫
• 著者名(英): Itoh, Hideo
• 論文抄録 / 内容記述タイプ: Other
• 論文抄録 / 内容記述: Suffix arrayは文字列索引の一種であり，suffix treeに比べ単純でコンパクトなデータ構造を用いて実装できる．文字列処理に対して多くの優れた性質を持つsuffix arrayだが，特に大規模なテキストに対しては索引構築に多大な記憶量と計算コストを必要とし実用上の問題になっている．我々は，高速かつコンパクトなsuffix array構築法を提案する．そのキーとなるアイデアは，任意のsuffix間の関係ではなく，隣接するsuffix間の関係のみを利用する点にある．このアルゴリズムを二段階ソート法と呼ぶ．514MBの毎日新聞記事を含む様々なデータセットを用いた評価実験により，我々のアルゴリズムはQuicksortの約6倍拘束であり，また，今まで最も高速なアルゴリズムとして知られているSadakaneの方法に対し2?3倍高速であることを示す．
• 論文抄録(英) / 内容記述タイプ: Other
• 論文抄録(英) / 内容記述: 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.
• 書誌レコードID / 収録物識別子タイプ: NCID
• 書誌レコードID / 収録物識別子: AA11464847
• 書誌情報: 情報処理学会論文誌データベース（TOD）; 巻 41, 号 SIG01(TOD5), p. 31-39, 発行日 2000-02-15
• ISSN / 収録物識別子タイプ: ISSN
• ISSN / 収録物識別子: 1882-7799
• 出版者 / 言語: ja
• 出版者: 情報処理学会