壓縮算法deflate_第1頁
壓縮算法deflate_第2頁
壓縮算法deflate_第3頁
壓縮算法deflate_第4頁
全文預(yù)覽已結(jié)束

下載本文檔

版權(quán)說明:本文檔由用戶提供并上傳,收益歸屬內(nèi)容提供方,若內(nèi)容存在侵權(quán),請進(jìn)行舉報(bào)或認(rèn)領(lǐng)

文檔簡介

1、壓縮算法 deflategzip,zlib,以及圖形格式 png,使用的是同一個壓縮算法 deflate。我們通過對 gzip 源碼的分析來對 deflate 壓縮算法做一個詳細(xì)的說明。 我閱讀的 gzip 版本為 gzip-1.2.4。 我們對算法做三種程度的說明。第一種程度,對 gzip 所使用壓縮算法基本原理的說明。第二種程度,對 gzip 壓縮算法實(shí)現(xiàn)方法的說明。第三種程度,對 gzip 實(shí)現(xiàn)源碼級的說明。如果你有時間的話,我建議你先不要看下面的內(nèi)容,自己嘗試通過讀 gzip源碼,來了解它的壓縮解壓縮是如何實(shí)現(xiàn)的,這將會是一個非常有趣的智力游戲,千萬不要錯過。當(dāng)一個又一個的謎被解開時,

2、那感覺就像唐伯虎同志所說的,“慷慨然諾杯酒中”。(小唐的詩,除了另一個倒霉蛋曹雪芹外,好像不太被人提。)1 gzip 所使用壓縮算法的基本原理gzip 對于要壓縮的文件,首先使用 lz77 算法進(jìn)行壓縮,對得到的結(jié)果再使用huffman 編碼的方法進(jìn)行壓縮。所以我們分別對 lz77 和 huffman 編碼的原理進(jìn)行說明。1.1 .1.2.2 gzip 壓縮算法實(shí)現(xiàn)方法2.1 LZ77 算法的 gzip 實(shí)現(xiàn)首先,gzip 從要壓縮的文件中讀入 64KB 的內(nèi)容到一個叫 window 的緩沖區(qū)中。為了簡單起見,我們以 32KB 以下文件的壓縮為例做說明。對于我們這里使用 32KB 以下文件,g

3、zip 將整個文件讀入到 window 緩沖區(qū)中。然后使用一個叫 strstart 的變量在window 數(shù)組中,從 0 開始一直向后移動。strstart 在每一個位置上,都在它之前的區(qū)域中,尋找和當(dāng)前 strstart 開始的用的頭 3 個字節(jié)匹配的用,并試圖從這些匹配用中找到最長的匹配用。如果當(dāng)前的 strstart 開始的用,可以找到最少為 3 個字節(jié)的匹配用的話,當(dāng)前的strstart 開始的匹配長度那么長的申,將會被一個匹配長度,到匹配用開頭的距離對替換。如果當(dāng)前的 strstart 開始的用,找不到任何的最少為 3 個字節(jié)的匹配用的話,那么當(dāng)前 strstart 的所在字節(jié)將不作

4、改動。為了區(qū)分是一個匹配長度,到匹配用開頭的距離對,還是一個沒有被改動的字節(jié),還需要為每一個沒有被改動的字節(jié)或者匹配長度,到匹配用開頭的距離對,另外再占用一位,來進(jìn)行區(qū)分。這位如果為 1,表示是一個匹配長度,到匹配用開頭的距離對,這位如果為 0,表示是一個沒有被改動的字節(jié)?,F(xiàn)在來說明一下,為什么最小匹配為 3 個字節(jié)。這是由于,gzip 中,匹配長度,到匹配用開頭的距離對中,匹配長度”的范圍為 3-258,也就是 256 種可能值,需要8bit 來保存。到匹配用開頭的距離的范圍為 0-32K,需要 15bit 來保存。所以一個匹配長度,到匹配用開頭的距離對需要 23 位,差一位 3 個字節(jié)。如

