4

bzip2（即Julian Seward 的这个程序）列出了 100k 到 900k 之间的可用块大小：

 $ bzip2 --help
 bzip2, a block-sorting file compressor.  Version 1.0.6, 6-Sept-2010.

 usage: bzip2 [flags and input files in any order]

   -1 .. -9            set block size to 100k .. 900k

这个数字对应于hundred_k_blocksize写入压缩文件头的值。

从文档中，内存要求如下：

Compression:   400k + ( 8 x block size )

Decompression: 100k + ( 4 x block size ), or
               100k + ( 2.5 x block size )

在编写原始程序时（1996 年），我想 7.6M（400k + 8 * 900k）在计算机上可能是一个巨大的内存量，但对于今天的机器来说，它什么都不是。

我的问题分为两部分：

1) 使用更大的块大小会实现更好的压缩吗？（我天真地假设是的）。有什么理由不使用更大的块吗？压缩的 cpu 时间如何随着块的大小而变化？

2) 实际上，是否存在允许更大块大小的 bzip2 代码分支（或替代实现）？这是否需要对源代码进行重大修改？

文件格式似乎足够灵活来处理这个问题。例如...由于hundred_k_blocksize包含一个指示块大小的 8 位字符，因此可以向下扩展ASCII 表以指示更大的块大小（例如':'= x3A=> 1000k、';'= x3B=> 1100k、'<'= x3C=> 1200k、...） .

4

1 回答 1

5

Matt Mahoney 从他的大文本压缩基准中编译的程序支持您的直觉，即更大的块大小应该导致更高的压缩比。例如，开源 BWT 程序 BBB，( http://mattmahoney.net/dc/text.html#1640) 从块大小 10^6 到 10^9，压缩率提高了约 40%。在这两个值之间，压缩时间加倍。现在“xz”程序使用的是最初由 7zip 的作者 Igor Pavlov 描述的 LZ 变体（称为 LZMA2），它开始取代 bzip2 作为压缩源代码的默认策略，值得研究提高 bzip2 的可能性块大小，看看它是否可能是一个可行的选择。此外，由于专利限制，bzip2 避免了算术编码，专利限制已经过期。结合使用 Jarek Duda 开发的快速非对称数字系统进行熵编码的可能性，现代化的 bzip2 在压缩比和 xz 速度方面很可能具有竞争力。

于 2018-05-07T03:10:01.763 回答