HTTP/2 协议-HPACK（HTTP2 头部压缩算法）原理介绍

HTTP/2 协议-HPACK（HTTP2 头部压缩算法）原理介绍

HTTP/1 协议是一个无状态的协议，这样就导致每次请求都会传输重复的大量 HTTP 头部，使得 HTTP/1 协议的效率非常低下，HTTP/2 使用 HPACK（HTTP头部压缩算法） 解决了这样效率低下的问题，这篇文章简单介绍一下 HPACK 算法原理。

1.HPACK 中的三种压缩方式

• 静态字典
• 动态字典
• 压缩算法：Huffman 编码（最高压缩比8:5）

1.1 静态字典

比如需要传递 GET 这样一个数据，只需要传递它的静态字典 index的值 2 就可以用来表达 GET 这样的含义，在 RFC7541 文档中对静态表的定义如下：

Tips：RFC7541 文档地址https://httpwg.org/specs/rfc7541.html#static.table.definition。

1.2 静态字典附录表

1.3 HEADER 压缩编码示意图

Tips：Huffman 是一种压缩算法。

1.4 h2load 工具介绍

动态表可以简单理解为在请求过程中映射的 索引表，比如第一个请求帧（frame） 使用 静态表+Huffman算法 构成的索引表（静态表+动态表）可以在下一次请求 帧（frame） 中只需要传递新增的内容使用 Huffman算法，不变的内容可以使用 索引表 中的值（和静态表类似）替代，下图使用 h2load 工具检验 静态表+动态表+Huffman 压缩空间图：

2.哈夫曼（Huffman）编码原理介绍

• 原理：出现概率较大的符号采用较短的编码，概率较小的符号采用较长的编码。
• 静态 Huffman 编码。
• 动态 Huffman 编码。
  

Tips: RFC7541文档关于’Huffman编码’描述地址：https://httpwg.org/specs/rfc7541.html#huffman.code

3.哈夫曼(Huffman)树的构造原理

• **（1）**计算各个字母出现的概率
• **（2）**将出现频率最小的两个字母相加构成子树，左小右大
• **（3）**重复步骤 2，直到完成树的构造
• **（4）**给树的左儿子编码为 0，右儿子编码为 1
• **（5）**每个字母的编码即从根节点至所在结点中所有链接的编码

3.1 哈夫曼(Huffman)树构造举例1

如 singwa 这六个字需要编码，各个字母出现概率如下图：

Tips：其中 frequency 表示出现的次数。

步骤1：将出现频率最小的字母 a（5） 和 w（6） 构成子树，它的父亲节点是它们的和，如下图所示：

步骤2：继续查找出现频率最小两个的字母 g 和 n，它的父亲节点是它们的和，如下图所示：

步骤3：继续找到出现频率最小的字母 i，将它与 步骤1 生成的子树合并：

步骤4：继续找到出现频率最小的字母 s，将它与 步骤2 生成的子树合并：

步骤5：将步骤3和步骤4生成的子树合并：

Tips：最后形成的树，按照 左儿子为 0，右儿子为 1标记，这样就可以对每个字符编码如 a 的编码为 000。

3.2 对字符编码

最终构造出的哈夫曼（Huffman）树对应的各个字符编码如下：

3.3 抓取报文简单分析

Tips：如图所示的二进制数据是根据 静态表+动态表+Huffman 得出的。

扫码关注爱因诗贤