简介

Huffman 编码是一种可变字长编码的压缩算法，同时也是一种 无损编码 的方式。

整体来说一句话就可以描述 Huffman 算法：通过统计字符出现的概率，出现概率大的字符使用短编码，出现概率小的字符使用长编码，从而使平均码长最短。

编码流程

构建 Huffman tree

假设编码以下字符串 FFOOORRRRGGGGEEEEETTTTTTT

第一步 - 统计每个字符出现的次数

第二步 - 将出现概率最小的数字作为左子节点，次小的作为右子节点

第三步 - 递归上述流程

第四步 - 将左连接编码为0，右连接编码为1

第五步 - 得到每个数字的编码，即从根节点到叶子节点经过的路径

• F - 000
• O - 001
• E - 01
• T - 10
• R - 110
• G - 111

  google http2 中的实现

  https://github.com/golang/net/blob/master/http2/hpack/huffman.go#L49

  leetcode

  535. TinyURL 的加密与解密

  参考

  https://zhuanlan.zhihu.com/p/63362804
  https://github.com/golang/net/blob/master/http2/hpack/huffman.go#L49