數(shù)據(jù)庫是怎么進(jìn)行壓縮的？
回答問題之前先來看看什么是壓縮。當(dāng)你有天走在路上，碰見熟人對你說：“吃了?”你一定知道他是在打招呼，既不是要請客也不是讓你“沒吃趕緊回家吃去”。這一句簡單的“吃了”是禮貌和問好的體現(xiàn)，也是一種信息的壓縮?；\統(tǒng)地說，把一系列已有信息通過一定方法處理，使得其長度縮短，并且信息含量基本或者完全不變，就稱之為壓縮。
計算機(jī)上的壓縮過程
我們都知道，計算機(jī)采用的是2進(jìn)制系統(tǒng)。一個連續(xù)的n位二進(jìn)制數(shù)集，就可以用來表示 2 n 個字符。目前的國際標(biāo)準(zhǔn)是ASCII碼：用一個字節(jié)即8位數(shù)的2進(jìn)制碼，來表示各種字符和字母。
現(xiàn)在我們只使用2位二進(jìn)制碼，來簡單地演示由4個符號組成的字符串的壓縮過程。
假設(shè)我們有這么一串20個字母的數(shù)據(jù)：
默認(rèn)情況下，用2位2進(jìn)制碼來表示這四個字母：
每個字符在字符串種各自出現(xiàn)的次數(shù)并不相等：
A:6次 B:10次 C:3次 D:1次
而在計算機(jī)中，數(shù)據(jù)則是以2進(jìn)制碼的形式儲存在硬盤上的：
00 00 01 00 00 01 01 10 01 00 01 01 01 10 01 01 00 01 11 10
壓縮過程如下：
①注明每個字符的出現(xiàn)次數(shù)。把兩個出現(xiàn)次數(shù)最小的字符圈到一起，看作一個新字符，新字符的次數(shù)為兩個組成字符的次數(shù)之和。
②重復(fù)上述操作，直至完成對所有字符的處理。這種操作形成的結(jié)構(gòu)看起來像棵樹(下圖)，被稱為——霍夫曼(Huffman)樹。
③在每一層的分支線上，按下圖所示分別標(biāo)上0和1。
從最頂端往下讀，每個字符都有唯一的分支編號連到它那里，無重復(fù)也無遺漏，這樣就得到了ABCD這四個字符的新的代碼：
用以上新編碼代入原字符串中，得到：
10 10 0 10 10 0 0 110 0 10 0 0 0 110 0 0 10 0 111 110
整理一下得到新編碼：
原編碼：0000010000010110010001010110010100011110
新編碼：1010010100011001000011000100111110
看!數(shù)據(jù)成功被壓縮。這一段40位長度的內(nèi)容被壓縮到了34位，壓縮率是85%。
回顧過程容易發(fā)現(xiàn)壓縮的秘密：出現(xiàn)頻率最多的"B"由一位二進(jìn)制碼“0”來表示，而出現(xiàn)頻率較低的"C"和"D"，則由長度增加了的三位二進(jìn)制碼來表示。通過合理分配不同長度的編碼，肯定可以對數(shù)據(jù)進(jìn)行一定程度的壓縮。
另外可以證明，霍夫曼樹就是此類編碼替代的最優(yōu)化的方案之一。因為假如存在一個字符的出現(xiàn)頻率高于另一個字符，而它的變長碼長度卻長于另一個字符，那么必然可以通過交換兩者的位置，使得輸出結(jié)果的總長度變短。有限次操作后可以達(dá)到無法再交換的情況，也就是霍夫曼樹規(guī)則下的情況。
進(jìn)一步思考幾個問題
在壓縮文件的時候，人們不禁會產(chǎn)生一些新想法或者遇到一些疑問：是否可以對壓縮后的數(shù)據(jù)再次壓縮?當(dāng)2 n 的n變大后，遇到A：1010，B：10這樣的情況，如何解讀10101010?
就操作上來說，當(dāng)然能反復(fù)編碼，但通過對本文例子中得到的新編碼再次操作后會發(fā)現(xiàn)，結(jié)果是不會有任何變化的。壓縮的實質(zhì)，在于消除特定字符分布上的不均衡，通過將短碼分配給高頻字符，而長碼對應(yīng)低頻字符實現(xiàn)長度上的優(yōu)化。而數(shù)據(jù)經(jīng)過一次壓縮后，字符的分布已經(jīng)幾乎平均化了，很難更進(jìn)一步的壓縮了。
而第二個問題描述的情況是不會出現(xiàn)的的。從構(gòu)造霍夫曼樹操作上可以看到，一個字符無法在另一個字符的上層。只要操作正確，就一定可以構(gòu)造出唯一的代碼表，不存在歧義。
還有一個有趣的問題是：雖然把40字節(jié)的內(nèi)容壓縮到了34字節(jié)，但需要將相應(yīng)的碼表一并發(fā)送給接收方(沒有對應(yīng)碼表，無法解壓)。這不反而使得壓縮后的數(shù)據(jù)比壓縮前的還要長?
事實也確實如此。本文例子中，真正的最終結(jié)果體積是大于原文的。但這不意味了算法錯誤。這是因為“n”過小(例子中為2，實際通常為8)導(dǎo)致的。
總長度的不夠使得節(jié)省出來的那部分容量還不足以彌補(bǔ)碼表本身的儲存空間。實際應(yīng)用中，如果你非要去壓縮一個只有幾個字節(jié)的文件，得到的壓縮包也經(jīng)常會大于文件本身。通常，壓縮軟件會在每壓縮4kb到32kb數(shù)據(jù)后，重新生成并保存一個霍夫曼樹。當(dāng)分塊過大時，統(tǒng)計上的整體平均，會掩蓋小區(qū)域內(nèi)的極度不平均，損失了壓縮的空間。比如存在一個這樣的文件：
AAAAA……AAAAA(一萬個)BBBBB……BBBBB(一萬個)……ZZZZ(一萬個)。
如果從整體上進(jìn)行霍夫曼樹操作，將不會產(chǎn)生任何壓縮，但是這時候我們把它分成26塊，壓縮并各自保存相應(yīng)的重新編碼的霍夫曼樹，壓縮率將非常驚人，約等于12.5%。
英語中各字母出現(xiàn)頻率示意圖
從上面字頻圖我們知道，在現(xiàn)實的文本中，英語字母使用頻率各不相同，而且差別很大。有著很高的不平均度。所以大部分壓縮軟件對文本文件依然有著很高的壓縮率。
【編輯推薦】
