文件存儲在聊壓縮算法前，有必要先普及一下文件存儲的知識點。 文件是將數(shù)據(jù)存儲在磁盤等存儲媒介的一種形式。程序文件中最基本的存儲數(shù)據(jù)單位是字節(jié)。文件是以字節(jié) B = Byte 為單位來存儲的。文件就是字節(jié)數(shù)據(jù)的集合。用 1 字節(jié)（8 位）表示的字節(jié)數(shù)據(jù)有 256 種，用二進制表示的話就是 0000 0000 - 1111 1111 。如果文件中存儲的數(shù)據(jù)是文字，那么該文件就是文本文件。如果是圖形，那么該文件就是圖像文件。在任何情況下，文件中的字節(jié)數(shù)都是連續(xù)存儲的。 ? 壓縮算法的定義當文件太大時，一般會使用文件壓縮來降低文件的占用空間。比如把相機拍完的照片保存到計算機上的時候，會使用壓縮算法進行文件壓縮，文件壓縮的格式一般是 JPEG。 壓縮算法（compaction algorithm）指數(shù)據(jù)壓縮的算法，主要包括壓縮和還原（解壓縮）的兩個步驟。是在不改變原有文件屬性的前提下，降低文件字節(jié)空間和占用空間的一種算法。 根據(jù)壓縮算法的定義，分成不同的類型：
? 幾種常用壓縮算法的理解RLE 算法的機制 把文件內(nèi)容用 數(shù)據(jù) * 重復次數(shù) 的形式來表示的壓縮方法稱為 RLE(Run Length Encoding, 行程長度編碼)? 算法。RLE 算法是一種很好的壓縮方法，經(jīng)常用于壓縮傳真的圖像等。因為圖像文件的本質(zhì)也是字節(jié)數(shù)據(jù)的集合體，所以可以用 RLE 算法進行壓縮 下面用一個例子描述一下 RLE 算法： 1.首先對 AAAAAABBCDDEEEEEF 這 17 個半角字符的文件（文本文件）進行壓縮，由于半角字符（其實就是英文字符）是作為 1 個字節(jié)保存在文件中的，所以上述的文件的大小就是 17 字節(jié)。 2.只要是能夠使文件小于 17 字節(jié)，我們可以使用任何壓縮算法。 3.最顯而易見的一種壓縮方式就是把相同的字符去重化，也就是 字符 * 重復次數(shù) 的方式進行壓縮。所以上面文件壓縮后就會變成下面這樣
4.從圖中可以看出，AAAAAABBCDDEEEEEF?的17個字符成功被壓縮成了?A6B2C1D2E5F1?的12個字符，也就是 12 / 17 ?= 70%，壓縮比為 70%，壓縮成功了。 ? 哈夫曼算法和莫爾斯編碼 在了解哈夫曼算法之前，需要先舍棄半角英文數(shù)字的1個字符是1個字節(jié)(8位)的數(shù)據(jù)的認知。 哈夫曼算法的基本思想：文本文件是由不同類型的字符組合而成的，而且不同字符出現(xiàn)的次數(shù)也是不一樣的。例如，在某個文本文件中，A 出現(xiàn)了 100次左右，Q僅僅用到了 3 次，類似這樣的情況很常見。哈夫曼算法的關(guān)鍵就在于?多次出現(xiàn)的數(shù)據(jù)用小于 8 位的字節(jié)數(shù)表示，不常用的數(shù)據(jù)則可以使用超過 8 位的字節(jié)數(shù)表示。A 和 Q 都用 8 位來表示時，原文件的大小就是 100次 * 8 位 3次 * 8 位 = 824位，假設(shè) A 用 2 位，Q 用 10 位來表示就是 2 * 100 3 * 10 = 230 位。不過要注意一點，最終磁盤的存儲都是以8位為一個字節(jié)來保存文件的。 ? 接下來看一下莫爾斯編碼，下面是莫爾斯編碼的示例，可以把 1 看作是短點(嘀)，把 11 看作是長點(嗒)。
莫爾斯編碼一般把文本中出現(xiàn)最高頻率的字符用短編碼來表示。如表所示，假如表示短點的位是 1，表示長點的位是 11 的話，那么 E（嘀）這一數(shù)據(jù)的字符就可以用 1 來表示，C（滴答滴答）就可以用 9 位的 110101101來表示。在實際的莫爾斯編碼中，如果短點的長度是 1 ，長點的長度就是 3，短點和長點的間隔就是1。這里的長度指的就是聲音的長度。 比如上面的 AAAAAABBCDDEEEEEF 例子來用莫爾斯編碼重寫，在莫爾斯曼編碼中，各個字符之間需要加入表示時間間隔的符號。這里用 00 加以區(qū)分。所以，AAAAAABBCDDEEEEEF 這個文本就變?yōu)榱?A * 6 次 B * 2次 C * 1次 D * 2次 E * 5次 F * 1次 字符間隔 * 16 = 4 位 * 6次 8 位 * 2次 9 位 * 1 次 6位 * 2次 1位 * 5次 8 位 * 1次 2位 * 16次 = 106位 ?= 14字節(jié)。所以使用莫爾斯電碼的壓縮比為 14 / 17 = 82%。效率并不太突出。 莫爾斯編碼是根據(jù)日常文本中各字符的出現(xiàn)頻率來決定表示各字符的編碼數(shù)據(jù)長度的。不過，在該編碼體系中，對 AAAAAABBCDDEEEEEF 這種文本來說并不是效率最高的。 ? 用二叉樹實現(xiàn)哈夫曼算法 哈夫曼算法是指為各壓縮對象文件分別構(gòu)造最佳的編碼體系，并以該編碼體系為基礎(chǔ)來進行壓縮。因此，用什么樣的編碼（哈夫曼編碼）對數(shù)據(jù)進行分割，就要由各個文件而定。用哈夫曼算法壓縮過的文件中，存儲著哈夫曼編碼信息和壓縮過的數(shù)據(jù)。
接下來，對 AAAAAABBCDDEEEEEF 中的 A - F 這些字符，按照出現(xiàn)頻率高的字符用盡量少的位數(shù)編碼來表示這一原則進行整理。按照出現(xiàn)頻率從高到低的順序整理后，結(jié)果如下，同時也列出了編碼方案。 ?
在上表的編碼方案中，隨著出現(xiàn)頻率的降低，字符編碼信息的數(shù)據(jù)位數(shù)也在逐漸增加，從最開始的 1位、2位依次增加到3位。不過這個編碼體系是存在問題的，不知道100這個3位的編碼，它的意思是用 1、0、0這三個編碼來表示 E、A、A 呢？還是用10、0來表示 B、A 呢？還是用100來表示 C 呢。 而在哈夫曼算法中，通過借助哈夫曼樹的構(gòu)造編碼體系，即使在不使用字符區(qū)分符號的情況下，也可以構(gòu)建能夠明確進行區(qū)分的編碼體系。不過哈夫曼樹的算法要比較復雜，下面是一個哈夫曼樹的構(gòu)造過程。
自然界樹的從根開始生葉的，而哈夫曼樹則是葉生枝 使用哈夫曼樹之后，出現(xiàn)頻率越高的數(shù)據(jù)所占用的位數(shù)越少，這也是哈夫曼樹的核心思想。通過上圖的步驟二可以看出，枝條連接數(shù)據(jù)時，是從出現(xiàn)頻率較低的數(shù)據(jù)開始的。這就意味著出現(xiàn)頻率低的數(shù)據(jù)到達根部的枝條也越多。而枝條越多則意味著編碼的位數(shù)隨之增加。 用上圖得到的數(shù)據(jù)表示 AAAAAABBCDDEEEEEF 為 000000000000 100100 110 101101 0101010101 111，40位 = 5 字節(jié)。壓縮前的數(shù)據(jù)是 17 字節(jié)，壓縮后的數(shù)據(jù)竟然達到了驚人的5 字節(jié)，也就是壓縮比率 = 5 / 17 = 29% 如此高的壓縮率，簡直是太驚艷了。 無論哪種類型的數(shù)據(jù)，都可以用哈夫曼樹作為壓縮算法
可逆壓縮和非可逆壓縮 最后，來看一下圖像文件的數(shù)據(jù)形式。圖像文件的使用目的通常是把圖像數(shù)據(jù)輸出到顯示器、打印機等設(shè)備上。常用的圖像格式有 : BMP、JPEG、TIFF、GIF 格式等。
圖像文件可以使用前面介紹的 RLE 算法和哈夫曼算法，因為圖像文件在多數(shù)情況下并不要求數(shù)據(jù)需要還原到和壓縮之前一摸一樣的狀態(tài)，允許丟失一部分數(shù)據(jù)。能還原到壓縮前狀態(tài)的壓縮稱為可逆壓縮，無法還原到壓縮前狀態(tài)的壓縮稱為非可逆壓縮 。 一般來說，JPEG格式的文件是非可逆壓縮，因此還原后有部分圖像信息比較模糊。GIF 是可逆壓縮 ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?? 來源：https://www./content-1-635001.html |
|
|
