6

你们中有人知道产生无头输出的无损压缩算法吗？例如不存储用于压缩的霍夫曼树吗？我不谈论硬编码的霍夫曼树，但我想知道是否有任何算法可以压缩和解压缩输入而不在其输出中存储一些元数据。或者这在理论上是不可能的？

4

5 回答 5

5

当然这是可能的。其中，LZ 系列压缩器不需要输出压缩数据本身以外的任何内容，因为字典是在压缩（或解压缩）过程中在线构建的。对于那些 LZ 类型的算法，您有很多参考实现。例如，LZMA， 7zip 的组件。

于 2009-02-18T16:04:15.760 回答
4

运行长度编码就是一个例子

于 2009-02-18T15:58:38.817 回答
4

自适应霍夫曼编码正是这样做的。更一般地，术语自适应编码用于描述具有此属性的熵码。一些字典代码也具有此属性，例如游程编码 (RLE)和Lempel-Ziv-Welch (LZW)。

于 2009-02-26T03:12:20.293 回答
1

我想到了lzo 。在OpenVPN中使用，效果很好

于 2009-02-18T16:43:36.850 回答
0

为什么要寻找具有无头压缩输出的压缩算法？

也许（a）您有一个需要低延迟流压缩/解压缩的系统，例如 2 路电话。Zach Scrivena 提到的自适应编码类压缩算法和 Diego Sevilla 和 Javier 提到的 LZ 系列字典压缩算法非常适合这类应用。这些算法的实际实现通常在开始时确实有一两个字节的元数据（使它们对 (b) 应用程序无用），但这对延迟几乎没有影响。

也许（b）您主要对密码学感兴趣，并且您听说 compress-before-encrypt 提供了一些改进的安全属性，只要压缩文本没有固定的元数据标头“crib”。现代加密算法（据我们所知）不易受到此类“婴儿床”的影响，但如果您偏执，您可能会对“双射压缩”（a，b，c等）感兴趣。当接收器获得这样的压缩输出时，不可能检测到传输中的错误（翻转位、插入位、删除位等）（使得这些算法对 (a) 应用程序不是特别有用）。

也许（c）您出于其他原因对无头压缩感兴趣。听起来很吸引人——那是什么原因？

于 2012-09-01T14:31:13.513 回答