多媒體發(fā)展簡史第一頁，共七十六頁，2022年，8月28日2023/1/291第0章多媒體發(fā)展簡史1.數(shù)據(jù)壓縮技術(shù)半個世紀發(fā)展小述2.互聯(lián)網(wǎng)的誕生

3.多媒體發(fā)展簡史第一章

作業(yè)題第二頁，共七十六頁，2022年，8月28日2023/1/292什么是數(shù)據(jù)壓縮第三頁，共七十六頁，2022年，8月28日2023/1/293

電腦里的數(shù)據(jù)壓縮其實類似于美眉們的瘦身運動，不外有兩大功用。

第一，可以節(jié)省空間。拿瘦身美眉來說，要是八個美眉可以擠進一輛出租車里，那該有多省錢啊！

第二，可以減少對帶寬的占用。例如，我們都想在手機上觀看DVD大片，前者則取決于美眉們的恒心和毅力，后者有待于數(shù)據(jù)壓縮技術(shù)的突破性進展。第四頁，共七十六頁，2022年，8月28日2023/1/294

簡單地說，如果沒有數(shù)據(jù)壓縮技術(shù)，我們就沒法用WinRAR為Email中的附件瘦身；如果沒有數(shù)據(jù)壓縮技術(shù)，市場上的數(shù)碼錄音筆就只能記錄不到20分鐘的語音；如果沒有數(shù)據(jù)壓縮技術(shù)，從Internet上下載一部電影也許要花半年的時間……可是這一切究竟是如何實現(xiàn)的呢？數(shù)據(jù)壓縮技術(shù)又是怎樣從無到有發(fā)展起來的呢？

第五頁，共七十六頁，2022年，8月28日2023/1/295數(shù)據(jù)壓縮簡史音畫時尚

回到未來

概率奇緣

數(shù)學(xué)游戲異族傳說第六頁，共七十六頁，2022年，8月28日2023/1/296概率奇緣

一千多年前的中國學(xué)者就知道用“班馬”這樣的縮略語來指代班固和司馬遷，這種崇尚簡約的風(fēng)俗一直延續(xù)到了今天的Internet時代：當(dāng)我們在BBS上用“

7456”代表“氣死我了”，或是用“

B4”代表“

Before”的時候，我們至少應(yīng)該知道，這其實就是一種最簡單的數(shù)據(jù)壓縮呀。第七頁，共七十六頁，2022年，8月28日2023/1/297概率奇緣

嚴格意義上的數(shù)據(jù)壓縮起源于人們對概率的認識。當(dāng)我們對文字信息進行編碼時，如果為出現(xiàn)概率較高的字母賦予較短的編碼，為出現(xiàn)概率較低的字母賦予較長的編碼，總的編碼長度就能縮短不少。第八頁，共七十六頁，2022年，8月28日2023/1/298概率奇緣

