COMPRESSION OF INDIVIDUAL SEQUENCES VIA VARIABLE-RATE CODING
COMPRESSION OF INDIVIDUAL SEQUENCES VIA VARIABLE-RATE CODING
复制标题
DOI：
10.1109/tit.1978.1055934
复制
发表时间：
1978-01-01
影响因子：
2.5
通讯作者：
LEMPEL, A
中科院分区：
文献类型：
--
作者：
ZIV, J;LEMPEL, A
研究了一类广义有限状态信息无损编码器对单个序列的可压缩性。这些编码器可以在可变速率模式下工作，也可以在固定速率模式下工作，并且它们允许任何可变长度到可变长度编码的有限状态方案。对于每一个单独的无限序列，定义了一个量，称为的可压缩性，它被证明是任何有限状态编码器可以达到的压缩比的渐近可达的下界。这是通过构造编码定理及其逆定理证明的，除了它们的渐近意义外，还为有限和实际的数据压缩任务提供了有用的性能标准。所提出的可压缩性概念也被证明发挥了类似于经典信息理论中的熵的作用，在经典信息理论中，人们处理序列的概率集成而不是单个序列。的定义允许对每个不同的序列使用不同的机器进行压缩，而构造编码定理导致了一个对所有序列都是渐近最优的通用算法。
Compressibility of individual sequences by the class of generalized finite-state information-lossless encoders is investigated. These encoders can operate in a variable-rate mode as well as a fixed-rate one, and they allow for any finite-state scheme of variable-length-to-variable-length coding. For every individual infinite sequencea quantityis defined, called the compressibility of, which is shown to be the asymptotically attainable lower bound on the compression ratio that can be achieved forby any finite-state encoder. This is demonstrated by means of a constructive coding theorem and its converse that, apart from their asymptotic significance, also provide useful performance criteria for finite and practical data-compression tasks. The proposed concept of compressibility is also shown to play a role analogous to that of entropy in classical information theory where one deals with probabilistic ensembles of sequences rather than with individual sequences. While the definition ofallows a different machine for each different sequence to be compressed, the constructive coding theorem leads to a universal algorithm that is asymptotically optimal for all sequences.