講演抄録/キーワード |
講演名 |
2011-10-21 15:50
メモリの圧縮 Wing-Kin Sung(シンガポール国立大)・○定兼邦彦(NII)・Jesper Jansson(お茶の水女子大) COMP2011-34 |
抄録 |
(和) |
本論文では圧縮ランダムアクセスメモリのための動的データ構造を提案する.
メモリ (文字列) $T[1..n]$ は $\log\sigma$ ビットの文字 $T[i]$ から構成されるが,これを
$n H_k(T) + \Order\left(n \log \sigma \left(\epsilon + \frac{k\log \sigma +\log \log n}{\log n}\right)\right)$
ビットに圧縮して格納する.なお,$H_k(T)$ は $T$ の $k$-次の経験的エントロピーで,
$\epsilon > 0$ は任意の定数である.このデータ構造は
部分文字列 $T[i..i+\log_{\sigma} n - 1]$ (計算機の1語に相当) の読み込みを
$\Order(1)$ 時間,
書き換えを $\Order(1/\epsilon)$ 時間で実現する.
また,このデータ構造は $\log_{\sigma} n$ 文字の挿入削除を
$\Order(\log n/\log\log n)$ 時間で実現できるが,この場合は読み書き時間も
$\Order(\log n/\log\log n)$ となる.これは下限と一致する. |
(英) |
This paper proposes a new dynamic data-structure
for \emph{compressed random access memory}.
A memory (or string) $T[1..n]$, where each character $T[i]$ consists of $\log\sigma$ bits,
can be stored in
$n H_k(T) + \Order\left(n \log \sigma \left(\epsilon + \frac{k\log \sigma +\log \log n}{\log n}\right)\right)$
bits, where $H_k(T)$ is the $k$-th order empirical entropy of $T$
and $\epsilon > 0$ is any fixed constant,
such that
(1)~accessing $T[i..i+\log_{\sigma} n - 1]$ (one machine word)
takes
$\Order(1)$ time
and (2)~replacing $T[i..i+\log_{\sigma} n - 1]$ by another string of length $\log_{\sigma} n$
takes $\Order(1/\epsilon)$ time.
We can also support insertion and deletion of $\log_{\sigma} n$ characters
in $\Order(\log n/\log\log n)$ time at the cost of increasing the access
time to $\Order(\log n/\log\log n)$ time, which matches a known lower bound. |
キーワード |
(和) |
圧縮 / ランダムアクセスメモリ / 動的データ構造 / / / / / |
(英) |
compression / random access memory / dynamic data structure / / / / / |
文献情報 |
信学技報, vol. 111, no. 256, COMP2011-34, pp. 39-46, 2011年10月. |
資料番号 |
COMP2011-34 |
発行日 |
2011-10-14 (COMP) |
ISSN |
Print edition: ISSN 0913-5685 Online edition: ISSN 2432-6380 |
著作権に ついて |
技術研究報告に掲載された論文の著作権は電子情報通信学会に帰属します.(許諾番号:10GA0019/12GB0052/13GB0056/17GB0034/18GB0034) |
PDFダウンロード |
COMP2011-34 |