著名的Morse電碼(由美國的摩爾斯在1844年發(fā)明的，所以電碼符號也被叫做摩爾斯電碼—Morsecode），電碼符號由兩種基本信號和不同的間隔時間組成：短促的點信號“．”，讀“的”（Di）；保持一定時間的長信號“—”，讀“答—”（Da）。第九頁，共七十六頁，2022年，8月28日2023/1/299概率奇緣

A:.-

B:-...

C:-.-.

D:-..

E:.

F:..-.

G:--.

H:....

I:..

J:.---

L:.-..

M:--

N:-.

P:.--.

Q:--.-

R:.-.

S:...

T:-

U:..-

V:...-W:.--

X:-..-

Y:-.--

Z:--..

0:-----

1:.----

2:..---

3:...--

4:....-

5:.....6:-....

7:--...

8:---..

9:----.

Morse電碼

Morse電碼

Morse電碼

Morse電碼第十頁，共七十六頁，2022年，8月28日2023/1/2910信息論之父C.E.Shannon第一次用數(shù)學(xué)語言闡明了概率與信息冗余度的關(guān)系。在1948年發(fā)表的論文中，Shannon指出，任何信息都存在冗余，冗余大小與信息中每個符號（數(shù)字、字母或單詞）的出現(xiàn)概率或者說不確定性有關(guān)。Shannon借鑒了熱力學(xué)的概念，把信息中排除了冗余后的平均信息量稱為“信息熵”，并給出了計算信息熵的數(shù)學(xué)表達式。第十一頁，共七十六頁，2022年，8月28日2023/1/2911這篇偉大的論文后來被譽為信息論的開山之作，信息熵也奠定了所有數(shù)據(jù)壓縮算法的理論基礎(chǔ)。從本質(zhì)上講，數(shù)據(jù)壓縮的目的就是找出并消除信息中的冗余，而信息熵及相關(guān)的定理恰恰用數(shù)學(xué)手段精確地描述了信息冗余的程度。利用信息熵公式，人們可以計算出信息編碼的極限，即在一定的概率模型下，無損壓縮的編碼長度不可能小于信息熵公式給出的結(jié)果。第十二頁，共七十六頁，2022年，8月28日2023/1/2912En=-log2(Pn)I=D-du第十三頁，共七十六頁，2022年，8月28日2023/1/2913有了完備的理論，接下來的事就是要想辦法實現(xiàn)具體的算法，并盡量使算法的輸出接近信息熵的極限了。當(dāng)然，大多數(shù)工程技術(shù)人員都知道，要將一種理論從數(shù)學(xué)公式發(fā)展成實用技術(shù)，就像僅憑一個E=mc2的公式就要去制造原子彈一樣，并不是一件很容易的事。第十四頁，共七十六頁，2022年，8月28日2023/1/2914數(shù)學(xué)游戲

設(shè)計具體的壓縮算法的過程通常更像是一場數(shù)學(xué)游戲。開發(fā)者首先要尋找一種能盡量精確地統(tǒng)計或估計信息中符號出現(xiàn)概率的方法，然后還要設(shè)計一套用最短的代碼描述每個符號的編碼規(guī)則。1948年，Shannon在提出信息熵理論的同時，也給出了一種簡單的編碼方法——Shannon編碼。1952年，R.M.Fano又進一步提出了Fano編碼。這些早期的編碼方法揭示了變長編碼的基本規(guī)律，也確實可以取得一定的壓縮效果，但離真正實用的壓縮算法還相去甚遠。第十五頁，共七十六頁，2022年，8月28日2023/1/2915第一個實用的編碼方法是由D.A.Huffman提出的。Huffman編碼效率高，運算速度快，實現(xiàn)方式靈活。今天，在許多知名的壓縮工具和壓縮算法（如WinRAR、gzip和JPEG）里，都有Huffman編碼的身影。如果不是后文將要提到的那兩個猶太人，我們還不知要到什么時候才能用上WinZIP這樣方便實用的壓縮工具呢。第十六頁，共七十六頁，2022年，8月28日2023/1/2916異族傳說逆向思維永遠是科學(xué)和技術(shù)領(lǐng)域里出奇制勝的法寶。就在大多數(shù)人絞盡腦汁想改進Huffman或算術(shù)編碼，以獲得一種兼顧了運行速度和壓縮效果的“完美”編碼的時候，兩個聰明的猶太人J.Ziv和A.Lempel獨辟蹊徑，完全脫離Huffman及算術(shù)編碼的設(shè)計思路，創(chuàng)造出了一系列比Huffman編碼更有效，比算術(shù)編碼更快捷的壓縮算法。我們通常用這兩個猶太人姓氏的縮寫，將這些算法統(tǒng)稱為LZ系列算法。第十七頁，共七十六頁，2022年，8月28日2023/1/2917異族傳說說實話，LZ系列算法的思路并不新鮮，其中既沒有高深的理論背景，也沒有復(fù)雜的數(shù)學(xué)公式，它們只是簡單地延續(xù)了千百年來人們對字典的追崇和喜好，并用一種極為巧妙的方式將字典技術(shù)應(yīng)用于通用數(shù)據(jù)壓縮領(lǐng)域。通俗地說，當(dāng)你用字典中的頁碼和行號代替文章中每個單詞的時候，你實際上已經(jīng)掌握了LZ系列算法的真諦。這種基于字典模型的思路在表面上雖然和Shannon、Huffman等人開創(chuàng)的統(tǒng)計學(xué)方法大相徑庭，但在效果上一樣可以逼近信息熵的極限。而且，可以從理論上證明，LZ系列算法在本質(zhì)上仍然符合信息熵的基本規(guī)律。第十八頁，共七十六頁，2022年，8月28日2023/1/2918異族傳說今天，LZ77、LZ78、LZW算法以及它們的各種變體幾乎壟斷了整個通用數(shù)據(jù)壓縮領(lǐng)域，我們熟悉的PKZIP、WinZIP、WinRAR、gzip等壓縮工具以及ZIP、GIF、PNG等文件格式都是LZ系列算法的受益者。沒有誰能否認兩位猶太人對數(shù)據(jù)壓縮技術(shù)的貢獻。我想強調(diào)的只是，在工程技術(shù)領(lǐng)域，片面追求理論上的完美往往只會事倍功半，如果大家能像Ziv和Lempel那樣，經(jīng)常換個角度來思考問題，沒準(zhǔn)兒你就能發(fā)明一種新的算法，就能在技術(shù)方展史上揚名立萬呢。第十九頁，共七十六頁，2022年，8月28日2023/1/2919音畫時尚LZ系列算法基本解決了通用數(shù)據(jù)壓縮中兼顧速度與壓縮效果的難題。但是，數(shù)據(jù)壓縮領(lǐng)域里還有另一片更為廣闊的天地等待著我們?nèi)ヌ剿?。第二十頁，共七十六頁?022年，8月28日2023/1/2920音畫時尚例如，對于生活中更加常見的，圖片、圖像等，通用壓縮算法的優(yōu)勢就不那么明顯了。幸運的是，科學(xué)家們發(fā)現(xiàn)，如果在壓縮這一類圖像數(shù)據(jù)時允許改變一些不太重要的像素值，或者說允許損失一些精度（在壓縮通用數(shù)據(jù)時，我們絕不會容忍任何精度上的損失，但在壓縮和顯示一幅數(shù)碼照片時，如果一片樹林里某些樹葉的顏色稍微變深了一些，看照片的人通常是察覺不到的），我們就有可能在壓縮效果上獲得突破性的進展。也許，這和生活中常說的“退一步海闊天空”的道理有異曲同工之妙吧。第二十一頁，共七十六頁，2022年，8月28日2023/1/2921音畫時尚聲音編碼基本原理視頻壓縮基本原理第二十二頁，共七十六頁，2022年，8月28日2023/1/2922音畫時尚Internet的發(fā)展對視頻壓縮提出了更高的要求。在內(nèi)容交互、對象編輯、隨機存取等新需求的刺激下，ISO于1999年通過了MPEG-4標(biāo)準(zhǔn)。MPEG-4標(biāo)準(zhǔn)擁有更高的壓縮比率，支持基于內(nèi)容的交互操作等先進特性。第二十三頁，共七十六頁，2022年，8月28日2023/1/2923音畫時尚Internet上新興的DivX和XviD文件格式就是采用MPEG-4標(biāo)準(zhǔn)來壓縮視頻數(shù)據(jù)的，它們可以用更小的存儲空間或通信帶寬提供與DVD不相上下的高清晰視頻，這使我們在Internet上發(fā)布或下載數(shù)字電影的夢想成為了現(xiàn)實。第二十四頁，共七十六頁，2022年，8月28日2023/1/2924回到未來

