省スペースな圧縮接尾辞配列構成アルゴリズム
スポンサーリンク
概要
- 論文の詳細を見る
文字列検索のための索引として接尾辞配列が有名であるが, そのサイズが問題となっている.圧縮接尾辞配列はそれを圧縮したもので, 通常は元の文字列よりもサイズが小さくなる.ただし圧縮接尾辞配列を構成するアルゴリズムとしては一旦接尾辞配列を構成するものしか存在しないため, 一時的だが大量のメモリが必要となる.本研究では長さnの文字列に対し, O(n)ビットの一時記憶を用いるO(n|Σ|log n)時間(|Σ|はアルファベットサイズ)のアルゴリズムを提案する.このアルゴリズムは短い文字列に対する圧縮接尾辞配列から長い文字列に対するものを徐々に作成するものになっており, データの追加を容易に行える点も利点である.
- 一般社団法人情報処理学会の論文
- 2001-11-27
著者
関連論文
- 圧縮接尾辞配列構築アルゴリズムの改良
- 実数列の大域的丸めの数え上げ
- 量子計算での幾何学データ処理
- LD-2 サイト内検索システムのためのスコアリング手法(D. データベース)
- LA-4 柔軟な文書検索のためのコンパクトなデータ構造(A. アルゴリズム・基礎)
- 文書データを対象とした索引技術(マルチメディア時代のデータベース索引技術)
- 省スペースな圧縮接尾辞配列構成アルゴリズム