compression - 确定用于一系列字节的最佳压缩算法

Question

对于我的个人项目，我正在编写一个小类来压缩和解压缩一种相当晦涩的格式。我有完整的规范，但这不是问题所在。

首先，这种“格式”使用一组 6 种不同的压缩类型以及未压缩的字节数据 block 。格式是 RLE，RLE 的一个分支，其中数字递增每个字节(例如 3、4、5，...)、16 位 RLE、LZ-Copy、反向 LZ-copy 和 LZ-Copy Xor' d 和 255。它不是最干净的规范，但我也没有设计它。

我的压缩例程应该采用 1 到 65535 字节之间的任意数组，并(希望)尽可能地压缩它。我之前的尝试只是简单地计算出，从未压缩流中的任何索引开始，上面的哪种压缩技术将提供最好的压缩，然后压缩该方法将压缩到压缩字节数组的字节数，然后从新的“未压缩”索引，例如:

{0,0,0,1,2,3,4}

该算法首先会读到开头有三个零，然后输出规范使用的它们的 RLE 编码，然后从第四个元素开始，会读到递增的 RLE 将覆盖 '1,2 ,3,4' 足够好并在返回之前压缩它。

总结的问题是，在尝试找出要使用的最佳规范时，即使在小 (20-30) 字节数组上，例程也非常慢。任何人都可以提供有关我如何优化它的提示，或者我是否可以提供更多信息来提供帮助？

Answer 1

听起来您正在尝试做的是为文件的每个可能段(我们称您的可变长度 1-64K block 段)计算出大量压缩可能性。如果我错了请纠正我，但是你是否从以下选择中为第一段计算出最佳压缩(方法 0 未压缩):

• 压缩方式0，长度1字节。
• 压缩方式一，长度1字节。
• : : : : :
• 压缩方式6，长度1字节。
• 压缩方式0，长度2字节。
• 压缩方式一，长度2字节。
• : : : : :
• 压缩方式6，长度65534字节。
• 压缩方式0，长度65535字节。
• 压缩方式一，长度65535字节。
• 压缩方式2，长度65535字节。
• 压缩方式3，长度65535字节。
• 压缩方式4，长度65535字节。
• 压缩方式5，长度65535字节。
• 压缩方式6，长度65535字节。

这将花费大量时间(每段大约 420,000 次压缩尝试)。如果这就是你正在做的，你最好选择一个单一的段大小(例如 64K)并应用七种压缩方法中的每一种来选择最好的。然后，对于每个段，输出“方法”字节后跟压缩数据。