Suffix Array 構成アルゴリズムの比較
-
- 定兼 邦彦
- 東京大学大学院理学系研究科情報科学専攻
書誌事項
- タイトル別名
-
- Comparison among Suffix Array Construction Algorithms
この論文をさがす
説明
文書データベースから一致文字列を検索するためのコンパクトなデータ構造としてsuffix arrayがある。これは文字列の全ての接尾辞のポインタを辞書順に格納した配列で、木構造よりも必要なメモリが小さいため大きなデータベースに対して有効である。またsuffix arrayの構成はブロックソート圧縮法でも必要である。このsuffix arrayを構成するいくつかのアルゴリズムについて必要メモリと速度を比較し、それらを組み合わせた省メモリで高速なアルゴリズムを提案する。このアルゴリズムは文字列中に繰り返しが多い場合に有効である。
Suffix array is a compact data structure for searching matched strings from text databases. It is an array of pointers and stores all suffixes of a text in lexicographic order. Because its memory requirement is less than tree structures, it is effective for large databases. Moreover, constructing the suffix array is used in the Block Sorting compression scheme. We compare algorithms for constructing suffix arrays on speed and required memory and propose a fast and memory efficient algorithm by combining them. It is effective when the length of repeated strings in a text is large.
収録刊行物
-
- 情報処理学会研究報告. AL, アルゴリズム研究会報告
-
情報処理学会研究報告. AL, アルゴリズム研究会報告 59 9-16, 1997-11-28
一般社団法人情報処理学会
- Tweet
詳細情報 詳細情報について
-
- CRID
- 1573950401931472256
-
- NII論文ID
- 110002812051
-
- NII書誌ID
- AN1009593X
-
- ISSN
- 09196072
-
- 本文言語コード
- en
-
- データソース種別
-
- CiNii Articles