從信息熵到算術(shù)編碼，從猶太人到WinRAR

，從JPEG到MP3，數(shù)據(jù)壓縮技術(shù)的發(fā)展史就像是一個寫滿了“創(chuàng)新”、“挑戰(zhàn)”、“突破”和“變革”的羊皮卷軸。也許，我們在這里不厭其煩地羅列年代、人物、標(biāo)準(zhǔn)和文獻，其目的只是要告訴大家，前人的成果只不過是后人有望超越的目標(biāo)而已，誰知道在未來的幾年里，還會出現(xiàn)幾個Shannon，幾個Huffman呢？談到未來，我們還可以補充一些與數(shù)據(jù)壓縮技術(shù)的發(fā)展趨勢有關(guān)的話題。第二十五頁，共七十六頁，2022年，8月28日2023/1/2925回到未來分形壓縮技術(shù)是圖像壓縮領(lǐng)域近幾年來的一個熱點。這一技術(shù)起源于B.Mandelbrot于1977年創(chuàng)建的分形幾何學(xué)。M.Barnsley在20世紀80年代后期為分形壓縮奠定了理論基礎(chǔ)。從20世紀90年代開始，A.Jacquin等人陸續(xù)提出了許多實驗性的分形壓縮算法。今天，很多人相信，分形壓縮是圖像壓縮領(lǐng)域里最有潛力的一種技術(shù)體系，但也有很多人對此不屑一顧。無論其前景如何，分形壓縮技術(shù)的研究與發(fā)展都提示我們，在經(jīng)過了幾十年的高速發(fā)展之后，也許，我們需要一種新的理論，或是幾種更有效的數(shù)學(xué)模型，以支撐和推動數(shù)據(jù)壓縮技術(shù)繼續(xù)向前躍進。

