LiteHub中间件之gzip算法

gzip算法

- 理论部分
- - LZ777算法
  - 霍夫曼编码算法
  - 改进型的LZ777算法
- 代码实现
- - 压缩对象
  - gzip实现
- 运行分析
- - 日志查看
  - wireshark抓包查看
  - 后台管理界面查看

理论部分

gzip是一种无损压缩算法，其基础为Deflate，Deflate是LZ77与哈弗曼编码的一个组合体。它的基本原理是：对于要压缩的文件，首先使用LZ77算法的一个变种进行压缩，对得到的结果再使用哈夫曼编码（根据情况，使用静态哈弗曼编码或动态哈夫曼编码）的方法进行压缩。

LZ777算法

几个术语

等待编码区
搜索缓冲区（已经编码的区域）
滑动窗口（指定大小，包括“搜索缓冲区”和“待编码区”）

具体的编码过程：
接下来，介绍具体的编码过程：
　　为了编码待编码区，编码器在滑动窗口的搜索缓冲区查找直到找到匹配的字符串。匹配字符串的开始字符串与待编码缓冲区的距离称为“偏移值”，匹配字符串的长度称为“匹配长度”。
　　编码器在编码时，会一直在搜索区中搜索，直到找到最大匹配字符串，并输出(o, l )，其中o是偏移值， l是匹配长度。然后窗口滑动l，继续开始编码。
　　如果没有找到匹配字符串，则输出(0, 0, c)，c为待编码区下一个等待编码的字符，窗口滑动“1”。

参考文章：LZ77压缩算法编码原理详解(结合图片和简单代码)

下面我们以字符串“abababc”为例，来了解其编码过程：

假设滑动窗口的大小足够大(LZ777设置的滑动窗口是32k)，可以覆盖整个字符串。

第一步：
待编码区：abababc
搜索缓冲区：（初始为空）
操作：搜索缓冲区为空，无法找到匹配字符串。
输出：(0, 0, a)（表示没有找到匹配，输出字符a）
窗口滑动：窗口向右滑动1个字符。
结果：a已经被编码，剩下bababc。
第二步：
待编码区：bababc
搜索缓冲区：a（已经编码的部分）
操作：在搜索缓冲区中查找b的匹配。搜索缓冲区中没有b。
输出：(0, 0, b)（表示没有找到匹配，输出字符b）
窗口滑动：窗口向右滑动1个字符。
结果：ab已经被编码，剩下ababc。
第三步：
待编码区：ababc
搜索缓冲区：ab（已经编码的部分）
操作：在搜索缓冲区中查找ab的匹配。搜索缓冲区中存在ab，匹配长度为2。
输出：(2, 2)（表示匹配长度为2，偏移值为2）
窗口滑动：窗口向右滑动2个字符。
结果：abab已经被编码，剩下abc。
第四步：
待编码区：abc
搜索缓冲区：abab（已经编码的部分）
操作：在搜索缓冲区中查找ab的匹配。搜索缓冲区中存在ab，匹配长度为2。
输出：(4, 2)（表示匹配长度为2，偏移值为4）
窗口滑动：窗口向右滑动2个字符。
结果：ababab已经被编码，剩下c。
第五步：
待编码区：c
搜索缓冲区：ababab（已经编码的部分）
操作：在搜索缓冲区中查找c的匹配。搜索缓冲区中没有c。
输出：(0, 0, c)（表示没有找到匹配，输出字符c）
窗口滑动：窗口向右滑动1个字符。
结果：整个字符串已经编码完成。

最终编码结果
经过上述步骤，字符串abababc的LZ77编码结果为：

(0, 0, a) (0, 0, b) (2, 2) (4,2) (0, 0, c)

使用LZ77压缩算法编码原理详解(结合图片和简单代码)给定的代码的编码结果是
在这里插入图片描述
说明上述编码过程分析正确！！！

上面的如(0, 0, a)这个其实根本不用写偏移和匹配长度，保留为原字符‘a’，占的编码长度还更短一些。

(0, 0, a) (0, 0, b) (2, 2) (4,2) (0, 0, c)

变为

ab(2, 2) (4,2)c

霍夫曼编码算法

霍夫曼编码是一种基于字符频率的变长编码方法，通过构建霍夫曼树来为每个字符分配一个唯一的二进制编码。霍夫曼树的构建过程依赖于字符的频率，频率越高的字符通常会被分配较短的编码。
首先我们统计"abababc"中每一个字符出现的频率，如下所示

a	b	c
3	3	1

根据霍夫曼编码的规则，我们需要按照字符频率从低到高构建霍夫曼树。以下是构建过程：

将字符串出现的频率视为优先级，放入一个最小优先队列中：

在这里插入图片描述

然后弹出两个优先级最低的字符作为子节点, 构造出第一个二叉树; 父节点的优先级视为两个字节优先级之和, 然后把父节点插入队列中:
重复这个操作, 最后我们会得到一颗二叉树. 这便是 Huffman编码树.

