Minimum Expected Length of Fixed-to-Variable Lossless Compression Without Prefix Constraints
Minimum Expected Length of Fixed-to-Variable Lossless Compression Without Prefix Constraints
复制标题
无前缀约束的固定到可变无损压缩的最小预期长度
DOI：
10.1109/tit.2011.2145590
复制
发表时间：
2011
影响因子：
2.5
通讯作者：
S. Verdú
中科院分区：
文献类型：
--
作者：
W. Szpankowski;S. Verdú
具有熵H的n块无记忆源的固定到可变长度编码的最小预期长度增长为nH + O（1），其中项O（1）位于0和1之间。然而，这种众所周知的性能是在分配给整个n块的代码是前缀码的隐式约束下获得的。丢弃前缀约束，这是很少有必要在块级，我们表明，最小预期长度有限字母表无记忆源与已知的分布增长为nH-1/2 log n + O（1），除非源是等概率的。对于那些对数概率不位于格上的无记忆源，我们还将此结果优化到o（1）。
The minimum expected length for fixed-to-variable length encoding of an n-block memoryless source with entropy H grows as nH + O(1), where the term O(1) lies between 0 and 1. However, this well-known performance is obtained under the implicit constraint that the code assigned to the whole n-block is a prefix code. Dropping the prefix constraint, which is rarely necessary at the block level, we show that the minimum expected length for a finite-alphabet memoryless source with known distribution grows as nH-1/2 log n + O(1) unless the source is equiprobable. We also refine this result up to o(1) for those memoryless sources whose log probabilities do not reside on a lattice.