zlib库介绍四：zlib算法（LZ77、LZ78、霍夫曼编码、滑动窗口、Rabin-Karp算法、哈希链、I/O缓冲区）
1.簡(jiǎn)介
在2017年，我有機(jī)會(huì)從事一個(gè)旨在提高數(shù)據(jù)壓縮性能的項(xiàng)目。在此過(guò)程中，我研究了zlib庫(kù)及其實(shí)現(xiàn)的deflate壓縮算法。在這里，我想與那些也希望對(duì)zlib有更好理解的人分享我的研究。
1.1 什么是zlib
zlib是一個(gè)免費(fèi)的開(kāi)源軟件庫(kù)，用于無(wú)損數(shù)據(jù)壓縮?和?減壓。它是由Jean-loup Gailly（壓縮）和Mark Adler（解壓縮）用C語(yǔ)言編寫(xiě)的。zlib的第一個(gè)版本于1995年5月發(fā)布。Jean-loupGailly和Mark Adler也為gzip（GNU zip）。在后臺(tái)，gzip使用zlib庫(kù)。
迄今為止，zlib主要由Mark Adler維護(hù)，其最新更新和版本均可在GitHub上找到。Mark Adler還積極參與Stack Overflow，以回答有關(guān)zlib和gzip的技術(shù)問(wèn)題。
許多軟件應(yīng)用程序和庫(kù)都使用zlib。如果引起注意，您幾乎可以在操作系統(tǒng)，Internet服務(wù)，流服務(wù)，文檔編輯器等中的任何地方找到zlib。這是這些應(yīng)用程序的不完整列表。
zlib規(guī)范于1996年5月獲得正式的Internet RFC（征求意見(jiàn)）狀態(tài)。
- RFC 1950：zlib壓縮數(shù)據(jù)格式
- RFC 1951：壓縮壓縮數(shù)據(jù)格式
- RFC 1952：gzip文件格式
2.壓縮算法
的?壓縮?zlib中使用的算法是?放氣方法。deflate方法將輸入數(shù)據(jù)編碼為壓縮數(shù)據(jù)。的減壓?zlib中使用的算法是?膨脹?方法，這是一種解碼過(guò)程，需要使用壓縮的位流進(jìn)行解壓縮并正確生成原始的全尺寸數(shù)據(jù)或文件。
在本文檔中，我將重點(diǎn)介紹zlib的壓縮部分以及zlib對(duì)zlib的實(shí)現(xiàn)。?放氣算法。
我會(huì)用這樣的話?“數(shù)據(jù)字節(jié)”，?“數(shù)據(jù)字節(jié)”，?“數(shù)據(jù)符號(hào)”，?“數(shù)據(jù)流”，?“位流”指示要壓縮的數(shù)據(jù)。在下面的部分中，這些詞具有相同的含義并且可以互換。
2.1 放氣
放氣的方法最初是由定義菲爾·卡茨在PKWARE的歸檔工具PKZIP 2.x版本?它是LZ77算法?和?霍夫曼編碼。
下圖從高層次說(shuō)明了放氣和充氣過(guò)程。
2.2 LZ77
LZ77是基于字典的無(wú)損壓縮算法。它也被稱(chēng)為L(zhǎng)Z1。
基于字典的算法的基本思想是，通過(guò)引用該序列的先前出現(xiàn)來(lái)替換數(shù)據(jù)中特定字節(jié)序列的出現(xiàn)。
基于字典的壓縮算法有兩種主要類(lèi)型：LZ77和LZ78。這兩個(gè)算法以?xún)蓚€(gè)創(chuàng)建者Jakob Ziv和Abraham Lempel命名。LZ77（Lempel-Ziv77）和LZ78（Lempel-Ziv78）分別發(fā)表于1977年和1978年。
LZ77壓縮算法通過(guò)使用?滑動(dòng)窗口?查找重復(fù)的數(shù)據(jù)序列，并使用稱(chēng)為a的一對(duì)數(shù)字對(duì)每個(gè)重復(fù)的序列進(jìn)行編碼?長(zhǎng)距離對(duì)。
2.2.1 滑動(dòng)窗口
滑動(dòng)窗口用于檢查輸入數(shù)據(jù)序列，并維護(hù)用作字典的歷史數(shù)據(jù)。換句話說(shuō)，字典是先前出現(xiàn)和編碼的數(shù)據(jù)的一部分。
滑動(dòng)窗由兩部分組成：?搜索緩沖區(qū)和?前瞻緩沖區(qū)。搜索緩沖區(qū)包含字典-最近編碼的數(shù)據(jù)，而前瞻緩沖區(qū)包含要編碼的輸入數(shù)據(jù)序列的下一部分。下圖給出了一個(gè)滑動(dòng)窗口的示例。
滑動(dòng)窗的尺寸是影響壓縮性能的關(guān)鍵因素之一。如果滑動(dòng)窗口太小，則壓縮器可能會(huì)發(fā)現(xiàn)較少的重復(fù)數(shù)據(jù)序列，結(jié)果，壓縮文件的大小將更大。如果滑動(dòng)窗口太大，則壓縮器可能需要花費(fèi)更長(zhǎng)的時(shí)間來(lái)查找重復(fù)的數(shù)據(jù)序列，因此壓縮速度將變慢。
實(shí)際上，滑動(dòng)窗口的大小通?？梢詮膸譑B到MB，例如4 KB，32 KB，1 MB或4 MB。
2.2.2 長(zhǎng)距離對(duì)
長(zhǎng)度-距離對(duì)指示下一個(gè)?長(zhǎng)度?字符與字符完全相同?距離?原始數(shù)據(jù)流中后面的字符。
在LZ77算法中，壓縮器通過(guò)搜索緩沖區(qū)進(jìn)行搜索，直到找到與超前緩沖區(qū)中的第一個(gè)字符匹配為止。搜索緩沖區(qū)中可能存在多個(gè)匹配項(xiàng)，并且壓縮程序?qū)⒄业介L(zhǎng)度最長(zhǎng)的一個(gè)匹配項(xiàng)。當(dāng)。。。的時(shí)候最長(zhǎng)的匹配?找到后，壓縮器將其編碼為三元組?（D，L，C）?哪里：
- D =搜索光標(biāo)到超前緩沖區(qū)起點(diǎn)的距離
- L =最長(zhǎng)匹配的長(zhǎng)度
- C =超前緩沖區(qū)中最長(zhǎng)匹配的下一個(gè)字符
在三元組中添加第三個(gè)元素C的原因是為了處理在搜索緩沖區(qū)中找不到匹配項(xiàng)的情況。在這種情況下，D和L的值均為0，并且C是當(dāng)前預(yù)讀緩沖區(qū)中的第一個(gè)字符。
下圖顯示了LZ77如何找到最長(zhǎng)匹配項(xiàng)并為給定字符串編碼重復(fù)字符“axrrmaxrbaxssr”的示例。
實(shí)際上，壓縮器可以根據(jù)自己的實(shí)現(xiàn)來(lái)優(yōu)化編碼輸出，并選擇除?（D，L，C）?三胞胎。
2.3 霍夫曼編碼
霍夫曼編碼是一種統(tǒng)計(jì)壓縮方法。它使用以下代碼編碼數(shù)據(jù)符號(hào)（例如字符）可變長(zhǎng)度代碼，代碼長(zhǎng)度基于相應(yīng)符號(hào)的頻率。
霍夫曼編碼以及其他可變長(zhǎng)度編碼方法具有兩個(gè)屬性：
霍夫曼編碼有兩個(gè)步驟：
霍夫曼碼可以是?固定（靜態(tài)）?要么?動(dòng)態(tài)。兩者都用deflate方法。
可以通過(guò)檢查大量數(shù)據(jù)集并找到典型的代碼長(zhǎng)度來(lái)創(chuàng)建固定的霍夫曼代碼。使用固定霍夫曼編碼時(shí)，所有輸入數(shù)據(jù)符號(hào)均使用相同的編碼。
動(dòng)態(tài)霍夫曼碼是通過(guò)將輸入數(shù)據(jù)分為多個(gè)塊，并為每個(gè)數(shù)據(jù)塊生成代碼來(lái)生成的。
3. zlib的實(shí)現(xiàn)
zlib的實(shí)現(xiàn)是實(shí)用且高效的。在過(guò)去的20年中，人們進(jìn)行了許多嘗試來(lái)提高壓縮應(yīng)用程序的性能，但是似乎我們只能通過(guò)使用除放氣（和放氣），采用并行處理或改進(jìn)CPU級(jí)別指令以外的算法來(lái)獲得更好的性能。因此，zlib（在其GitHub存儲(chǔ)庫(kù)中指出）相當(dāng)龐大而精致的壓縮庫(kù)。
在以下各節(jié)中，我們將介紹zlib用于實(shí)現(xiàn)deflate壓縮算法的一些詳細(xì)技術(shù)。
3.1 壓縮等級(jí)
zlib具有10個(gè)壓縮級(jí)別（0-9）。不同級(jí)別的壓縮性能不同壓縮率?和?速度。級(jí)別0表示不壓縮，zlib將輸出原始數(shù)據(jù)。1級(jí)是最快的，但壓縮率較低。級(jí)別9提供最高的壓縮率，但壓縮速度較慢。zlib使用的默認(rèn)壓縮級(jí)別為6。
在引擎蓋下，壓縮級(jí)別會(huì)在放氣過(guò)程中更改放氣策略和參數(shù)。更多細(xì)節(jié)將在以下各節(jié)中討論。
3.2 滑動(dòng)窗口
在zlib中，滑動(dòng)窗口的默認(rèn)大小為64KB?；瑒?dòng)窗分為兩部分，分別對(duì)應(yīng)搜索緩沖區(qū)?和?前瞻緩沖區(qū)，每個(gè)部分為32KB。輸入字節(jié)被讀入窗口的后半部分，然后移至前半部分以保持至少32KB的字典。該組織確保始終以塊大小（8KB）的倍數(shù)執(zhí)行IO。此外，在較舊的平臺(tái)MSDOS上64KB的限制非常有用。
以下代碼段顯示了如何初始化滑動(dòng)窗口。宏MAX_WBITS確定滑動(dòng)窗口的大小。它是可配置的，默認(rèn)值為15，這將導(dǎo)致32KB的搜索緩沖區(qū)和64KB的滑動(dòng)窗口。
define MAX_WBITS 15 /* 32K LZ77 window */s->w_bits = windowBits; s->w_size = 1 << s->w_bits; s->w_mask = s->w_size - 1;s->window = (Bytef *) ZALLOC(strm, s->w_size, 2*sizeof(Byte));當(dāng)超前緩沖區(qū)不足時(shí)，數(shù)據(jù)將被復(fù)制到滑動(dòng)窗口中。此過(guò)程在函數(shù)內(nèi)部實(shí)現(xiàn)fill_window。
local void fill_window(s)deflate_state *s; {... }3.3 尋找最長(zhǎng)的匹配
zlib用于在搜索緩沖區(qū)中找到最長(zhǎng)匹配項(xiàng)的技術(shù)很簡(jiǎn)單，而且對(duì)于大多數(shù)輸入文件來(lái)說(shuō)，它是最快的：使用字符串匹配算法查找可能的匹配項(xiàng)，然后嘗試所有可能的匹配項(xiàng)并選擇最長(zhǎng)的匹配項(xiàng)。
小字符串的匹配算法的靈感來(lái)自?Rabin-Karp算法。該算法的關(guān)鍵特征是，在字符串字典中的插入非常簡(jiǎn)單，因此速度很快，并且完全避免了刪除。插入在每個(gè)輸入字符處執(zhí)行，而字符串匹配僅在上一個(gè)匹配結(jié)束時(shí)執(zhí)行。因此，最好花更多時(shí)間進(jìn)行匹配，以允許非?？焖俚淖址迦氩⒈苊鈩h除。當(dāng)發(fā)現(xiàn)較小的匹配項(xiàng)時(shí)，將使用蠻力方法來(lái)查找較長(zhǎng)的字符串。
因此，總而言之，找到最長(zhǎng)匹配項(xiàng)的過(guò)程包括兩個(gè)主要部分：
3.3.1?匹配長(zhǎng)度限制
zlib將MIN_MATCH和MAX_MATCH定義為最低?和?最大值?匹配搜索的長(zhǎng)度。
#define MIN_MATCH 3 #define MAX_MATCH 258MIN_MATCH設(shè)置為3。最小匹配長(zhǎng)度等于3的原因很明顯：小于3的匹配將無(wú)助于減小編碼數(shù)據(jù)的大小，因?yàn)榫幋a數(shù)據(jù)符號(hào)的長(zhǎng)度將相同或更長(zhǎng)。
除非您更改相關(guān)代碼（例如，多次調(diào)用UPDATE_HASH函數(shù)），否則無(wú)法更改MIN_MATCH值。
將MAX_MATCH設(shè)置為258這個(gè)數(shù)字是來(lái)自一個(gè)事實(shí)，即一個(gè)長(zhǎng)的距離對(duì)，這是LZ77編碼的數(shù)據(jù)符號(hào)的輸出，可以在最258個(gè)字節(jié)代表。長(zhǎng)度至少需要一位，距離至少需要一位，因此輸入兩位可以發(fā)出258個(gè)字節(jié)。
zlib中的MAX_MATCH值可以更改，但是更改可能會(huì)影響壓縮性能。同樣在zlib中，還有一些由condition控制的邏輯MAX_MATCH == 258。啟用這些代碼后，使用現(xiàn)代編譯器時(shí)，可以提高壓縮性能。
#if (defined(UNALIGNED_OK) && MAX_MATCH == 258)/* This code assumes sizeof(unsigned short) == 2. Do not use* UNALIGNED_OK if your compiler uses a different size.*/if (*(ushf*)(match+best_len-1) != scan_end ||*(ushf*)match != scan_start) continue;...3.3.2 Rabin-Karp算法
Rabin-Karp算法是由Richard M. Karp和Michael O. Rabin創(chuàng)建的字符串搜索算法。它使用散列來(lái)查找文本中一組模式字符串中的任何一個(gè)。例如，給定文字“AABAACAADAABAABA”和圖案“AABA”，我們可以使用Rabin-Karp算法來(lái)找出模式在索引中的文本存在0，9，12。
以下偽代碼描述了Rabin-Karp算法的工作原理。
# p is a pattern, its length is m # t is text, its length is n # the algorithm searches for pattern p in text tCompute hash_p (for pattern p) Compute hash_t (for the first substring of t with m length) for i = 0 to n - m:if hash_p == hash_t:Match t[i . . . i+m-1] with p, if matched return 1else:Update hash_t for t[i+1 . . . i+m] using rolling hash End的?平均?和?最佳情況下的運(yùn)行時(shí)間Rabin-Karp算法的O表示O（n + m），其中n是文本的長(zhǎng)度，m是圖案的長(zhǎng)度。但是它最壞的情況下時(shí)間是O（nm）。當(dāng)模式和文本的所有字符與文本的所有子字符串的哈希值與模式的哈希值匹配時(shí)，會(huì)發(fā)生Rabin-Karp算法的最壞情況。例如text = “AAAAAAA”和pattern = “AAA”。
Rabin-Karp算法性能的關(guān)鍵是通過(guò)使用以下命令來(lái)有效計(jì)算文本的連續(xù)子字符串的哈希值：?滾動(dòng)哈希技術(shù)。滾動(dòng)哈希的好處是，它只需執(zhí)行恒定數(shù)量的操作即可計(jì)算前一個(gè)子字符串的下一個(gè)子字符串的哈希值，而不必重新哈希整個(gè)子字符串。
3.3.3 哈希鏈
如前所述，Rabin-Karp算法檢查子字符串的哈希值，以查找文本中的匹配項(xiàng)。為了在存儲(chǔ)最新數(shù)據(jù)符號(hào)的搜索緩沖區(qū)中找到匹配項(xiàng)，zlib使用了哈希鏈組織保留每3個(gè)字節(jié)（或由MIN_MATCH定義的其他值）的哈希值的記錄。
zlib中的此哈希鏈通過(guò)使用兩個(gè)數(shù)組來(lái)實(shí)現(xiàn)：prev[]和head[]。兩個(gè)數(shù)組都將位置存儲(chǔ)在滑動(dòng)窗口中。該head[]數(shù)組存儲(chǔ)哈希鏈的頭部，該prev[]數(shù)組存儲(chǔ)并鏈接具有相同哈希索引的字符串的位置。下圖顯示了哈希鏈如何工作的示例。
在此示例中，HashValue函數(shù)及其結(jié)果僅是示例，并不準(zhǔn)確。
prev[]的大小限制為滑動(dòng)窗口的一半。因?yàn)閜rev[]維護(hù)的鏈接僅適用于搜索緩沖區(qū)中的數(shù)據(jù)，并且默認(rèn)情況下僅最后32K字符串。在索引prev[]陣列是窗口索引模32K。
以下代碼段顯示了zlib如何實(shí)現(xiàn)哈希鏈組織。哈希大小隨memLevel為每個(gè)壓縮級(jí)別配置的參數(shù)而變化。
s->hash_bits = (uInt)memLevel + 7; s->hash_size = 1 << s->hash_bits;s->prev = (Posf *) ZALLOC(strm, s->w_size, sizeof(Pos)); s->head = (Posf *) ZALLOC(strm, s->hash_size, sizeof(Pos));#define UPDATE_HASH(s,h,c) (h = (((h)<<s->hash_shift) ^ (c)) & s->hash_mask)#define INSERT_STRING(s, str, match_head) \(UPDATE_HASH(s, s->ins_h, s->window[(str) + (MIN_MATCH-1)]), \match_head = s->prev[(str) & s->w_mask] = s->head[s->ins_h], \s->head[s->ins_h] = (Pos)(str)) #endif#define CLEAR_HASH(s) \s->head[s->hash_size-1] = NIL; \zmemzero((Bytef *)s->head, (unsigned)(s->hash_size-1)*sizeof(*s->head));在中CLEAR_HASH，數(shù)組head[]被清除。數(shù)組prev[]是動(dòng)態(tài)清除的，不是這里清除的。
3.3.4 自適應(yīng)搜索限制
在哈希鏈中搜索最長(zhǎng)匹配項(xiàng)時(shí)，zlib會(huì)限制?鏈長(zhǎng) 以提高搜索效率。搜索限制是通過(guò)以下方式設(shè)置的：
搜索極限值在?配置表：
local const config configuration_table[10] = { /* good lazy nice max_chain_length */ /* 0 */ {0, 0, 0, 0, deflate_stored}, /* store only */ /* 1 */ {4, 4, 8, 4, deflate_fast}, /* max speed, no lazy matches */ /* 2 */ {4, 5, 16, 8, deflate_fast}, /* 3 */ {4, 6, 32, 32, deflate_fast}, /* 4 */ {4, 4, 16, 16, deflate_slow}, /* lazy matches */ /* 5 */ {8, 16, 32, 32, deflate_slow}, /* 6 */ {8, 16, 128, 128, deflate_slow}, /* 7 */ {8, 32, 128, 256, deflate_slow}, /* 8 */ {32, 128, 258, 1024, deflate_slow}, /* 9 */ {32, 258, 258, 4096, deflate_slow}}; /* max compression */在上面的代碼片段中：
- 0-9是壓縮級(jí)別。
- good，lazy，nice是一個(gè)很好的匹配，水上匹配和一個(gè)漂亮的匹配的長(zhǎng)度值。
- max_chain_length?是zlib搜索的最大鏈長(zhǎng)。
3.4 霍夫曼編碼
Zib既實(shí)現(xiàn)?靜態(tài)（固定）霍夫曼編碼?和?動(dòng)態(tài)霍夫曼編碼。對(duì)于LZ77編碼數(shù)據(jù)的每個(gè)塊，zlib使用靜態(tài)霍夫曼編碼和動(dòng)態(tài)霍夫曼編碼來(lái)計(jì)算該塊中的位數(shù)，然后選擇方法?產(chǎn)生?較小的數(shù)量數(shù)據(jù)的。如果使用兩種方法使位數(shù)相等，則zlib選擇靜態(tài)霍夫曼編碼，因?yàn)榻獯a過(guò)程更快。
整個(gè)數(shù)據(jù)流可以包含靜態(tài)和動(dòng)態(tài)霍夫曼編碼數(shù)據(jù)的混合。在每個(gè)塊的放氣流頭中發(fā)送霍夫曼碼。
總而言之，zlib中的霍夫曼編碼過(guò)程包括以下步驟：
3.5 I / O緩沖區(qū)
壓縮中的一個(gè)重要概念是?數(shù)據(jù)塊。 壓縮數(shù)據(jù)格式由塊組成，這些塊的頭取決于塊數(shù)據(jù)。因此，deflate的輸出一次到達(dá)一個(gè)塊，直到第一個(gè)塊完成之前，什么都沒(méi)有寫(xiě)（zlib或gzip標(biāo)頭除外）?？紤]到數(shù)據(jù)塊在deflate過(guò)程中如何傳輸，zlib實(shí)現(xiàn)了幾個(gè)緩沖區(qū)?存儲(chǔ)數(shù)據(jù)塊并控制I / O性能。
3.5.1 輸入緩沖器
開(kāi)始?jí)嚎s之前，zlib?積累數(shù)據(jù)?在一個(gè)?輸入緩沖區(qū)，當(dāng)輸入緩沖區(qū)已滿時(shí)開(kāi)始?jí)嚎s。默認(rèn)輸入緩沖區(qū)大小為8KB。
之所以具有輸入緩沖區(qū)，是因?yàn)閦lib不會(huì)生成任何輸出數(shù)據(jù)，直到在其中生成16K數(shù)據(jù)符號(hào)為止。?文字緩沖區(qū)（文字緩沖區(qū)的默認(rèn)大小為16K，有關(guān)文字緩沖區(qū)的詳細(xì)信息，請(qǐng)參見(jiàn)下一部分）。因此，以非常短的數(shù)據(jù)長(zhǎng)度開(kāi)始?jí)嚎s沒(méi)有任何好處。使用輸入緩沖區(qū)可提高I / O效率。
可以使用gzbuffer功能更改默認(rèn)的輸入緩沖區(qū)大小。
gzbuffer(file, size) {...state->want = size;... }3.5.2 文字緩沖
文字緩沖區(qū)存儲(chǔ)的數(shù)據(jù)符號(hào)由LZ77編碼。符號(hào)可以是編碼為文字的單個(gè)字節(jié)，也可以是長(zhǎng)度-距離對(duì)，它可以對(duì)前32K未壓縮數(shù)據(jù)中某處最多258個(gè)字節(jié)的副本進(jìn)行編碼。默認(rèn)的文字緩沖區(qū)大小為16K，因此未壓縮數(shù)據(jù)的累積范圍為16K至4MB（對(duì)于高度可壓縮的數(shù)據(jù)）。
一旦?文字緩沖區(qū)已滿，zlib決定為霍夫曼編碼構(gòu)造哪種塊，然后執(zhí)行此操作，創(chuàng)建標(biāo)頭，該標(biāo)頭針對(duì)動(dòng)態(tài)塊描述該塊中的霍夫曼代碼，然后為該塊創(chuàng)建編碼符號(hào)?；蛘?#xff0c;它會(huì)創(chuàng)建一個(gè)存儲(chǔ)塊或靜態(tài)塊，無(wú)論結(jié)果是最少的位數(shù)。只有這樣，壓縮數(shù)據(jù)才能用于輸出。
默認(rèn)文字緩沖區(qū)大小由marco配置DEF_MEM_LEVEL。在zlib的代碼中，DEF_MEM_LEVEL = 8，所有壓縮級(jí)別都相同。因此，所有壓縮級(jí)別都具有相同的16K文字緩沖區(qū)大小。
3.5.3 輸出緩沖器
為了輸出壓縮數(shù)據(jù)，zlib使用兩個(gè)緩沖區(qū)：?暫掛緩沖區(qū)， 和?輸出緩沖區(qū)。數(shù)據(jù)流如下圖所示：
初始化后，zlib將創(chuàng)建一個(gè)暫掛緩沖區(qū)（默認(rèn)大小為36K）和一個(gè)輸出緩沖區(qū)（默認(rèn)大小為8K）。首先輸出數(shù)據(jù)累積在未決緩沖區(qū)中，然后得到?復(fù)制到輸出緩沖區(qū)，最后將其寫(xiě)入輸出的壓縮zip或gz文件中。
數(shù)據(jù)從函數(shù)flush_pending中的待處理緩沖區(qū)復(fù)制到輸出緩沖區(qū)。當(dāng)文字緩沖區(qū)已滿時(shí)，即表示已處理數(shù)據(jù)塊時(shí)，將調(diào)用此函數(shù)。在某些其他情況下，當(dāng)需要刷新塊時(shí)也會(huì)調(diào)用它。復(fù)制到輸出緩沖區(qū)的數(shù)據(jù)長(zhǎng)度受輸出緩沖區(qū)中的可用空間限制。
當(dāng)。。。的時(shí)候?輸出緩沖區(qū)已滿，或何時(shí)?沖洗信號(hào)?發(fā)出后，zlib將輸出緩沖區(qū)寫(xiě)入zip或gz文件。
zlib使用計(jì)數(shù)器pending_out和avail_out記錄未決緩沖區(qū)和輸出緩沖區(qū)中有多少字節(jié)可用。計(jì)數(shù)器值0表示緩沖區(qū)已滿。
相關(guān)代碼段：
flush_pending() {len = s->pending;if (len > strm->avail_out) len = strm->avail_out;if (len == 0) return;zmemcpy(strm->next_out, s->pending_out, len); } gzcomp() {if (strm->avail_out == 0 || (flush != Z_NO_FLUSH &&(flush != Z_FINISH || ret == Z_STREAM_END))) {have = (unsigned)(strm->next_out - state->x.next);if (have && ((got = write(state->fd, state->x.next, have)) < 0 || (unsigned)got != have)) {gz_error(state, Z_ERRNO, zstrerror());return -1;}if (strm->avail_out == 0) {strm->avail_out = state->size;strm->next_out = state->out;}} }4.優(yōu)化zlib
多家公司對(duì)通過(guò)優(yōu)化zlib的實(shí)施來(lái)提高壓縮性能感興趣。以下是一些摘要最近的相關(guān)作品。
4.1 英特爾：zlib-new
參考：英特爾：英特爾架構(gòu)處理器上的高性能ZLIB壓縮（pdf）
優(yōu)化的重點(diǎn)在于改進(jìn)的散列，在LZ77進(jìn)程中搜索子串的最長(zhǎng)前綴匹配以及Huffman代碼流。
改進(jìn)的哈希：對(duì)于壓縮級(jí)別1到5，哈希元素為四元組（至少匹配4個(gè)字節(jié)）。對(duì)于6到9的壓縮級(jí)別，請(qǐng)使用zlib的原始哈希元素作為三元組（至少匹配3個(gè)字節(jié)）。
添加兩個(gè)其他策略：級(jí)別1為DEFLATE_quick，級(jí)別4至6為DEFLATE_medium。
- DEFLATE_quick：將哈希鏈搜索限制為第一個(gè)條目。
- DEFLATE_medium：旨在在zlib的壓縮率之間取得平衡?DEFLATE_slow?策略以及zlib的性能?DEFLATE_fast戰(zhàn)略。找到匹配項(xiàng)后，它將跳過(guò)匹配長(zhǎng)度的轉(zhuǎn)發(fā)，并支持延遲匹配評(píng)估的變體。當(dāng)在位置p和長(zhǎng)度l上找到匹配項(xiàng)時(shí)，在位置p + l + 1檢查匹配項(xiàng)。如果找到新的匹配項(xiàng)，則從position?p + l + 1向后掃描，以確定是否可以改善第二個(gè)匹配項(xiàng)。
哈希表移動(dòng)速度更快：利用SSE（Intel?）一次對(duì)8個(gè)條目（16字節(jié)）進(jìn)行哈希移位。
更快的CRC計(jì)算：利用PCLMULQDQ（Intel?）指令以更改的算法一次處理64字節(jié)的輸入。
減少循環(huán)展開(kāi)：消除了現(xiàn)代處理器上Adler32和CRC32計(jì)算中過(guò)多的循環(huán)展開(kāi)。對(duì)于Adler32，將展開(kāi)系數(shù)從16減小到8。對(duì)于CRC32，將展開(kāi)系數(shù)從8減小到4。
4.2 IBM：快速放氣
參考：IBM：Deflate的快速實(shí)現(xiàn)
優(yōu)化的重點(diǎn)是通過(guò)使用LZ4的重復(fù)消除過(guò)程和改進(jìn)的霍夫曼編碼過(guò)程來(lái)提高zlib放氣過(guò)程的速度。
用LZ4替換LZ77更快地消除重復(fù)：觀察到的提速是中等的，可能由于緩存使用率的差異而未達(dá)到LZ4的性能。還觀察到的壓縮比幾乎不受影響。
強(qiáng)制使用靜態(tài)霍夫曼樹(shù)：達(dá)到較快的速度，但可能對(duì)壓縮率產(chǎn)生負(fù)面影響。
半靜態(tài)霍夫曼編碼：使用靜態(tài)樹(shù)壓縮中間數(shù)據(jù)的第一個(gè)塊（LZ77的輸出），并收集該第一個(gè)塊的統(tǒng)計(jì)信息，以構(gòu)建用于編碼后續(xù)塊的霍夫曼樹(shù)。第一個(gè)塊的大小是配置，默認(rèn)大小是8KB。其他塊的大小也是可配置的，默認(rèn)值為128KB。添加的另一個(gè)步驟是在構(gòu)建霍夫曼樹(shù)之前確定初始?jí)K的統(tǒng)計(jì)信息，以確定是否值得使用動(dòng)態(tài)樹(shù)。這種方法既可以實(shí)現(xiàn)更快的速度，又可以實(shí)現(xiàn)更好的壓縮率。
4.3 臉書(shū)：Zstandard
參考：Facebook Zstandard（zstd）設(shè)計(jì)介紹
GitHub上的Zstandard
Zstandard旨在與現(xiàn)代硬件一起擴(kuò)展，并壓縮得更快，更小，從而可以對(duì)各種數(shù)據(jù)類(lèi)型進(jìn)行通用壓縮。
通過(guò)結(jié)合幾種最新創(chuàng)新并針對(duì)現(xiàn)代硬件來(lái)改進(jìn)zlib。
增加視窗大小?到1MB-8MB（推薦）。
壓縮使用?有限狀態(tài)熵?基于ANS（非對(duì)稱(chēng)數(shù)字系統(tǒng)）的系統(tǒng)，以提高性能并減少延遲。
用?repcode建模?有效壓縮結(jié)構(gòu)化數(shù)據(jù)
用一個(gè)?無(wú)分支設(shè)計(jì)風(fēng)格?減少CPU分支預(yù)測(cè)器的開(kāi)銷(xiāo)。
在解壓縮中，將數(shù)據(jù)分成多個(gè)并行流，并使用新一代的霍夫曼解碼器?并行解碼多個(gè)符號(hào)一個(gè)核心。這利用了現(xiàn)代CPU的能力，即每個(gè)周期可以發(fā)出多個(gè)指令。
4.4 Google：Zopfli，Brotli
參考：使用Zopfli的數(shù)據(jù)壓縮（pdf），Brotli，Deflate，Zopfli，LZMA，LZHAM和Bzip2壓縮算法的比較（pdf）
GitHub上的Zopfli
GitHub上的Brotli
Google在2013年推出了?佐普利，與deflate格式兼容。Zopfli給較小的壓縮數(shù)據(jù)大小?比gzip（小3.7-8.3％），但它具有?壓縮速度較慢?比gzip 9級(jí)高。Zopfli庫(kù)只能壓縮，不能解壓縮。
布羅特利?嘗試實(shí)施?新的壓縮格式，并且比放氣更有效。它的速度與放氣相似，但壓縮更緊密。
Brotli壓縮格式在RFC 7932中定義。該算法結(jié)合了LZ77算法的現(xiàn)代變體，霍夫曼編碼和二階上下文建模的組合。它還使用包含超過(guò)13K個(gè)單詞的靜態(tài)字典。靜態(tài)字典有助于壓縮短文件。
4.5 蘋(píng)果：LZFSE
參考：Apple數(shù)據(jù)壓縮：LZFSE
LZFSE專(zhuān)為iOS和macOS設(shè)計(jì)，以實(shí)現(xiàn)更高的能源效率和速度（介于2x和3x之間）。
LZFSE算法的用途?LZ77?和?有限狀態(tài)熵編碼。
4.6 CloudFlare：zlib
參考：CloudFlare與癌癥抗?fàn)?#xff1a;開(kāi)放源代碼帶來(lái)的意想不到的好處
GitHub上的CloudFlare zlib fork
CloudFlare對(duì)zlib的改進(jìn)包括：
- 用?uint64_t?替換16位類(lèi)型。
- 使用?改進(jìn)的哈希函數(shù)iSCSI CRC32。此功能作為Intel處理器上的硬件指令實(shí)現(xiàn)。它具有非?？斓男阅芎透玫呐鲎残阅?。
- 搜索至少匹配的項(xiàng)?4字節(jié)。
- 使用SIMD指令?窗戶滾動(dòng)。
- 使用Intel的硬件無(wú)攜帶乘法指令PCLMULQDQ?CRC32校驗(yàn)和。
- 優(yōu)化的最長(zhǎng)匹配功能。這是庫(kù)中對(duì)性能要求最高的功能。
尚未包含在已發(fā)布的zlib fork中的其他實(shí)驗(yàn)：
- 使用zlib（哈希鏈）中使用的鏈表的改進(jìn)版本
基準(zhǔn)測(cè)試結(jié)果
- 測(cè)試數(shù)據(jù)集是四個(gè)標(biāo)準(zhǔn)語(yǔ)料庫(kù)數(shù)據(jù)，包括ASCII文本，位圖圖像，數(shù)字和源代碼文件。
- 速度：通常，CloudFlare的zlib比zlib和Intel的zlib快2至9級(jí)，尤其是6至9級(jí)（2倍-7.5倍）。
- 壓縮率：在所有級(jí)別上與zlib非常相似，并且在級(jí)別1上優(yōu)于Intel的zlib。
4.7 CloudFlare：預(yù)設(shè)字典
參考：CloudFlare：使用預(yù)設(shè)的deflate字典改善壓縮
優(yōu)化旨在提高HTML文件的壓縮性能（降低25％）（主要是?短文）。
將最小匹配長(zhǎng)度更改為?4字節(jié)。
用一個(gè)?預(yù)設(shè)字典?因此在輸入的開(kāi)頭有用于搜索匹配項(xiàng)的反向參考。
- 通過(guò)對(duì)一組要壓縮的文件執(zhí)行偽LZ77來(lái)創(chuàng)建預(yù)設(shè)字典，并在每個(gè)輸入文件的前16Kb中找到DEFLATE不會(huì)壓縮的字符串。然后對(duì)各個(gè)字符串進(jìn)行頻率計(jì)數(shù)，并根據(jù)其長(zhǎng)度和頻率對(duì)其進(jìn)行評(píng)分。得分最高的字符串將保存到詞典文件中。
- 使用Go程序制作這樣的deflate字典：GitHub上的獨(dú)裁者
總結(jié)
以上是生活随笔為你收集整理的zlib库介绍四：zlib算法（LZ77、LZ78、霍夫曼编码、滑动窗口、Rabin-Karp算法、哈希链、I/O缓冲区）的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。
- 上一篇： 激活函数（activation func
- 下一篇： linux幸运字符,删好友后幸运字符怎么