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;}
}