メモリの圧縮 Memory Compression

この論文をさがす

著者

抄録

本論文では圧縮ランダムアクセスメモリのための動的データ構造を提案する.メモリ(文字列)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)となる.これは下限と一致する.

This paper proposes a new dynamic data-structure for compressed random access memory. A memory (or string) T[1..n], where each character T[i] consists of logσ bits, can be stored in nH_k(T) + O [numerical formula] bits, where H_k(T) is the κ-th order empirical entropy of T and ∈ > 0 is any fixed constant, such that (1) accessing T[i..i + logσ n-1] (one machine word) takes O(1) time and (2) replacing T[i..i + logσ n-1] by another string of length logσ n takes O(1/∈) time. We can also support insertion and deletion of logσn characters in O (log n/ log log n) time at the cost of increasing the access time to O (log n/ log log n) time, which matches a known lower bound.

収録刊行物

  • 電子情報通信学会技術研究報告. COMP, コンピュテーション

    電子情報通信学会技術研究報告. COMP, コンピュテーション 111(256), 39-46, 2011-10-14

    一般社団法人電子情報通信学会

参考文献:  15件中 1-15件 を表示

各種コード

  • NII論文ID(NAID)
    110008900061
  • NII書誌ID(NCID)
    AN10013152
  • 本文言語コード
    JPN
  • 資料種別
    ART
  • ISSN
    0913-5685
  • NDL 記事登録ID
    023345509
  • NDL 請求記号
    Z16-940
  • データ提供元
    CJP書誌  NDL  NII-ELS 
ページトップへ