资源描述：
《谈谈zip的压缩原理与代码实现机械基础》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、zip的壓縮原理與實現無損資料壓縮是一件奇妙的事情,想一想,一串任意的資料能夠根據一定的規則轉換成只有原來1/2-1/5長度的資料,並且能夠按照相應的規則還原到原來的樣子,聽起來真是很酷｡半年前,苦熬過初學vc時那段艱難的學習曲線的我,對MFC､SDK開始失望和不滿,這些雖然不算易學,但和DHTML沒有實質上的區別,都是調用微軟提供的各種各樣的函數,不需要你自己去創建一個視窗,多線程編程時,也不需要你自己去分配CPU時間｡我也做過驅動,同樣,有DDK(微軟盤機動開發包),當然,也有DDK的“參考手冊”,連一個最簡單的資料結構都不需要你自己做,
2、一切都是函數､函數……微軟的高級程式師編寫了函數讓我們這些搞應用的去調用,我不想在這裏貶低搞應用的人,正是這些應用工程師連接起了科學和社會之間的橋樑,將來可以做銷售,做管理,用自己逐漸積累起來的智慧和經驗在社會上打拼｡ 但是,在技術上來說,誠實地說,這並不高深,不是嗎?第一流的公司如微軟､Sybase､Oracle等總是面向社會大眾的,這樣才能有巨大的市場｡但是他們往往也是站在社會的最頂層的:作業系統､編譯器､資料庫都值得一代代的專家去不斷研究｡這些帝國般的企業之所以偉大,恐怕不是“有經驗”､“能吃苦”這些中國特色的概念所能涵蓋的,艱
3、深的技術體系､現代的管理哲學､強大的市場能力都是缺一不可的吧｡我們既然有志於技術,並且正在起步階段,何必急不可耐地要轉去做“管理”,做“青年才俊”,那些所謂的“成功人士”的根底能有幾何,這樣子浮躁,胸中的規模和格局能有多大? 在我發現vc只是一個用途廣泛的編程工具,並不能代表“知識”､“技術”的時候,我有些失落,無所不能的不是我,而是MFC､SDK､DDK,是微軟的工程師,他們做的,正是我想做的,或者說,我也想成為那種層次的人,現在我知道了,他們是專家,但這不會是一個夢,有一天我會做到的,為什麼不能說出我的想法呢｡那時公司做的系統裏
4、有一個壓縮模組,領導找了一個zlib庫,不讓我自己做壓縮演算法,站在公司的立場上,我很理解,真的很理解,自己做演算法要多久啊｡但那時自己心中隱藏的一份倔強驅使我去尋找壓縮原理的資料,我完全沒有意識到,我即將打開一扇大門,進入一個神奇的“資料結構”的世界｡“電腦藝術”的第一線陽光,居然也照到了我這樣一個平凡的人的身上｡ 上面說到“電腦藝術”,或者進一步細化說“電腦編程藝術”,聽起來很深奧,很高雅,但是在將要進入專業的壓縮演算法的研究時,我要請大家做的第一件事情是:忘掉自己的年齡､學歷,忘掉自己的社會身份,忘掉編程語言,忘掉“面向物件”､
5、“三層架構”等一切術語｡把自己當作一個小孩,有一雙求知的眼睛,對世界充滿不倦的､單純的好奇,唯一的前提是一個正常的具有人類理性思維能力的大腦｡下面就讓我們開始一段神奇的壓縮演算法之旅吧:1.原理部分:有兩種形式的重複存在於電腦資料中,zip就是對這兩種重複進行了壓縮｡一種是短語形式的重複,即三個位元組以上的重複,對於這種重複,zip用兩個數字:1.重複位置距當前壓縮位置的距離;2.重複的長度,來表示這個重複,假設這兩個數位各占一個位元組,於是資料便得到了壓縮,這很容易理解｡一個位元組有0-255共256種可能的取值,三個位元組有256*256
6、*256共一千六百多萬種可能的情況,更長的短語取值的可能情況以指數方式增長,出現重複的概率似乎極低,實則不然,各種類型的資料都有出現重複的傾向,一篇論文中,為數不多的術語傾向於重複出現;一篇小說,人名和地名會重複出現;一張上下漸變的背景圖片,水準方向上的圖元會重複出現;程式的原始檔案中,語法關鍵字會重複出現(我們寫程式時,多少次前後copy､paste?),以幾十K為單位的非壓縮格式的資料中,傾向于大量出現短語式的重複｡經過上面提到的方式進行壓縮後,短語式重複的傾向被完全破壞,所以在壓縮的結果上進行第二次短語式壓縮一般是沒有效果的｡第二種重複
7、為單字節的重複,一個位元組只有256種可能的取值,所以這種重複是必然的｡其中,某些位元組出現次數可能較多,另一些則較少,在統計上有分佈不均勻的傾向,這是容易理解的,比如一個ASCII文字檔案中,某些符號可能很少用到,而字母和數位則使用較多,各字母的使用頻率也是不一樣的,據說字母e的使用概率最高;許多圖片呈現深色調或淺色調,深色(或淺色)的圖元使用較多(這裏順便提一下:png圖片格式是一種無損壓縮,其核心演算法就是zip演算法,它和zip格式的檔的主要區別在於:作為一種圖片格式,它在檔頭處存放了圖片的大小､使用的顏色數等資訊);上面提到的短語式
8、壓縮的結果也有這種傾向:重複傾向於出現在離當前壓縮位置較近的地方,重複長度傾向於比較短(20位元組以內)｡這樣,就有了壓縮的可能:給256種位元組取值重新編碼,使出
