簡單的理解deflate算法

最近做壓縮算法. 用到了deflate壓縮算法, 找了很多資料, 這篇文章算是講的比較易懂的,這篇文章不長,但卻淺顯易懂, 基本上涵蓋了我想要知道的所有要點. 翻譯出來, 留存. 可能對正在學(xué)習(xí)或者準(zhǔn)備學(xué)習(xí)deflate算法的童鞋有所幫助.

先說一下deflate算法吧. deflate是zip壓縮文件的默認(rèn)算法. 其實deflate現(xiàn)在不光用在zip文件中, 在7z, xz等其他的壓縮文件中都用. 實際上deflate只是一種壓縮數(shù)據(jù)流的算法. 任何需要流式壓縮的地方都可以用. deflate 還有微型改進版本deflate64. “微型改進型” 這個名詞是我發(fā)明的, 為什么這么說, 因為改進實在太小了, 而性能提高也非常小. 以至于大名鼎鼎的開源zlib庫到現(xiàn)在都不支持deflate64. http://zlib.net/zlib_faq.html

開始正題, 原文地址:http://zlib.net/feldspar.html, 我盡量按照原文直譯,但是有些地方實在沒必要就簡單意譯了. 有想交流的童鞋歡迎訪問我的獨立博客留言交流:http://byNeil.com

==========================華麗的分割線====================

Deflate 算法的介紹

作者:Antaeus Feldspar feldspar@netcom.com

在理解deflate之前, 先理解它的兩個組成算法非常重要: Huffman 編碼 和 LZ77壓縮

Huffman 編碼

Huffman編碼是一種前綴編碼, 你其實知道, 但你可能不覺得. 比如打電話時, 從撥號開始, 你按下一串號碼, 或許是5781112 或者別的號碼. 一串號碼就就能到達(dá)另一部特定的電話. (翻譯: 這個比方太羅嗦,本來不想翻譯過來的.)

