Huffman編碼
????? Huffman編碼是第一個真正實用的編碼方法，由D.A.Huffman在1952年提出。當時Huffman是麻省理工學院的一名學生，據(jù)說為了向老師證明自己可以不參加某門功課的期末考試，他設計了這個看似簡單卻影響深遠的編碼方法。Huffman編碼效率高，運算速度快，實現(xiàn)方式靈活，從20世紀60年代直到現(xiàn)在，在數(shù)據(jù)壓縮領域得到了廣泛的應用。而20世紀80年代初，Huffman編碼又出現(xiàn)在CP/M和DOS系統(tǒng)中，即使在今天，在許多知名的壓縮工具和壓縮算法里（如WinZip、gzip和JPEG），也都有Huffman編碼的身影。不過，Huffman編碼所得的編碼長度只是對信息熵計算結(jié)果的一種近似，并不能真正逼近信息熵的極限。Huffman編碼影響力很深遠，至今還在計算機大專學生必修課程《數(shù)據(jù)結(jié)構(gòu)》中被提及。
????? LZ是其發(fā)明者J.Ziv和A.Lempel兩個猶太人姓氏的縮寫。此二人于1977年發(fā)表題為《順序數(shù)據(jù)壓縮的一個通用算法》的論文，論文中描述的算法被后人稱為LZ77算法。1978年，二人又發(fā)表了該論文的續(xù)篇，描述了后來被命名為LZ78的壓縮算法。其實LZ系列的算法并不新鮮，其中既沒有高深的理論背景，也沒有復雜的數(shù)學公式。它們只是簡單的延續(xù)了千百年來人們對字典的追崇和喜好，并用一種極為巧妙的方式將字典技術(shù)運用于通用數(shù)據(jù)壓縮領域。簡單的說如果你習慣用字典中的頁碼和行號代替文章中的每個單詞的時候，那實際上你已經(jīng)掌握了LZ系列算法的真諦，因此這類編碼算法被統(tǒng)稱為Dictionary coders。
????? 在1984年，Terry Welch發(fā)表論文描述了他在Sperry研究中心（現(xiàn)在Unisys公司的一部分）的研究成果，也就是后來非常有名的LZW算法。它實質(zhì)上是LZ78算法的一個變種，但被認為是一個獨立的編碼算法。LZW繼承了LZ77和LZ78壓縮效果好、速度快的優(yōu)點，而且在算法描述上更容易被人們接受，實現(xiàn)也相對簡單。而在其后發(fā)展出來的各式各樣的字典編碼算法，基本上都是這三種編碼算法的分支或變體。也就是說LZ77、LZ78和LZW是字典編碼中最基礎的3種編碼算法。今天我們熟悉的PKZIP、WinZip、WinRAR、gzip等壓縮工具都是LZ系列算法的受益者，甚至連PGP這樣的加密文件格式也選擇了LZ系列算法作為其數(shù)據(jù)壓縮的標準。
字典式編碼不但在壓縮效果上大大超過了Huffman編碼，而且在實現(xiàn)上，壓縮和解壓縮的速度也異常驚人。于是LZ系列算法的優(yōu)越性很快就在數(shù)據(jù)壓縮領域里體現(xiàn)出來，使用LZ系列算法的工具軟件數(shù)量呈爆炸式增長。UNIX系統(tǒng)上最先出現(xiàn)了使用LZW算法的Compress程序，該程序性能優(yōu)良，很快成為UNIX世界的壓縮程序標準。緊隨其后的是MS-DOS環(huán)境下的ARC程序，還有像PKARC等仿制品。LZ78和LZW一時間幾乎統(tǒng)治了UNIX和DOS兩大平臺。然而隨著時間流逝，事情變得耐人尋味。目前為止占據(jù)個人用戶計算機的主流壓縮工具幾乎都采用LZ77變種算法，為什么？