第二十六頁，共七十六頁，2022年，8月28日2023/1/2926回到未來人工智能是另一個可能對數(shù)據(jù)壓縮的未來產(chǎn)生重大影響的關(guān)鍵詞。既然Shannon認為，信息能否被壓縮以及能在多大程度上被壓縮與信息的不確定性有直接關(guān)系，假設(shè)人工智能技術(shù)在某一天成熟起來，假設(shè)計算機可以像人一樣根據(jù)已知的少量上下文猜測后續(xù)的信息，那么，將信息壓縮到原大小的萬分之一乃至十萬分之一，恐怕就不再是天方夜譚了。第二十七頁，共七十六頁，2022年，8月28日2023/1/2927回到未來回顧歷史之后，人們總喜歡暢想一下未來。但未來終究是未來，如果僅憑你我?guī)拙湓捑涂梢岳砬逦磥淼募夹g(shù)發(fā)展趨勢，那技術(shù)創(chuàng)新的工作豈不就索然無味了嗎？依我說，未來并不重要，重要的是，趕快到Internet上下載幾個MP3或DVD大片，好好享受一下數(shù)據(jù)壓縮為我們帶來的無限快樂吧。返回第二十八頁，共七十六頁，2022年，8月28日2023/1/2928多媒體電視計算機通信ISDN通信尼普柯夫圓盤黑白電視彩色電視數(shù)字電視HDTV、IPTV計算文字及圖像音視頻MPC互聯(lián)網(wǎng)手動交換機械自動交換程控交換ISDN分組交換多媒體發(fā)展簡史第二十九頁，共七十六頁，2022年，8月28日2023/1/2929

多媒體是通信、計算機和電視等各種技術(shù)聯(lián)合發(fā)展的必然結(jié)果。通信A電視B計算機CBACABC返回第三十頁，共七十六頁，2022年，8月28日2023/1/2930作業(yè)題

參照課上所講到的“數(shù)據(jù)壓縮”與“互聯(lián)網(wǎng)”的發(fā)展簡史，通過查找相關(guān)資料，寫一篇“多媒體通信技術(shù)”的小論文。返回第三十一頁，共七十六頁，2022年，8月28日2023/1/2931尼普柯夫(P.Nipkow)圓盤第三十二頁，共七十六頁，2022年，8月28日2023/1/2932電話是如何發(fā)明的

亞歷山大·格拉漢姆·貝爾（AlexanderGrahamBell，1847-1942）美國發(fā)明家和企業(yè)家。他發(fā)明了世界上第一臺可用的電話機，創(chuàng)建了貝爾電話公司。被譽為“電話之父”。第三十三頁，共七十六頁，2022年，8月28日2023/1/2933電話是如何發(fā)明的1847年生于英國蘇格蘭，他的祖父親畢生都從事聾啞人的教育事業(yè)，由于家庭的影響，他從小就對聲學(xué)和語言學(xué)有濃厚的興趣。開始，他的興趣是在研究電報上。有一次，當(dāng)他在做電報實驗時，偶然發(fā)現(xiàn)了一塊鐵片在磁鐵前振動會發(fā)出微弱聲音的現(xiàn)象，而且他還發(fā)現(xiàn)這種聲音能通過導(dǎo)線傳向遠方。這給貝爾以很大的啟發(fā)。他想，如果對著鐵片講話，不也可以引起鐵片的振動嗎?就是貝爾關(guān)于電話的最初構(gòu)想。梅布爾

第三十四頁，共七十六頁，2022年，8月28日2023/1/2934

