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

我一直在搜索互联网，但找不到我需要的东西。

我必须使用霍夫曼编码来压缩大文件。我的想法是读取文件的前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之类的块使用自适应霍夫曼编码更好

最佳答案

除非数据对存在的字节有很大的偏见，否则不能仅凭霍夫曼编码就可以期待很多。我只是尝试了Wikipedia的100 MB英文文本文件。它使文件减小到其原始大小的63％，因此平均可能从8位减小到5位。同样，霍夫曼（Huffman）一次以大约16 KB的块进行，因此代码适用于每个块。

常规zlib压缩（还会查找匹配的字符串）会将其压缩到原始大小的35％。更高级的压缩器（例如xz）花费更多的时间和内存来查找字符串越来越费劲，并且比霍夫曼编码要好一些，从而将压缩率降低到原始大小的26％。

关于c++ - 大文件的霍夫曼树，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/41827511/