書誌事項
- タイトル別名
-
- Suffix array ノ コウリツテキ ナ コウチクホウ
- An Efficient Method for Construction of Suffix Arrays
この論文をさがす
説明
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.
収録刊行物
-
- 情報処理学会論文誌データベース（TOD）
-
情報処理学会論文誌データベース（TOD） 41 (SIG01(TOD5)), 31-39, 2000-02-15
東京 : 情報処理学会
- Tweet
キーワード
詳細情報 詳細情報について
-
- CRID
- 1050001337891965696
-
- NII論文ID
- 110002725334
-
- NII書誌ID
- AA11464847
-
- ISSN
- 18827799
- 03875806
-
- NDL書誌ID
- 5700364
-
- 本文言語コード
- ja
-
- 資料種別
- article
-
- データソース種別
-
- IRDB
- NDL
- CiNii Articles