65.9K
CodeProject 正在变化。 阅读更多。
Home

快速简单的 Huffman 压缩器

Jan Mojzis
starIconstarIconstarIconstarIcon
emptyStarIcon
starIcon

4.80/5 (14投票s)

2010年8月29日

CPOL

5分钟阅读

viewsIcon

79545

downloadIcon

4852

快速简单的 Huffman 压缩器

引言

霍夫曼树压缩几乎和RLE压缩一样简单，但速度同样快，并且能提供更合理的压缩比，因此效率更高。本源代码和二进制文件是霍夫曼树压缩的一个例子。

背景 

霍夫曼树压缩和树的构建在维基百科上有详细的描述。霍夫曼树编码基于前缀。因此，不可能有两个不同的叶子具有完全相同的路径，更重要的是，必须有一条路径只以一个叶子结束（叶子之间不重叠）。此外，霍夫曼树编码基于每个特定符号出现的频率或概率。基于这个想法，我们使用一个优先队列，它最初填充了小的树，每棵树都有其符号/字符及其出现概率/ref.count。我们将队列/数组按降序排序，因此最频繁的符号位于顶部，而最不常见的符号位于底部。然后我们从最少的一个端开始，向上合并树，将两棵树合并成一棵新的树。每次合并后，都会进行排序，以便队列/数组再次按降序排列。我们进行合并、排序，直到队列中只剩下一棵树。然后，我们可以完成树的构建，然后进行压缩，其中每个符号都被其在树中的位路径替换。

Using the Code

代码包含一个名为simple_Huffman的public类，位于simple_huffman.cpp中。

主类

#include <memory.h>     // memset
#include <stdlib.h>     // qsort
typedef unsigned char BYTE;
class simple_Huffman{
private:
    class node{
    public:
        node *left, *right;
        int count;       // ref. count
        int code;        // code in bits
        int codelength;  // code length
        BYTE chr;        // ASCII char, serves in compression and then in writing of frequencies
        // constructor, memset is faster than individ.
        node(void)  {memset(this, 0, sizeof(node));}
        ~node() {
            if (left) {delete left; left = NULL;}
            if (right) {delete right; right = NULL;}
        }
    };
    // Array of trees, here will be only one tree at pos.
    // 0 when finished with merging 
    node *trees[256];
    node *leaves[256]; // array of leaves, each contains ASCII char,
         // ref. count, later code and codelength too. It is a reference to original trees
    node *trees_backup[256];
    // as the tree is constructed, this stores
    // exact steps (movings) of the last tree
    int STEPS[256];
    int stepscount;
    node nodes[256];

    void MakeTree();
    void MakeTreeD(); // maketree for decompression (no searching)
    int treescount;
    BYTE *allocatedoutput;
    // initialization of leaves with codes and code lengths
    void InitializeLeaves(node *, int, int);
    // sorting, we want to sort descending
    static int comparefreq(const void *A, const void *B);
    void moveTreesRight(node **toTree);
    void moveTreesRight2(node **toTree);
    void tryToPop();
    void moveToTop();
    void performInternalCleanup();
    void initialize();
    int LastError;
public:
    simple_Huffman();
    int Compress(BYTE *input, int inputlength);
    int Decompress(BYTE *input, int inputlength);
    int CompressFile(char *InFile, char *OutFile);
    int DecompressFile(char *InFile, char *OutFile);
    void Finalize(); // call after each stream compress/decompress to deallocate
    BYTE *getOutput(); // call after each stream compress/decompress to obtain output
    int getLastError(); // get code of last error (-1 input file failed
                        // to open, -2 output failed, -3 output allocation failed)
};

Using the Code

int Compress(BYTE *input, int inputlength);   // compress streams, return value is output size
int Decompress(BYTE *input, int inputlength); // decompress streams, return value is output size
int CompressFile(char *InFile, char *OutFile);  // compress file directly, return value is output size
int DecompressFile(char *InFile, char *OutFile); // decompress file directly return value is output size

关注点