叛逆斗士的勝利--ZIP格式誕生
????? 為什么技術(shù)實現(xiàn)上更為優(yōu)秀的LZ78和LZW沒有成為最主流的算法？LZ77與它們有什么不同？答案是--專利權(quán)。
????? 相對于LZ77完全沒有專利限制來說，LZ78在美國稍稍涉及到一些專利禁止區(qū)，而LZW正像上文所說的專利權(quán)最終歸屬于Unisys公司。因此直接應用LZ78的算法可能會帶來意想不到的麻煩，而所有使用LZW算法（哪怕是他的變體）的人都要獲得Unisys公司的專利許可。這種專利限制是相當廣泛的，例如GIF圖像格式使用了LZW算法，那么所有開發(fā)GIF編碼/解碼器的人都必須要有LZW專利使用許可，這意味著繳納大筆的專利費。
????? 在DOS年代由于計算機存儲介質(zhì)容量的微小，個人用戶對數(shù)據(jù)壓縮軟件的渴望是現(xiàn)在的用戶無法想象的。例如在1984年，個人計算機的標配不過是容量360kB的5.25寸軟盤而已，如果個人能將數(shù)據(jù)壓縮數(shù)倍后存儲，不啻于節(jié)省了一大筆錢。這種渴望在1988年時達到了頂峰，這正是互聯(lián)網(wǎng)剛剛形成雛形的年代，網(wǎng)絡數(shù)據(jù)交換開始出現(xiàn)。當時最流行的是使用電話線撥號登錄別人在家里搭建的服務平臺--BBS系統(tǒng)，當時中國也曾有幾十個這樣的BBS存在，比如水木清華BBS。這種方式不但可以傳遞文本信息，也可由用戶上傳文件到站點的計算機以供其他用戶下載。不過由于電話線的接入速度慢的可憐，那時的接入標準僅僅是14.4kbit/s，通過BBS傳輸稍大一點的文件就叫人萬分痛苦。于是數(shù)據(jù)壓縮軟件就成為了BBS用戶一項必須的工具還記得上文提到1985年SEA公司開發(fā)的MS-DOS環(huán)境下第一個應用LZW算法的ARC壓縮軟件嗎？它是當時MS-DOS下統(tǒng)治性的壓縮軟件。從技術(shù)角度來說ARC確實不錯，但使用了專利LZW算法的ARC當然是標準的商業(yè)軟件，使用這種軟件工作就必須付費。不過當時許多玩家根本買不起ARC軟件，順便說一句題外話，那時大多PC玩家基本都沒什么富裕的錢，事實上個人計算機本身的發(fā)展就是被窮玩家精打細算所推動。不過個人計算機從誕生之日起就充滿了叛逆、自由的精神，這也是推動整個個人計算機世界前行的主要動力。此時一個年輕的程序員出現(xiàn)并試圖改變壓縮世界，這個人叫Phillip W.Katz（菲利普·卡茲）。
????? 20世紀七八十年代出售軟件的方式和現(xiàn)在截然不同，以ARC軟件來說，它不僅包括了一份EXE可執(zhí)行文件，還包括它的C語言源代碼。經(jīng)常混跡于BBS上的菲利普·卡茲同樣買不起ARC,于是他自己將ARC的C語言源代碼進行復制并用匯編語言重寫,并將這個壓縮工具稱作PKARC,這個程序自然與ARC完全兼容,而且由于使用匯編使得速度較ARC更快.在當時的計算機世界里這是一種很普遍的現(xiàn)象,并沒有程序員認為這種行為不對,甚至只要不與自己沖突,被改寫者通常也不在乎.不過這次不太一樣,菲利普·卡茲不僅僅是自己和朋友用,而是將這個軟件以非強迫性注冊的共享軟件形式向他人發(fā)放,但即使是不注冊,一樣可以毫無限制地使用下去,大批ARC用戶自然也就轉(zhuǎn)而使用菲利普·卡茲的軟件.SEA其實不是什么大企業(yè),它只是個3人起家的小公司,當然無法接受這種毀滅性打擊.以現(xiàn)在的眼光看來,最初SEA的方式是溫和的,它接洽菲利普·卡茲并希望通過授權(quán)的方式將PKARC納入旗下,然而并不認為自己有什么過錯的菲利普·卡茲一口拒絕,他不想讓PKARC成為商業(yè)軟件,他制作這個工具的初衷并不是為了賺錢.最終菲利普·卡茲被SEA以侵犯ARC壓縮格式編碼算法的罪名告上了法庭,并輸?shù)袅斯偎?叛逆倔強的卡茲在敗訴后依然拒絕將PKARC授權(quán)給SEA公司,而選擇了支付法律費用和停止發(fā)放PKARC。
????? 這場官司對菲利普·卡茲的人生觀和信念影響巨大，追求自由平等的精神并不意味著盲目和法律對抗，試圖劫富濟貧的少年俠客行為只能逞一時快意，實質(zhì)上幫助不了任何人。在官司的進行中，菲利普·卡茲一直在持續(xù)開發(fā)PKARC的后續(xù)產(chǎn)品PKPRC，敗訴后菲利普·卡茲決定將PKPRC完全重寫。很顯然，這次再也不能去觸犯任何編碼算法的專利權(quán)了，從3個基本編碼算法來衍生自己的算法是必然的，于是去掉有專利權(quán)的LZW和LZ78，剩下的就只有LZ77。也許是被激怒后帶來了驚人的動力，只用了幾周的時間菲利普·卡茲就創(chuàng)造出一個全新的壓縮編碼算法，該算法完美地結(jié)合LZ77和Huffman編碼，也就是后來大名鼎鼎的DEFLATE算法了。新壓縮軟件被命名為PKZIP，而其文件格式擴展名叫作“.zip”。PKZIP可將多個文件壓縮到一個文件中，無論壓縮比、壓縮速度都全面超過了商業(yè)軟件ARC。菲利普·卡茲將PKZIP作為自由軟件免費發(fā)放，使其如野火般在全美各大BBS上蔓延開來，用戶以幾何級數(shù)增長，遭受毀滅性打擊的SEA公司半年內(nèi)就無聲無息。這段故事最后演變?yōu)橛米杂绍浖驍∩虡I(yè)軟件的傳奇，菲利普·卡茲更是成為充滿幻想的年輕程序員心中十步殺一人的偶像。

總結(jié)

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

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