Universal Lossless Data Compression Via Binary Decision Diagrams
Universal Lossless Data Compression Via Binary Decision Diagrams
复制标题
通过二元决策图进行通用无损数据压缩
DOI：
--
复制
发表时间：
2011
期刊：
影响因子：
--
通讯作者：
E. Yang
中科院分区：
文献类型：
--
作者：
J. Kieffer;P. Flajolet;E. Yang
一个长度为2^k的二进制字符串可以导出k个变量的布尔函数，其香农展开式就是给定的二进制字符串。这个布尔函数可以通过一个唯一的降序二元决策图（ROBDD）来表示。给定的二进制字符串可以从这个ROBDD中完全恢复。我们展示了一种无损数据压缩算法，其中长度为2的幂的二进制串通过如上所述压缩与其相关联的ROBDD来压缩。
我们表明，当二进制字符串的长度为$n $2的幂通过该算法压缩，最大逐点冗余/样本相对于任何s-状态的二进制信息源的上限$（4log_2s+16+o（1））/log_2n $。为了建立这个结果，我们利用Liaw和Lin的一个结果，即$k$变量的布尔函数的ROBDD表示包含数量级为$（2+o（1））2^{k}/k$的顶点。
A binary string of length $2^k$ induces the Boolean function of $k$ variables whose Shannon expansion is the given binary string. This Boolean function then is representable via a unique reduced ordered binary decision diagram (ROBDD). The given binary string is fully recoverable from this ROBDD. We exhibit a lossless data compression algorithm in which a binary string of length a power of two is compressed via compression of the ROBDD associated to it as described above.
We show that when binary strings of length $n$ a power of two are compressed via this algorithm, the maximal pointwise redundancy/sample with respect to any s-state binary information source has the upper bound $(4log_2s+16+o(1))/log_2n $. To establish this result, we exploit a result of Liaw and Lin stating that the ROBDD representation of a Boolean function of $k$ variables contains a number of vertices on the order of $(2+o(1))2^{k}/k$.