5、果匹配用小于 3 個字節(jié)的話,使用匹配長度,到匹配用開頭的距離對進(jìn)行替換,不但沒有壓縮,反而還會增大。所以彳存匹配長度,到匹配用開頭的距離對所需要的位數(shù),決定了最小匹配長度至少要為 3 個字節(jié)。卜面我們就來介紹 gzip 如何實(shí)現(xiàn)尋找當(dāng)前 strstart 開始的用的最長匹配用如果每次為當(dāng)前用尋找匹配用時, 都要和之前的每個用的至少 3 個字節(jié)進(jìn)行比較的話,那么比較量將是非常非常大的。為了提高比較速度,gzip 使用了哈希表。這是 gzip 實(shí)現(xiàn) LZ77 的關(guān)鍵。這個哈希表是一個叫 head 的數(shù)組(后面我們將看到為什么這個緩沖區(qū)叫 head)。gzip 對 windows 中的每個用,使用

6、用的頭三個字節(jié),也就是 strstart,strstart+1,strstart+2,用一個設(shè)計(jì)好的哈希函數(shù)來進(jìn)行計(jì)算,得到一個插入位置 ins_h。也就是用用的頭三個字節(jié)來確定一個插入位置。然后把用的位置,也就是 strstart 的值,保存在 head 數(shù)組的第 ins_h 項(xiàng)中。我們馬上就可以看到為什么要這樣做。head 數(shù)組在沒有插入任何值時,全部為00當(dāng)某處的當(dāng)前用的三個字節(jié)確定了一個 ins_h,并把當(dāng)時當(dāng)前用的位置也就是當(dāng)時的strstart 保存在了 headins_h中。之后另一處,當(dāng)另一處的當(dāng)前用的頭三個字節(jié),再為那三個字節(jié)時,心使用那個哈希函數(shù)來計(jì)算,由于是同樣的三個字節(jié)

7、,同樣的哈希函數(shù),得到的 ins_h 必然和前面得到的 ins_h 是相同的。于是就會發(fā)現(xiàn)headins_h不為 0。這就說明了,有一個頭三個字節(jié)和自己相同的用把自己的位置保存不了這里,現(xiàn)在 headins_h中保存的值,也就是那個用的開始位置,我們就可以找到那個用,那個用至少前 3 個字節(jié)和當(dāng)前用的前 3 個字節(jié)相同(稍后我們就可以看到這種說法不準(zhǔn)確,這里是為了說明方便),我們可以找到那個用,做進(jìn)一步比較,看到底能有多長的匹配。我們現(xiàn)在來說明一下, 相同的三個字節(jié), 通過哈希函數(shù)得到的 ins_h 必然是相同的。而不同的三個字節(jié),通過哈希函數(shù)有沒有可能得到同一個 ins_h,我沒有對這個哈希

8、函數(shù)做研究,并不清楚,不過一般的哈希函數(shù)都是這樣而,所以極大可能這里的也會是這種情況,即不同的三個字節(jié),通過哈希函數(shù)有可能得到同一個 ins_h,不過這并不要緊,我們發(fā)現(xiàn)有可能是匹配用之后,還會進(jìn)行申的比較。一個文件中,可能有很多個用的頭三個字節(jié)都是相同的,也就是說他們計(jì)算得到的 ins_h 都是相同的,如何能保證找到他們中的每一個用呢?gzip 使用個鏈把他們鏈在一起。gzip 每次把當(dāng)前用的位置插入 head 的當(dāng)前用頭三個字節(jié)算出的ins_h 處時,都會首先把原來的 headins_h的值,保存到一個叫 prev 的數(shù)組中,殺存的位置就在現(xiàn)在的 strstart 處。這樣當(dāng)以后某處的當(dāng)前

