最近在了解 gzip 时，发现 gzip 采用了哈夫曼编码，于是复习一下。

一、工作原理

现在互联网上的大部分是英文内容，而英文就 26 个字母，英文文章无非就是 26 个字母的排列组合，可以想象：字母的重复率相当高。

就算是中文网站，常用的汉字不到 3000 个，重复率依然很高。

如果我们把文本中的字母出现的频率统计一下，然后按出现频率从高到低重新编码，比如频率最高的为 0 第二的为 1， 原先占用 8 位的英文字母，只需要一位就可以表示了。

这样不就可以节约很大的空间，减少网络传输数据量吗！

哈夫曼就是这样工作的。

而且很明显可以发现：

字符重复的频率越高，霍夫曼编码的工作效率就越高！

所以它通常用于 GZIP、BZIP2、PKZIP 这些常规的压缩格式中，压缩重复率越高，压缩效果越明显。

二、哈夫曼树定义

example：

定义：

为了得到权重最小的树，我们可以总结出树的分布规律：

1. 权值越大的叶节点越靠近根节点
2. 权值越小的叶节点越远离根节点

三、构造哈夫曼树

用一个例子来表述构造哈夫曼树的过程

1. 给出 8 个结点的权值大小如下：

2. 从 19，21，2，3，6，7，10，32 中选择两个权小结点。选中 2，3。同时算出这两个结点的和 5。

3. 从 19，21，6，7，10，32，5 中选出两个权小结点。选中 5，6。同时计算出它们的和 11。

4. 从 19，21，7，10，32，11 中选出两个权小结点。选中 7，10。同时计算出它们的和 17。

5. 从 19，21，32，11，17 中选出两个权小结点。选中 11，17。同时计算出它们的和 28。

6. 从 19，21，32，28 中选出两个权小结点。选中 19，21。同时计算出它们的和 40。另起一颗二叉树。

7. 从 32，28， 40 中选出两个权小结点。选中 28，32。同时计算出它们的和 60。

8. 从 40， 60 中选出两个权小结点。选中 40，60。同时计算出它们的和 100。 好了，此时哈夫曼树已经构建好了。

四、根据哈夫曼树生成哈夫曼编码

1. 首先我们来处理这棵构造好的一棵哈夫曼树，将经过左边路径标为 0，经过右边路径标为 1。

2. 根据路径，确定每个字符的二进制编码

3. 根据每个字符的二进制编码，编码原字符串

五、编码压缩率

根据三中的例子

压缩前：22 个英文字母 ASCII 编码，需要 176 位来存储
压缩后：只需要 52 位来存储

粗略计算压缩率来到了 30%左右

但考虑到解码，需要把霍夫曼树的结构也传递过去，于是字符占用和频率占用的位也需要传递过去。

最后压缩率也在 50%以上

根据哈夫曼编码的原理来看： 字符重复率越高，压缩率越高

js 实现哈夫曼树

class huffmanTree {
  constructor(str) {
    // 第一步，统计字符出现频率
    let hash = {}
    for (let i = 0; i < str.length; i++) {
      hash[str[i]] = hash[str[i]] + 1
    }
    this.hash = hash

    // 构造哈夫曼树
    this.huffmanTree = this.getHuffmanTree()

    let map = this.getHuffmanCode(this.huffmanTree)
    // 查看对照表，即每个字符的二进制编码是什么
    console.log(map)

    // 最终的二进制编码
    this.binaryStr = this.getBinaryStr(map, str)
  }

  // 构造哈夫曼树
  getHuffmanTree() {
    // 以各个字符出现次数为node.val, 构造森林
    let forest = []
    for (let char in this.hash) {
      let node = new Node(this.hash[char], char)
      forest.push(node)
    }

    // 等到森林只剩一个节点时，表示合并过程结束，树就生成了
    let allNodes = [] // 存放被合并的节点，因为不能真的删除森林中任何一个节点，否则.left .right就找不到节点了
    while (forest.length !== 1) {
      // 从森林中找到两个最小的树，合并之
      forest.sort((a, b) => {
        return a.val - b.val
      })

      let node = new Node(forest[0].val + forest[1].val, '')
      allNodes.push(forest[0])
      allNodes.push(forest[1])
      node.left = allNodes[allNodes.length - 2] // 左子树放置词频低的
      node.right = allNodes[allNodes.length - 1] // 右子树放置词频高的

      // 删除最小的两棵树
      forest = forest.slice(2)
      // 新增的树加入
      forest.push(node)
    }

    // 生成的哈夫曼树
    return forest[0]
  }

  // 遍历哈夫曼树，返回一个 原始字符 和 二进制编码 的对照表
  getHuffmanCode(tree) {
    let hash = {} // 对照表
    let traversal = (node, curPath) => {
      if (!node.length && !node.right) return
      if (node.left && !node.left.left && !node.left.right) {
        hash[node.left.char] = curPath + '0'
      }
      if (node.right && !node.right.left && !node.right.right) {
        hash[node.right.char] = curPath + '1'
      }
      // 往左遍历，路径加0
      if (node.left) {
        traversal(node.left, curPath + '0')
      }
      // 往右遍历，路径加1
      if (node.right) {
        traversal(node.right, curPath + '1')
      }
    }
    traversal(tree, '')
    return hash
  }

  // 返回最终的压缩后的二进制串
  getBinaryStr(map, originStr) {
    let result = ''
    for (let i = 0; i < originStr.length; i++) {
      result += map[originStr[i]]
    }
    return result
  }
}