On locally decodable source coding
On locally decodable source coding
复制标题
关于本地可解码的源代码
DOI：
10.1109/icc.2015.7249014
复制
发表时间：
2013
期刊：
影响因子：
--
通讯作者：
Yury Polyanskiy
中科院分区：
文献类型：
--
作者：
A. Makhdoumi;Shao;M. Médard;Yury Polyanskiy
随着大数据的兴起，传统的信源编码技术面临着只能高效解码一小部分信息的共同障碍。在本文中，我们旨在通过引入一种称为局部可解码信源编码（LDSC）的特定类型的信源编码方案来解决这一难题。严格来说，LDSC能够从其编码版本中恢复未编码消息的任意一位，只需将少量编码消息提供给解码器即可，如果只需要t个编码符号，我们就称该解码器为t - 局部的。我们考虑了LDSC的几乎无损（块错误）和有损（位错误）两种情况。首先，我们表明使用线性编码器和具有有限局部性的解码器，可靠压缩率不能小于1。更重要的是，我们表明即使使用通用编码器和2 - 局部解码器（t = 2），LDSC的速率仍然是1。相反，对于具有超额失真的几乎无损和有损压缩的可实现界限表明，当解码器对块长度为n的编码符号查询O(log n)个时，可以实现最优压缩率。我们还表明，当查询数量随n缩放且在有限长度范围内对速率有界时，率失真也是可实现的。尽管可实现界限仅仅基于码块的连接，但它们在简洁数据结构文献中的现有界限上有所改进。
With the boom of big data, traditional source coding techniques face the common obstacle to decode only a small portion of information efficiently. In this paper, we aim to resolve this difficulty by introducing a specific type of source coding scheme called locally decodable source coding (LDSC). Rigorously, LDSC is capable of recovering an arbitrary bit of the unencoded message from its encoded version, by only feeding a small number of the encoded message to the decoder, and we call the decoder t-local if only t encoded symbols are required.We consider both almost lossless (block error) and lossy (bit error) cases for LDSC. First, we show that using linear encoder and a decoder with bounded locality, the reliable compress rate can not be less than one. More importantly, we show that even with a general encoder and 2-local decoders (t = 2), the rate of LDSC is still one. On the contrary, the achievability bounds for almost lossless and lossy compressions with excess distortion suggest that optimal compression rate is achievable when O(log n) encoded symbols is queried by the decoder with block-length n. We also show that, rate distortion is achievable when the number of queries is scaled over n with a bound on the rate in finite-length regime. Although the achievability bounds are simply based on the concatenation of code blocks, they outperform the existing bounds in succinct data structures literature.