是梅布爾鼓舞他進行了所有那些使人精疲力竭的實驗，也是梅布爾使他克服了不時產(chǎn)生的沮喪情緒——那種常常困擾著緊張工作去奪取成功的人們的沮喪情緒——使他得以研制出當(dāng)時很了不起的一種工具。它能把人說的話轉(zhuǎn)變?yōu)殡娒}沖，之后又在金屬絲的末端使之還原成人說的話。

電話是如何發(fā)明的第三十五頁，共七十六頁，2022年，8月28日2023/1/2935

為了紀念貝爾的功績，將電學(xué)和聲學(xué)中計量功率或功率密度比值的一種單位命名為“貝爾”。

由于貝爾1876年3月10日所使用的這部電話機的送話器，在原理上與另一位電話發(fā)明家菲利浦·格雷(德國科學(xué)家)的發(fā)明雷同，因而格雷便向法院提出起訴。一場爭奪電話發(fā)明權(quán)的訴訟案便由此展開，并一直持續(xù)了十多年。最后，法院根據(jù)貝爾的磁石電話與格雷的液體電話有所不同，而且比格雷早幾個小時提交了專利申請等這些因素，作出了現(xiàn)在大家已經(jīng)知道結(jié)果的判決，電話發(fā)明權(quán)案至此畫上句號。

電話是如何發(fā)明的第三十六頁，共七十六頁，2022年，8月28日2023/1/2936聲音編碼示意圖

編碼、傳輸、人耳聽音的實現(xiàn)

第三十七頁，共七十六頁，2022年，8月28日2023/1/2937

聲音編碼的范圍第三十八頁，共七十六頁，2022年，8月28日2023/1/2938聲音編碼示意圖1、只對可聞信號進行編碼

第三十九頁，共七十六頁，2022年，8月28日2023/1/2939聲音編碼示意圖2、只對幅度強的掩蔽信號進行編碼

第四十頁，共七十六頁，2022年，8月28日2023/1/2940聲音編碼示意圖3、只對信號與量化噪聲的差值進行編碼

第四十一頁，共七十六頁，2022年，8月28日2023/1/2941聲音編碼示意圖4、通過子帶分割來進行優(yōu)化、編碼

第四十二頁，共七十六頁，2022年，8月28日2023/1/2942聲音編碼示意圖音頻編碼示意圖

輸入信號第四十三頁，共七十六頁，2022年，8月28日2023/1/2943

視頻壓縮基本原理時域冗余信息

使用幀間編碼技術(shù)可去除時域冗余信息，它包括以下二部分：

—幀間預(yù)測只傳兩幀之間變化的部分；

—運動補償

運動補償是通過先前的局部圖像來預(yù)測、補償當(dāng)前的局部圖像，它是減少幀序列冗余信息的有效方法。

第四十四頁，共七十六頁，2022年，8月28日2023/1/2944視頻壓縮基本原理空域冗余信息

－變換編碼

變換編碼將空域信號變換到另一正交矢量空間，使其相關(guān)性下降，數(shù)據(jù)冗余度減小。

－量化編碼

經(jīng)過變換編碼后，產(chǎn)生一批變換系數(shù)，對這些系數(shù)進行量化，使編碼器的輸出達到一定的位率。－熵編碼

熵編碼是無損編碼。它對變換、量化后得到的系數(shù)和運動信息，進行進一步的壓縮。第四十五頁，共七十六頁，2022年，8月28日2023/1/2945第四十六頁，共七十六頁，2022年，8月28日2023/1/2946背景全景圖+視頻對象(VO)=合成圖像MPEG-4應(yīng)用實例第四十七頁，共七十六頁，2022年，8月28日2023/1/2947第四十八頁，共七十六頁，2022年，8月28日2023/1/2948叛逆斗士的勝利--ZIP格式誕生

在DOS年代由于計算機存儲介質(zhì)容量的微小，個人用戶對數(shù)據(jù)壓縮軟件的渴望是現(xiàn)在的用戶無法想象的。例如在1984年，個人計算機的標(biāo)配不過是容量360kB的5.25寸軟盤而已，如果個人能將數(shù)據(jù)壓縮數(shù)倍后存儲，不啻于節(jié)省了一大筆錢。