9、審計(jì)算出 ins_h,發(fā)現(xiàn) headins_h不空時,就可以到 prevheadins_h中找到更前一本的頭三個字節(jié)相同而用的位置。對此我們舉例說明。一例,用0abcdabceabcfabcgAAAAAAAAAAAAAAAAA01234567890123456整個用被壓縮程序處理之后。由 abc 算出 ins_h。這時的 headins_h中為 13,即abcg的開始位置。這時 prev13中為 9,即abcfabcg的開始位置。這時 prev9中為 5,即abceabcfabcg”的開始位置。這時 prev5中為 1,即abcdabceabcfabcg”的開始位置。這時 prev1中為 0。

10、我們看到所有頭三個字母為 abc 的用,被鏈在了一起,從 head 可以一直找下去,直到找到00現(xiàn)在我們也就知道了,三個字節(jié)通過哈希函數(shù)計(jì)算得到同一 ins_h 的所有的用被鏈在了一起,headins_h為鏈頭,prev 數(shù)組中放著的更早的用。這也就是 head 和prev 名稱的由來。gzip 尋找匹配用的另外一個值得注意的實(shí)現(xiàn)是,延遲匹配。會進(jìn)行兩次嘗試。比如當(dāng)前用為 str,那么 str 發(fā)生匹配以后,并不發(fā)生壓縮,還會對 str+1 用進(jìn)行匹配,然后看哪種匹配效果好。例子從這個例子中我們就看到了做另外一次嘗試的原因。如果碰到的一個匹配就使用了的話,可能錯過更長匹配的機(jī)會。現(xiàn)在做兩次會有

11、所改善。2.2 問題討論我在這里對 gzip 壓縮算法做出了一些說明,是希望可以和對 gzip 或者壓縮解壓縮感興趣的朋友進(jìn)行交流。我對 gzip 的了解要比這里說的更多一些,也有更多的例子。如果哪位朋友愿意對下面的問題進(jìn)行研究,以及其他壓縮解壓縮的問題進(jìn)行研究,來這里http:/ 3 個字節(jié)(最小匹配)來計(jì)算一個整數(shù),是否比用用比較來得高效,高效到什么程度。哈希函數(shù)的討論。不同的三個字節(jié),是否可能得到同一個 ins_hoins_h 和計(jì)算它的三個字節(jié)的關(guān)系。一一幾次延遲嘗試比較好?用延遲,兩次嘗試是否對壓縮率的改善是非常有限的?影響 lz77 壓縮率的因素。壓縮的極限。2.3 .3 gzip 源碼分析main()中調(diào)用函數(shù) treat_file()。treat_file()中打開文件,調(diào)用函數(shù) zip()。注意這里的 work 的用法,這是一個畝數(shù)指針。zip()中輸出 gzip 文件格式的頭,調(diào)用 bi_init,ct_init,lm_init,其中在 lm_init 中將 head 初始化清 0。初始化 strstart

溫馨提示

  • 1. 本站所有資源如無特殊說明,都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請下載最新的WinRAR軟件解壓。
  • 2. 本站的文檔不包含任何第三方提供的附件圖紙等,如果需要附件,請聯(lián)系上傳者。文件的所有權(quán)益歸上傳用戶所有。
  • 3. 本站RAR壓縮包中若帶圖紙,網(wǎng)頁內(nèi)容里面會有圖紙預(yù)覽,若沒有圖紙預(yù)覽就沒有圖紙。
  • 4. 未經(jīng)權(quán)益所有人同意不得將文件中的內(nèi)容挪作商業(yè)或盈利用途。
  • 5. 人人文庫網(wǎng)僅提供信息存儲空間,僅對用戶上傳內(nèi)容的表現(xiàn)方式做保護(hù)處理,對用戶上傳分享的文檔內(nèi)容本身不做任何修改或編輯,并不能對任何下載內(nèi)容負(fù)責(zé)。
  • 6. 下載文件中如有侵權(quán)或不適當(dāng)內(nèi)容,請與我們聯(lián)系,我們立即糾正。
  • 7. 本站不保證下載資源的準(zhǔn)確性、安全性和完整性, 同時也不承擔(dān)用戶因使用這些下載資源對自己和他人造成任何形式的傷害或損失。

評論

0/150

提交評論