圧縮データ構造の更なる圧縮
スポンサーリンク
概要
- 論文の詳細を見る
省スペース(succinct)データ構造は, データを情報理論的下限近くまで圧縮しつつ, 高速な問合せが可能なデータ構造である.これまでに集合, 辞書, 木, グラフ, 文字列, 区間和などに対する省スペースデータ構造が提案されているが, 本論文ではこれら全てに適応可能な汎用的圧縮法を提案する.あるデータが, アルファベットA上の長さnの文字列Sで表されているとする.つまりサイズはn log |A|ビットである.高速な問合せを実現するためのデータ構造としてf(n)=o(n log |A|)ビットのものを用いているとする.本論文で提案する手法を用いると, このデータ構造をnH_k+O(f(n)+n(log |A|+log log n+k)/log_|A|n)ビットに圧縮でき(H_kはSのk次経験的エントロピーで, H_k≦log|A|), Sの任意の連続するO(log n)ビットを定数時間で復元できる.k+log |A|=o(log n)の場合, 従来のn log |A|+o(n log |A|)ビットのデータ構造をnH_k+o(n log |A|)ビットに圧縮でき, かつ問合せの計算量は漸近的には同じである.
- 社団法人電子情報通信学会の論文
- 2005-10-11
著者
関連論文
- 量子アルゴリズムによる近似文字列出現頻度問い合わせ
- メトロポリスウォークの到達時間及び全訪問時間に関するタイトな上界
- グラフ上の線形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.超簡潔データ構造(特定領域研究「新世代の計算限界-その解明と打破-」)
- 括弧列の簡単・簡潔な表現法
- 大規模データ処理のための簡潔データ構造
- 最小重み負荷分散枝被覆について