c++ - 大文件的霍夫曼树

Question

我一直在 Internet 上搜索，但找不到我需要的东西。

我必须使用霍夫曼编码来压缩大文件。我的想法是读取文件的前 1-2MB

(避免先读取整个文件来构建树，然后再读取一次以对其进行编码，避免 O(2n) )，

并构建霍夫曼树。如果缺少 256 个字母字节中的任何一个，我会自己添加它，以防它稍后出现在文件中(而不是在前 1-2 MB 中)。但是尝试使用这个来测试结果:

int * totalFr = new int[256];
unsigned char * symArr= new  unsigned char[256];

for (int i = 0; i < 256; i++)
{
    totalFr[i] = i;
    symArr[i] = unsigned char(i);
}

int size = sizeof(symArr) / sizeof(symArr[0]);
buildHuffmanTree(totalFr,symArr, size );
delete[] totalFr;
delete[] arrei;

其中 buildHuffmanTree 是一个函数，它构建哈夫曼树，让我意识到我可以获得的最佳字符代码是 7 位，例如 0000001。

这就是我的问题的来源 - 为完整的 256 个单词字母表构建霍夫曼树是否值得？还是对 1-2MB 这样的 block 使用自适应霍夫曼编码更好

Answer 1

除非数据在存在的字节方面存在极大偏差，否则您不能指望仅从霍夫曼编码中得到很多。我刚刚尝试了来自维基百科的 100 MB 英文文本文件。它将文件缩小到其原始大小的 63%，因此平均可能将 8 位缩小到 5 位。此外，这也是一次以大约 16 KB 的 block 为单位执行霍夫曼运算，以便代码适应每个 block 。

正常的 zlib 压缩也会查找匹配的字符串，将其压缩到原始大小的 35%。更高级的压缩器，例如 xz，它花费更多的时间和内存来寻找更难和更远的匹配字符串，并且比 Huffman 编码做得更好一点，将其压缩到原始大小的 26%。