圧縮接尾辞配列構築アルゴリズムの改良
スポンサーリンク
概要
- 論文の詳細を見る
文字列検索のためのデータ構造としては接尾辞本,接尾辞配列などが有名であるが,これらにはデータ構造の必要とする記他領域が大きいという欠点がある.近年GrossiとVitterによって提案された圧縮接尾辞配列は検索速度を落とすことなく接尾辞配列を圧縮したものであり,サイズは長さnの文字列に対してO(nlog|A|)ビット(Aはアルファベット)である.これは文字列のサイズの線形となっている.圧鎔接尾辞配列を構築するアルゴリズムとして,Honらの提案したO(nlog|A|)ビットの一時的な記他領域を使用するO(nloglogUI)時間アルゴリズムが存在する,これは領域に関しては最適だが時間に関しては最適ではない,本論文ではアルファベットサイズが小さいとき(log|A| = O((log log n)^<1-ε>))に0(n)時間で動くアルゴリズムを提案する.
- 2004-05-13
著者
関連論文
- 量子アルゴリズムによる近似文字列出現頻度問い合わせ
- メトロポリスウォークの到達時間及び全訪問時間に関するタイトな上界
- グラフ上の線形Cover Timeランダムウォーク実現の必要条件
- 圧縮接尾辞配列構築アルゴリズムの改良
- 負荷分散枝被覆問題に対する最適性とアルゴリズム
- 局所情報を用いたスケールフリーネットワークの探索
- 簡潔データ構造による全文検索のハードウェアを用いた高速化(ハードウェアアクセラレーション,SWoPP佐賀2008-2008年並列/分散/協調処理に関する『佐賀』サマー・ワークショップ)
- ディスクレパンシー基準によるディジタルハーフトーニング : 自動評価手法と最適化手法
- 実数列の大域的丸めの数え上げ
- Computational Geometry on Statistical Manifolds for Clustering : Extended Abstract (Models of Computation and Algorithms)
- 正規分布に従う枝重みをもつグラフにおける最小全域木コストの分布関数の近似手法
- ヨーロッパ型及び貯蓄型アジアオプションの高精度かつ高速な価格計算
- 近傍探索の解合流性に基づく並列局所探索法の考察(計算理論とアルゴリズムの新展開)
- k-集合合意問題を解く故障検知器
- 隠れマルコフモデルを用いたDNA配列設計
- 負荷分散セミマッチングにおける最適性について
- DS-1-10 DNA構造変化の特徴解析(DS-1.COMP-NHC学生シンポジウム,シンポジウム)
- センサーネットワークにおける省電力高信頼なデータ伝送(計算機科学の理論とその応用)
- DNA計算における局所探索法による反応障壁近似計算
- DNA計算における局所探索法による反応障壁近似計算
- 局所情報を用いたランダムウォークの拡張
- DNA配列に適した圧縮全文索引
- 曲線のピーク削減アルゴリズムの考察と実装
- F-050 数値データベースに対するエキスパート付き決定木の構築(F.人工知能)
- センサーネットワークにおける省電力高信頼なデータ伝送(計算理論とアルゴリズムの新展開)
- 非同期分散システムにおける故障検知器と故障計数器について(計算理論とアルゴリズムの新展開)
- DNA 分子の濃度と反応速度の関係解析(計算理論とアルゴリズムの新展開)
- 文書データベースへの効率的な索引付けとその更新に関する研究
- 局所情報を用いたランダムウォークの拡張
- 順序木の新しい表現法
- 圧縮データ構造の更なる圧縮
- 量子計算での幾何学データ処理
- 動的簡潔順序木
- 4.超簡潔データ構造(特定領域研究「新世代の計算限界-その解明と打破-」)
- 括弧列の簡単・簡潔な表現法
- 大規模データ処理のための簡潔データ構造
- 省スペースな圧縮接尾辞配列構成アルゴリズム
- 最小重み負荷分散枝被覆について