在这里插入图片描述
4. 我们把这棵树的左支编码为 0, 右支编码为 1, 那么从根节点向下遍历到叶子节点, 即可得出相应字符的 Huffman 编码. 因此我们得到上面例子的 Huffman 编码表为:

a:1
b:01
c:00

现在对字符串中出现的频率都做了一个统计，只需要解决偏移量和匹配长度的编码就可以了。

DEFLATE 算法对偏移距离和匹配长度已经做了一个统计，见下表：
偏移距离：
它有 0 至 29 一共 30 个编码. 距离编码的含义如下表所示:
在这里插入图片描述

code表示基本的编码表示，比如编码9对应的基准距离是25
extra表示距离基准距离偏移了多少，编码9对应的extra为3位，最大为111（7），即25+7，最大可以表示32。
distance，可以表示的距离范围
总结：code+extra可以灵活表示distance的任何数字

匹配长度：
对于长度, 它与普通字符共用同一编码空间. 这个编码空间一共有 286 个编码, 范围是从 0 至 285. 其中 0 至 255 为普通字符编码, 256 表示压缩块的结束; 而 257 至 285 则表示长度. 长度编码的含义如下表所示:
在这里插入图片描述

与距离编码类似, 每个编码都表示一个或多个长度, 表示多个长度时后面会有 extra 位指示具体的长度. 长度编码能表示的长度范围为 3 至 258.
注意：所以在 DEFLATE 中，长度 1~2 的重复不会用匹配项表示（直接把这 1~2 个字节原样输出（即用字面值编码）通常比引用匹配（还要额外编码长度和距离）更短！）；只有长度 ≥ 3 时才会用匹配项 (length, distance) 来引用重复块。
解压时, 当读到编码小于等于 255, 则认为这是个普通字符, 原样输出即可; 若在 257 至 285 之间, 则说明遇到了一个重复标记, 这意味着当前编码表示的是长度, 且下一个编码表示的是距离. 解码得到长度和距离, 再在解压缓冲区中找到相应的部分输出即可; 若为 256, 则说明压缩块结束了.

从LZ777编码到霍夫曼编码
上一步的LZ777编码结果为：

ab(2, 2) (4,2)c

字符串统计频率为：

a:1
b:01
c:00

字符编码为：

101(2, 2) (4,2)00

然后对偏移距离和匹配长度进行编码
但是这里发现匹配字符长度是从3开始的，那么这个2怎么编码呢？原来这里的deflate算法是使用了改进型的LZ777算法
参考文章：Gzip 格式和 DEFLATE 压缩算法

改进型的LZ777算法

LZ77压缩算法将所有数据都处理成为一个三元组串，每个三元组至少需要3个字节表示，如果在动态字典中未找到匹配字符串，会将1个字节输出为3个字节，这就导致了字节浪费。因此在DEFLATE算法中对其使用的LZ77算法进行了以下改进：

对匹配字符串长度小于3的字符串不压缩。因为长度小于3的字符串，使用三元组表示，对原始数据不能起到压缩的作用。
对字符串的匹配长度进行了限制，范围为（-128~127），用8bit表示，滑动窗口大小为32KB，用15bit表示，将压缩数据构造为标识+数据的形式，具体如表3所示。该存储方式，降低了压缩数据的存储空间。
由于只查找匹配长度大于3的字符串，为提高算法速度，在查找匹配字符串时，使用了哈希链结构搜索算法，其中哈希算法将3字节压缩到2字节，虽然哈希链结构存在搜索到错误结果的可能，但还是大幅提高了搜索速度。

所以最终的编码结果为：

a:1
b:01
c:00

这里的字符串“abababc”，连续匹配都没有超过三个字符，直接按照这个字符串常量进行编码即可

10110110100

代码实现

压缩对象

在开始编写代码前，我们需要弄清楚，需要压缩的对象是什么？

视频、音频、图片等文件本身就是压缩格式
mp4、jpg、png、avi、mp3 这些格已经过复杂压缩算法处理（如 H.264、H.265、JPEG、LZ77 等）。
👉 所以再次使用 GZIP 压缩不会有太大效果，反而可能略微增加体积。
GZIP 对二进制内容的压缩效率很低
GZIP 是为文本内容设计的压缩算法（如 HTML、JSON、JavaScript 等）。
它依赖数据的可预测性和重复性（如文本中的重复词、空格等）来压缩。
视频文件的数据模式看起来是“随机的”，压缩器无法从中找到有效的模式。

gzip实现

