Tag Archives: 压缩

Huffman编码压缩算法及其实现

哈弗曼编码是一个很经典的压缩算法,压缩率能达到50%,甚至更低。它的基本原理包括四个步骤:

  1. 统计文件中每个字符出现的频率。
  2. 构建一个哈弗曼树。建树的过程是不断的合并频率最小的两个节点,父亲节点的频率为两个孩子节点的频率之和。如此循环直到合并成一个根节点。叶子节点为不同的字符及其频率。
  3. 生成哈弗曼编码。从树根开始对树进行编码,比如进入左孩子的边标记为0,进入右孩子的边标记为1,这里的0和1都是二进制位。这样之后,每个叶子节点都有一个唯一的二进制编码,这就是哈弗曼编码。频率越低的字符哈弗曼编码越长,频率越高的字符哈弗曼编码越短,这样就能起到压缩的效果。
  4. 第二遍扫描文件,把字符转换为对应的哈弗曼编码,保存成压缩文件。

解压缩的过程就是解析二进制位,然后查找哈弗曼树,每找到一个叶子节点,就解析出一个字符,直到解析完所有二进制位。下面详细解释我的C++实现。 Continue reading