第四十九頁，共七十六頁，2022年，8月28日2023/1/2949叛逆斗士的勝利--ZIP格式誕生

于是數(shù)據(jù)壓縮軟件就成為了一項必須的工具。1985年SEA公司開發(fā)了MS-DOS環(huán)境下第一個應(yīng)用LZW算法的ARC壓縮軟件，它是當(dāng)時MS-DOS下統(tǒng)治性的壓縮軟件。從技術(shù)角度來說ARC確實不錯，但使用了專利LZW算法的ARC當(dāng)然是標(biāo)準(zhǔn)的商業(yè)軟件，使用這種軟件工作就必須付費。不過當(dāng)時許多玩家根本買不起ARC軟件，順便說一句題外話，那時大多PC玩家基本都沒什么富裕的錢，事實上個人計算機本身的發(fā)展就是被窮玩家精打細算所推動。不過個人計算機從誕生之日起就充滿了叛逆、自由的精神，這也是推動整個個人計算機世界前行的主要動力。此時一個年輕的程序員出現(xiàn)并試圖改變壓縮世界，這個人叫PhillipW.Katz（菲利普·卡茲）。第五十頁，共七十六頁，2022年，8月28日2023/1/2950

20世紀七八十年代出售軟件的方式和現(xiàn)在截然不同，以ARC軟件來說，它不僅包括了一份EXE可執(zhí)行文件，還包括它的C語言源代碼。經(jīng)?；燠E于BBS上的菲利普·卡茲同樣買不起ARC，于是他自己將ARC的C語言源代碼進行復(fù)制并用匯編語言重寫，并將這個壓縮工具稱作PKARC，這個程序自然與ARC完全兼容，而且由于使用匯編使得速度較ARC更快。在當(dāng)時的計算機世界里這是一種很普遍的現(xiàn)象，并沒有程序員認為這種行為不對，甚至只要不與自己沖突，被改寫者通常也不在乎。不過這次不太一樣，菲利普·卡茲不僅僅是自己和朋友用，而是將這個軟件免費向他人開放，大批ARC用戶自然也就轉(zhuǎn)而使用菲利普·卡茲的軟件。第五十一頁，共七十六頁，2022年，8月28日2023/1/2951SEA其實不是什么大企業(yè)，它只是個3人起家的小公司，當(dāng)然無法接受這種毀滅性打擊。以現(xiàn)在的眼光看來，最初SEA的方式是溫和的，它接洽菲利普·卡茲并希望通過授權(quán)的方式將PKARC納入旗下，然而并不認為自己有什么過錯的菲利普·卡茲一口拒絕，他不想讓PKARC成為商業(yè)軟件，他制作這個工具的初衷并不是為了賺錢。最終菲利普·卡茲被SEA以侵犯ARC壓縮格式編碼算法的罪名告上了法庭，并輸?shù)袅斯偎尽Ｅ涯婢髲姷目ㄆ澰跀≡V后依然拒絕將PKARC授權(quán)給SEA公司，而選擇了支付法律費用和停止發(fā)放PKARC。

第五十二頁，共七十六頁，2022年，8月28日2023/1/2952

這場官司對菲利普·卡茲的人生觀和信念影響巨大，追求自由平等的精神并不意味著盲目和法律對抗，試圖劫富濟貧的少年俠客行為只能逞一時快意，實質(zhì)上幫助不了任何人。敗訴后菲利普·卡茲決定將PKPRC完全重寫。很顯然，這次再也不能去觸犯任何編碼算法的專利權(quán)了，從3個基本編碼算法來衍生自己的算法是必然的，于是去掉有專利權(quán)的LZW和LZ78，剩下的就只有LZ77。第五十三頁，共七十六頁，2022年，8月28日2023/1/2953

也許是被激怒后帶來了驚人的動力，只用了幾周的時間菲利普·卡茲就創(chuàng)造出一個全新的壓縮編碼算法，該算法完美地結(jié)合LZ77和Huffman編碼，也就是后來大名鼎鼎的PKZIP，而其文件格式擴展名叫作“.zip”。PKZIP可將多個文件壓縮到一個文件中，無論壓縮比、壓縮速度都全面超過了商業(yè)軟件ARC。菲利普·卡茲將PKZIP作為自由軟件免費發(fā)放，使其如野火般在全美各大BBS上蔓延開來，用戶以幾何級數(shù)增長，遭受毀滅性打擊的SEA公司半年內(nèi)就無聲無息。這段故事最后演變?yōu)橛米杂绍浖驍∩虡I(yè)軟件的傳奇，菲利普·卡茲更是成為充滿幻想的年輕程序員心中十步殺一人的偶像。第五十四頁，共七十六頁，2022年，8月28日2023/1/2954