GzipMiddleware.h代码：

    GzipMiddleware():clientSupportGzip_(true){};void before(HttpRequest& request) override;void after(HttpResponse& response) override;void setClientSupportGzip(bool flag){clientSupportGzip_=flag;}bool isClinetSupportGzip() const {return clientSupportGzip_;}double getGzipEnableRate() const {uint64_t total = totalRequests_.load();return total == 0 ? 0.0 : (double)gzipAppliedCount_.load() / total;}double getAverageCompressionRatio() const {uint64_t original = originalSizeSum_.load();return original == 0 ? 0.0 : (double)compressedSizeSum_.load() / original;}private:bool compressGzip(const std::string& input, std::string& output);bool clientSupportGzip_;// gzip统计信息void checkArchive();  // 检查是否需要归档void resetStats();    // 重置统计信息std::atomic<uint64_t> totalRequests_{0};std::atomic<uint64_t> gzipAppliedCount_{0};std::atomic<uint64_t> originalSizeSum_{0};std::atomic<uint64_t> compressedSizeSum_{0};// std::function<void(uint64_t, uint64_t, uint64_t, uint64_t)> archiveCallback_;static constexpr uint64_t MAX_REQUESTS_BEFORE_ARCHIVE = 1e9;static constexpr uint64_t MAX_ORIGINAL_SIZE_BEFORE_ARCHIVE = 1ULL << 40; // 1 TB

GzipMiddleware.cpp代码：

void GzipMiddleware::before(HttpRequest& request)
{   // 从客户端请求头中获取 Accept-Encoding 字段std::string acceptEncoding=request.getHeader("Accept-Encoding");// 判断是否包含 "gzip" 关键字// 如果包含，说明客户端支持 gzip 压缩// 否则，不支持 gzip 压缩，如果不支持，就不进行gzip压缩acceptEncoding.find("gzip") != std::string::npos?setClientSupportGzip(true):setClientSupportGzip(false);}//--------------------------------------
// GzipMiddleware::after
//--------------------------------------
void GzipMiddleware::after(HttpResponse& response) 
{   // 统计总请求数（用于后续压缩统计归档）totalRequests_++;if (!isClinetSupportGzip())     // 如果客户端不支持 gzip，则直接跳过压缩return;//判断是否应该压缩，消息体大于256字节并且消息类型是文本、html等类型才可以//对于视频、图片等已经使用了其他压缩算法进行压缩了的，就不再使用gzip进行压缩了if (!response.isShouldGzipCompress()) return;// 获取原始响应体内容const std::string& rawBody = response.getBody();std::string compressed;// 调用实际压缩方法if (compressGzip(rawBody, compressed)) {// LOG_INFO<<"gzipAppliedCount_:"<<gzipAppliedCount_.load()<<"originalSizeSum_"<<originalSizeSum_.load()<<"compressedSizeSum_"<<compressedSizeSum_.load();gzipAppliedCount_++;originalSizeSum_ += rawBody.size();compressedSizeSum_ +=compressed.size();response.addHeader("Content-Encoding", "gzip");  // 添加响应头标识压缩格式为 gzipresponse.setContentLength(compressed.size());    // 更新 Content-Length 为压缩后大小response.setBody(compressed);                    // 设置压缩后的响应体}// 检查是否需要归档统计信息checkArchive();
}//--------------------------------------
// GzipMiddleware::compressGzip实际的压缩处理算法
//--------------------------------------
bool GzipMiddleware::compressGzip(const std::string& input, std::string& output)
{constexpr int CHUNK = 16384; z_stream strm{};    //zlib 用于压缩的状态结构体，记录输入、输出缓冲区状态等char out[CHUNK];    //输出缓冲区，用来暂存压缩后的数据块strm.zalloc = Z_NULL;strm.zfree = Z_NULL;strm.opaque = Z_NULL;if (deflateInit2(&strm,             //压缩状态Z_BEST_COMPRESSION, //压缩等级（0~9），9 表示最高压缩比，牺牲性能Z_DEFLATED,         //使用 DEFLATE 算法15 + 16,           //15位窗口大小(32KB), +16启用 GZIP 格式输出（否则是 zlib）8,                 //内部压缩缓冲区大小参数，一般为 8Z_DEFAULT_STRATEGY) != Z_OK) //默认压缩策略{return false;}strm.avail_in = input.size();          // 待压缩数据长度strm.next_in = (Bytef*)input.data();   // 待压缩数据do {strm.avail_out = CHUNK;            //待压缩数据存储buffer 的长度，如果多次写，会覆盖之前的写的数据//当然，之前的数据已经被读走了strm.next_out = reinterpret_cast<Bytef*>(out); //待压缩数据存储的bufferdeflate(&strm, Z_FINISH);            //如果输入和待输出的数据都被处理完，则返回 Z_STREAM_ENDsize_t have = CHUNK - strm.avail_out;//总长度-当前可写=已经写的数据长度output.append(out, have);} while (strm.avail_out == 0);deflateEnd(&strm);                       //释放deflateInit2申请的空间LOG_INFO<<"原始的数据大小为:"<< input.size();LOG_INFO<<"GZIP压缩完成,压缩比例为:"<<(static_cast<double>(output.size()) / input.size());;return true;
}void GzipMiddleware::checkArchive() {// 如果压缩的总请求数或原始数据累计大小超过阈值// 就清理统计数据（可用于后续监控、日志）if (totalRequests_ >= MAX_REQUESTS_BEFORE_ARCHIVE ||originalSizeSum_ >= MAX_ORIGINAL_SIZE_BEFORE_ARCHIVE) {totalRequests_ = 0;gzipAppliedCount_ = 0;originalSizeSum_ = 0;compressedSizeSum_ = 0;}
}