メモリの圧縮

スポンサーリンク

概要

• 論文の詳細を見る

• 本論文では圧縮ランダムアクセスメモリのための動的データ構造を提案する.メモリ(文字列)T[1..n]はlogσビットの文字T[i]から構成されるが,これを[numerical formula]ビットに圧縮して格納するなお,H_k(T)はTのκ-次の経験的エントロピーで,∈>0は任意の定数である.このデータ構造は部分文字列T{i..i+log_σ n-1](計算機の1語に相当)の読み込みをO(1)時間,書き換えをO(1/ε)時間で実現する.また,このデータ構造はlog_σ n文字の挿入削除をO (log n/log log n)時間で実現できるが,この場合は読み書き時間もO (log n/log log n)となる.これは下限と一致する.

• 2011-10-14

著者

• 定兼 邦彦

  国立情報学研究所

• Jesper Jansson

  お茶の水大学

• Jansson Jesper

  九州大学大学院システム情報科学研究院

• Jansson J

  九州大学大学院システム情報科学研究院

• Sung W‐k

  School Of Computing National University Of Singapore

• SUNG Wing-Kin

  国立シンガポール大

• JANSSON Jesper

  お茶の水女子大

関連論文

• 全二分木の簡潔な表現 (アルゴリズムと計算機科学の数理的基盤とその応用)
• 高速復元可能な接尾辞配列圧縮法(FIT推薦論文)(情報・システム基礎)
• メトロポリスウォークの到達時間及び全訪問時間に関するタイトな上界
• 連続確率分布枝重み付きDAGに対する最長路長さ分布の計算 (理論計算機科学の深化と応用)
• Metropolis Walkのcover timeにおけるタイトな上界 (理論計算機科学の深化と応用)
• 2点連結な直並列グラフ上の高速なランダムウォーク (理論計算機科学の深化と応用)
• DS-1-8 Computing the Exact Distribution Function of the Longest Path Length in Directed Acyclic Graphs with Exponentially Distributed Edge Lengths
• RA-003 A Counting-Based Approximation the Distribution Function of the Longest Path Length in Directed Acyclic Graphs
• グラフ上の線形Cover Timeランダムウォーク実現の必要条件
• 辺上を移動するロボット1台による最適な多角形探索 (理論計算機科学の深化 : 新たな計算世界観を求めて)
• 確率的な枝重みをもつ有向非巡回グラフにおける最長路長さの分布関数の解析的な計算に関する考察 (理論計算機科学の深化 : 新たな計算世界観を求めて)
• 3点系統樹を入力とした系統樹構築の近似アルゴリズムの近似比とその解析 (理論計算機科学の深化 : 新たな計算世界観を求めて)
• 局所的な次数情報を用いた無向グラフの探索 (理論計算機科学の深化 : 新たな計算世界観を求めて)
• グラフ上の線形Cover Timeランダムウォーク実現の必要条件 (理論計算機科学の深化 : 新たな計算世界観を求めて)
• 重み付きグラフ上の枝被覆に対する次数均等化と重み最小化 (理論計算機科学の深化 : 新たな計算世界観を求めて)
• 局所探索法による熱力学的DNA配列設計の改良 (理論計算機科学の深化 : 新たな計算世界観を求めて)
• DS-1-10 Approximating Distribution of Optimization Problems with Normally Distributed Edge Weights by Approximate Counting
• 負荷分散枝被覆問題に対する最適性とアルゴリズム
• 全二分木の簡潔な表現
• 高頻度なフレーズの検索が高速な索引
• グラフの最小出次数最大化問題
• 正規分布に従う枝重みをもつグラフにおける最小全域木コストの分布関数の近似手法
• 確率的枝重みを持つグラフ上での最小全域木コストの近似見積り法に関する考察(計算機科学の理論とその応用)
• A-023 接尾辞木に対する二分木化と簡潔データ構造による圧縮(A分野:モデル・アルゴリズム・プログラミング,一般論文)
• A-022 圧縮された接尾辞配列を用いた近似文字列照合(A分野:モデル・アルゴリズム・プログラミング,一般論文)
• RA-007 高速復元可能な接尾辞配列圧縮法(モデル・アルゴリズム・プログラミング,査読付き論文)
• Patrascu, M., Succincter (より簡潔な), Proc. 49th IEEE Symposium on Foundations of Computer Science (FOCS), pp.305-313, 2008
• k-集合合意問題を解く故障検知器
• $k$-Set Agreement を解く故障検知器(計算機科学の理論とその応用)
• センサーネットワークにおける省電力高信頼なデータ伝送(計算機科学の理論とその応用)
• 局所探索法に基づくDNA 配列設計手法(計算機科学の理論とその応用)
• 部分文字列の高速復元に適した圧縮データ構造に関する研究(計算機科学の理論とその応用)
• 最大重み付き出次数を最小化するグラフ有向化問題の近似(不)可能性
• ボトムアップ手法を用いた系統樹構築の近似アルゴリズム(計算機科学の理論とその応用)
• 文法圧縮に基づいた圧縮データの自己索引構造化の提案 (計算機科学とアルゴリズムの数理的基礎とその応用)
• 大規模分散フレームワーク Hadoop を用いた接尾辞配列構築 (計算機科学とアルゴリズムの数理的基礎とその応用)
• Online and Dynamic Detection of Squares in Strings
• 局所情報を用いたランダムウォークの拡張
• DNA配列に適した圧縮全文索引
• ラベル付けされたグラフ上におけるオンライン予測
• 境界上を移動可能なロボット2台による多角形探索(計算機科学の理論とその応用)
• 負荷分散枝被覆問題に対する最適性とアルゴリズム(計算機科学の理論とその応用)
• 局所情報を用いたランダムウォークの拡張
• 順序木の新しい表現法
• 動的簡潔順序木
• 4.超簡潔データ構造(特定領域研究「新世代の計算限界-その解明と打破-」)
• 括弧列の簡単・簡潔な表現法
• 大規模データ処理のための簡潔データ構造
• メモリの圧縮
• 次数上下界制約付きグラフ向き付けにおけるペナルティ最小化
• 木上の関数の簡単な並列計算アルゴリズム
• 次数上下界制約付きグラフ向き付けにおけるペナルティ最小化
• AGPUモデルでの並列ソートアルゴリズムの計算量について
• GPUのための並列計算モデル
• ゼロサプレス型二分決定グラフに基くコンパクトかつ高速な索引構造(一般)
• 木上の関数の簡単な並列計算アルゴリズム
• DS-1-13 AGPUモデルにおけるマルチスレッディングの効果(DS-1.COMP学生シンポジウム,シンポジウムセッション)

もっと見る 閉じる

スポンサーリンク