然而事情如果僅僅到此為止，那么這也不過是菲利普·卡茲為私人恩怨而快意恩仇的行為，未必能得到后人的真正尊重。不過他做出了一個讓所有計算機用戶都收益無窮的舉動，那就是宣布開放ZIP格式，任何人都可以自由使用ZIP編碼算法而不需要繳納任何專利費用。這個決定最終改變了壓縮的世界，使得通用數(shù)據(jù)無損壓縮領(lǐng)域再無法出現(xiàn)壟斷的商業(yè)巨鱷，真正意義上幫助了每個需要壓縮的計算機用戶。憑借這個無私的行為，菲利普·卡茲真正成為他想成為的英雄。

第五十五頁，共七十六頁，2022年，8月28日2023/1/2955

2000年4月14日，年僅37歲的菲利普·卡茲被人發(fā)現(xiàn)倒斃在美國威斯康星州密爾沃基的一家汽車旅館里，據(jù)說死因是慢性酒精中毒引起的并發(fā)癥。這位天才程序員從未在ZIP身上得到半點好處，堅持信念的結(jié)果是潦倒的生活。他為世界貢獻了一個偉大的免費軟件，更為重要的是他締造了一種大眾化的壓縮格式，然而卻過早的離開了這個世界。

第五十六頁，共七十六頁，2022年，8月28日2023/1/2956考慮用0和1組成的二進制數(shù)碼為含有n個符號的某條信息編碼，假設(shè)符號Fn

在整條信息中重復(fù)出現(xiàn)的概率為Pn，則該符號的熵也即表示該符號所需的位數(shù)為：En=-log2(Pn)熵的計算公式第五十七頁，共七十六頁，2022年，8月28日2023/1/2957算術(shù)編碼是由J.Rissanen在1979年提出的。算術(shù)編碼的基本原理．將被編碼的信息表示成實數(shù)軸上０和１之間的間隔，信息越長，間隔越小，表示這一間隔所需的二進制位數(shù)就越多。算術(shù)編碼第五十八頁，共七十六頁，2022年，8月28日2023/1/2958huffman編碼原理及計算過程

變長編碼——頻繁使用的數(shù)據(jù)用較短的代碼代替，較少使用的數(shù)據(jù)用較長的代碼代替，每個數(shù)據(jù)的代碼各不相同。第五十九頁，共七十六頁，2022年，8月28日2023/1/2959huffman編碼原理及計算過程

舉個例子：假設(shè)一個文件中出現(xiàn)了8種符號S0,S1,S2,S3,S4,S5,S6,S7，那么每種符號要編碼，至少需要3比特。假設(shè)編碼成000,001,010,011,100,101,110,111(稱做碼字)。第六十頁，共七十六頁，2022年，8月28日2023/1/2960huffman編碼原理及計算過程

那么符號序列S0S1S7S0S1S6S2S2S3S4S5S0S0S1

編碼后變成

。第六十一頁，共七十六頁，2022年，8月28日2023/1/2961huffman編碼原理及計算過程

共用了42比特。我們發(fā)現(xiàn)S0，S1，S2這三個符號出現(xiàn)的頻率比較大，其它符號出現(xiàn)的頻率比較小，如果我們采用一種編碼方案使得S0，S1，S2的碼字短，其它符號的碼字長，這樣就能夠減少占用的比特數(shù)。第六十二頁，共七十六頁，2022年，8月28日2023/1/2962huffman編碼原理及計算過程

例如，我們采用這樣的編碼方案：S0到S7的碼字分別00,01,100,101,1100，1101,1110,1111，那么上述符號序列變成，共用了39比特，盡管有些碼字如S4，S5，S6，S7變長了(由3位變成4位)，但使用頻繁的幾個碼字如S0，S1變短了，所以實現(xiàn)