(這一段就不翻譯了,沒有實際內(nèi)容.)Now suppose you’re in an office setting with an internal switchboard, as many large companies do. All other phones within the bank only require five numbers to dial, instead of seven — that’s because it’s expected that you’ll be calling those numbers more often. You may still need to call other numbers, though — so all of those numbers have a `9′ added to the front.

…這就是前綴編碼. 每一個你想要指定的元素都有一個由數(shù)字組成的代碼. 由于每個代碼都不可能是另外一個代碼的前綴, 所以當(dāng)你輸入的時候,不會有歧義.

Huffman 編碼是由一個特定算法生成的前綴編碼. (翻譯: 后面簡單介紹如何生成Huffman編碼, 都是教課書上的內(nèi)容, 不翻譯了, 自己看圖, 直接跳過:)Here, instead of each code being a series of numbers between 0 and 9, each code is a series of bits, either 0 or 1. Instead of each code representing a phone, each code represents an element in a specific “alphabet” (such as the set of ASCII characters, which is the primary but not the only use of Huffman coding in DEFLATE).

A Huffman algorithm starts by assembling the elements of the “alphabet,” each one being assigned a “weight” — a number that represents its relative frequency within the data to be compressed. These weights may be guessed at beforehand, or they may be measured exactly from passes through the data, or some combination of the two. In any case, the elements are selected two at a time, the elements with the lowest weights being chosen. The two elements are made to be leaf nodes of a node with two branches (I really hope you know nodes and trees…) Anyway, suppose we had a set of elements and weights that looked like this:

A 16
B 32
C 32
D 8
E 8
We would pick D and E first, and make them branches of a single node — one being the `0′ branch, and one the `1′ branch.

( )
0 / 1
D E

…… (翻譯中間省略無數(shù)廢話, 都是在介紹怎么生成huffman樹, 這個上過課的人都知道, 所以就不翻譯了, 細(xì)節(jié)非常繁瑣. 下面直接從 課本上沒有的另一個算法 Lz77開始:)

LZ77 壓縮
LZ77壓縮算法靠查找重復(fù)的序列. 這里使用術(shù)語:”滑動窗口”, 它的意思是:在任何的數(shù)據(jù)點上, 都記錄了在此之前的字符. 32k的滑動窗口表示壓縮器(解壓器)能記錄前32768個字符. 當(dāng)下一個需要壓縮的字符序列能夠在滑動窗口中找到, 這個序列會被兩個數(shù)字代替: 一個是距離,表示這個序列在窗口中的起始位置離窗口的距離, 一個是長度, 字符串的長度.

我覺得 看 比 說 更容易. 我們看看一些高壓縮比的數(shù)據(jù):

Blah blah blah blah blah!

字符流開始于: `B,’ `l,’ `a,’ `h,’ ` ,’ and `b.’ , 看看接下來的5個字符:

vvvvv
Blah blah blah blah blah!
^^^^^
接下來的5個字符正好和已經(jīng)在數(shù)據(jù)流中的字符串相等, 而且剛好在當(dāng)前數(shù)據(jù)點的前5個字符開始. 在這個case中,我們可以在數(shù)據(jù)流中輸出特殊的字符, 一個長度數(shù)字 和一個距離數(shù)字.
目前數(shù)據(jù)是:
Blah blah b
壓縮后的格式是:
Blah b[D=5,L=5]
壓縮還能繼續(xù)增加, 盡管要利用其全部的優(yōu)勢需要壓縮器方面的智慧. 對比這兩個相同的字符串, 對比它們各自的下一個字符,都是’l', 所以,我們可以把長度更新為6, 而不僅僅是5. 如果我們繼續(xù)比較,發(fā)現(xiàn)下一個, 下下一個, 下下下一個都是一樣的. 盡管前面的字符換已經(jīng)延伸覆蓋到了后面的字符串(需要壓縮的字符串).
最終我們發(fā)現(xiàn), 有18個字符相等. 當(dāng)我們解壓的時候, 當(dāng)讀到長度和距離對時, 我們并不知道這18個字符將會是什么. 但是如果我們把已有的字符放回去, 我們就知道更多. 而這有會讓更多的字符放回去, 或者知道任何長度大于距離的數(shù)據(jù)對都會不斷的重復(fù)數(shù)據(jù). 所以解壓器就可以這樣做.
最終我們的高壓縮性的數(shù)據(jù)能壓縮成如下的樣子:
Blah b[D=5, L=18]!
聯(lián)合起來(翻譯: 指的是把huffman編碼和 lz77壓縮算法聯(lián)合起來用):
deflate 壓縮器在怎樣壓縮數(shù)據(jù)上有非常大的靈活性. 程序員必須處理設(shè)計聰明的算法所面臨的問題以做出正確的選擇. 但是壓縮器的確有一些選擇.
壓縮器有三種壓縮模型:
1. 不壓縮數(shù)據(jù), 對于已經(jīng)壓縮過的數(shù)據(jù),這是一個明智的選擇. 這樣的數(shù)據(jù)會會稍稍增加, 但是會小于在其上再應(yīng)用一種壓縮算法.
2. 壓縮, 先用Lz77, 然后用huffman編碼. 在這個模型中壓縮的樹是Deflate 規(guī)范規(guī)定定義的, 所以不需要額外的空間來存儲這個樹.
3. 壓縮, 先用LZ77, 然后用huffman編碼. 壓縮樹是由壓縮器生成的, 并與數(shù)據(jù)一起存儲.

數(shù)據(jù)被分割成不同的塊, 每個塊使用單一的壓縮模式. 如過壓縮器要在這三種壓縮模式中相互切換, 必須先結(jié)束當(dāng)前的塊, 重新開始一個新的塊.

關(guān)于Lz77和huffman如何一起工作的細(xì)節(jié)需要更進一步的檢查. 一旦原始數(shù)據(jù)被轉(zhuǎn)換成了字符和長度距離對組成的串, 這些數(shù)據(jù)必須由huffman編碼表示.
盡管這不是一個標(biāo)磚術(shù)語, 把開始讀數(shù)據(jù)的點叫”撥號音”, 畢竟在我們的類推中, 撥號音的確是我們指定一個電話的的撥號的開始點. 所以我們把這個起始點叫”撥號音”. 在起始點之后, 只可能有三種元素能出現(xiàn):字符, 長度距離對, 或者是塊的結(jié)束標(biāo)志. 因為我們必須能夠區(qū)分它是什么. 所有可能的字符(字面量), 表示可能長度的區(qū)域, 以及特殊的塊結(jié)束標(biāo)記都被合并到同一個字母表中. 這個字母表就是huffman樹的基礎(chǔ). 距離不需要包含在字母表中, 因為它只能出現(xiàn)在長度的后面. 一點字面量被解壓, 或者長度距離對解壓出來, 我們就開始了另一個撥號音, 重新開始讀取. 當(dāng)然,如果遇到塊結(jié)束標(biāo)志的話, 就會開始另外一個塊,或者到達(dá)了壓縮數(shù)據(jù)的末尾.
長度或者距離的編碼實際上可以是: 一個基地址,后面跟上額外的bits(整數(shù)的形式,表示基地址后面的偏移),

可能deflate規(guī)范中最難理解的部分就是當(dāng)數(shù)據(jù)時被特殊的樹壓縮的時候, 樹與數(shù)據(jù)一起的壓縮方式.
樹 通過 編碼長度(codelengths)來傳輸, 正如前面討論的. 代碼長度被全部放在一個由0到15之間的數(shù)字組成的序列中(huffman樹種,代碼長度必須不大于15, 這是最復(fù)雜部分, 而不是怎樣約束元素的順序).

并不是所有的元素都必須有一個代碼長度. 如果字母表的最后的那些元素代碼長度都是0, 他們能并且應(yīng)該被忽略. 由于每個字母表中元素的個數(shù)都會被傳輸, 所以這兩個字母表會被鏈接成單一的序列.

一旦編碼長度序列組合完成, 它會被一種叫做 run-length 的壓縮方式壓縮. 當(dāng)一行中的多個元素?fù)碛幸粯拥拇a長度(常常是0) 的時候, 特殊的符號會用來表示這個長度的元素的個數(shù). 現(xiàn)在這個序列式0到18之間的數(shù)字組成的了(可能帶有額外的位組成修改基地址的值).

huffman 樹就是為這個0到18的字母表創(chuàng)建的.

huffman樹需要包含在數(shù)據(jù)中, 當(dāng)然. 正如其他的huffman樹一樣, 它會被記錄代碼長度的形式包含進來. 然而, 它們的順序不是0, 1, 2, 3, 4 … 16, 17, 18. 而是一個特殊的順序:16, 17, 18, 0, 8, 7, 9, 6, 10, 5, 11, 4, 12, 3, 13, 2, 14, 1, 15. 這背后的邏輯是:越靠近序列末尾的代碼,越可能是長度為0. 如果它們的確是0, 就能被省略掉. 直接記錄的元素的個數(shù)也會包含在數(shù)據(jù)中.

這些就是我覺得在deflate 規(guī)范中的難點. 多花時間讀規(guī)范,應(yīng)該能幫助了解. 有任何別的問題請聯(lián)系:- Antaeus Feldspar ( feldspar@netcom.com)

總結(jié)

以上是生活随笔為你收集整理的简单的理解deflate算法的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。