霍夫曼压缩比RLE压缩的比例要好得多，并且总体上更有效。但是，它当然不会消耗模式或重复项。通常提供20%-50%的节省比例。

霍夫曼树编码被广泛使用，例如在deflate gzip、JPEG图像等中。

如果你想立即学习霍夫曼编码，请随时访问我们最好的捷克语网站，专门用于此主题。请在此处输入一些字母。然后单击“Cetnosti”计算符号。看到那些小树了吗？很好。现在单击“Vytvor strom”创建最终树，或者尝试“Jeden krok”进行单步树合并。

在输出树结构中存储路径信息

当将树存储在输出文件中时，确定int是否足够大以包含所有可能的路径，以及是否存在任何导致失败的坏情况，这将非常有趣。在编写霍夫曼表（输出树结构）时，我们基本上有几种选择。选择如下。

头部

在两趟霍夫曼实现（获取概率，然后执行压缩/解压缩）中，我们需要通知解码器用于压缩的树结构。该结构可以由一个表表示，简单地列出字符及其概率。基本上，你有几种选择来生成原始树。你可以：

  1. 发送整个树（路径长度、路径本身、符号）或
  2. 发送字符计数（计数、字符）或
  3. 发送原始流中存在的字符的排序序列，并发送一个“食谱”来重建树，或者
  4. 发送树的规范表示

详细信息

  1. 发送带有路径长度、路径本身和符号的树需要4+4+1 = 9个字节（4个字节长度，4个字节路径，1个字节字符）。当有256个可能的字符时，生成的头部将是256*9 = 2304字节。
  2. 发送字符计数需要4个字节用于计数和1个字节用于字符。总共是4+1 = 5个字节。256个字符将花费256 * 5 = 1280字节。
  3. 排序序列存在于当前实现（3.0）中，我们将在下面更详细地讨论。一个树生成算法从（树数组的）末尾开始，经过所有字符树（只有1个字符的树），并将最后两棵树合并成一棵新树。每次执行合并时，所有剩余的树都会重新排序，以反映树的实际变化，并假定最后两棵树具有最小的概率。合并需要两棵树并创建一个新树，该树有1个左节点和1个右节点（子树），它们都是那些最小概率树。它们的概率被加起来并包含在新创建的树中。现在我们需要假设树的顺序是正确的（从最可能到最后可能）。为此，我们可以简单地对整个树进行重新排序。这里的关键是，根本不需要重新排序。只需更深入地思考一下：重新排序会检查所有树，以确保它们已排序。但我们知道，只有一棵树实际发生了变化，需要进行检查。所以，我们只需检查这棵新树（从后往前）是否有一个更好的位置。如果找到了更好的位置，我们就称这种检查为步骤。我们存储每个步骤（整数值=新位置）。步骤列表可以命名为“食谱”，因为它告诉我们如何使用确切的步骤重建原始树。

我们的排序序列只是按概率（从最高到最低）排序的字符。这是初始数组，在执行任何步骤之前。

所以我们最多需要256字节用于字符和256字节用于步骤，总计512字节。与2相比，我们节省了768字节。另一个好处是，我们不再担心存储路径长度（4个字节足够？见）。

关于规范表示，你可以访问[1]。或者你可以看[2]，它似乎更容易阅读。

参考文献

[1] http://www.arturocampos.com/ac_canonical_huffman.html#Canonical%20Huffman

[2] http://www.compressconsult.com/huffman/

历史 

  • 2012年4月1日 - 添加了int CompressFile和int DecompressFile。现在压缩输出中包含的头部更短（之前最大值（字节）：1280，当前最大值：512）。压缩和解压缩现在速度稍快。此版本与任何先前版本都不兼容。
  • 完整的历史列表可以在huffman.cpp C++源文件的头部找到。
  • 2010年8月30日 - 第一次源代码修订，类被拆分到单独的头文件中，并且只公开了Compress和Decompress（以及构造函数）。
  • 2010年8月29日 - 添加了注释和类重命名。
© . All rights reserved.