文件以字節(jié)位單位保存

文件是將數(shù)據(jù)存儲(chǔ)在磁盤等存儲(chǔ)媒介中的一種形式。程序文件中存儲(chǔ)數(shù)據(jù)的單位是 「字節(jié)」 。文件的大小之所以用xxKB、xxMB等來表示，就是因?yàn)槲募且宰止?jié)（B = Byte）為單位來存儲(chǔ)的。

?文件就是**「字節(jié)數(shù)據(jù)的集合」**

?

用1字節(jié)（=8位）表示的字節(jié)數(shù)據(jù)有256種，用二進(jìn)制數(shù)來表示的話，其范圍就是00000000~11111111。

• 如果文件中存儲(chǔ)的數(shù)據(jù)是文字，那么該文件就是**「文本文件」**
• 如果是圖形，那么該文件就是 「圖像文件」 。

?在任何情況下，文件中的字節(jié)數(shù)據(jù)都是 「連續(xù)存儲(chǔ)」 的。

?

RLE算法

我們來嘗試對(duì)存儲(chǔ)著AAAAAABBCDDEEEEEF這17個(gè) 「半角字符」 的文本文件進(jìn)行壓縮。

由于半角字母中， 「1個(gè)字符是作為1個(gè)字節(jié)」 的數(shù)據(jù)被保存在文件中的。因此，上述文件的大小就是17個(gè)字節(jié)。

我們可以采用將文件的內(nèi)容用 「字符 × 重復(fù)次數(shù)」 這樣的表現(xiàn)方式來壓縮。所以，AAAAAABBCDDEEEEEF就可以用A6B2C1D2E5F1來表示。而A6B2C1D2E5F1是12個(gè)字符，那么對(duì)應(yīng)的文本文件就變成了12字節(jié)。

12字節(jié)÷17字節(jié) ≈70%。也就是采用上述的方式，使得文件壓縮到原來大小的70%。

把文件內(nèi)容用 「數(shù)據(jù) × 重復(fù)次數(shù)」 的形式來表示的壓縮方法稱為RLE(Run Length Encoding,行程長(zhǎng)度編碼)算法

RLE算法的缺點(diǎn)

然而在實(shí)際的文本文件中，同樣字符多次重復(fù)出現(xiàn)的情況并不多見。雖然針對(duì) 「相同數(shù)據(jù)經(jīng)常連續(xù)出現(xiàn)」 的圖像、文件等，RLE算法可以發(fā)揮不錯(cuò)，但是它并不適合文本文件的壓縮。

哈夫曼算法

「哈夫曼算法」 是哈夫曼與1952年提出來的壓縮算法。

針對(duì)，哈夫曼算法，首先要拋棄 「半角英文數(shù)字的1個(gè)字符是1個(gè)字節(jié)（8位）的數(shù)據(jù)」 這一概念。

文本文件是由不同類型的字符組合而成的，而且不同的字符出現(xiàn)的次數(shù)也是不同的。例如，在某一個(gè)文本文件中，A出現(xiàn)了100次，Q出現(xiàn)了3次。

? 「哈夫曼算法」 的關(guān)鍵就在于 「多次出現(xiàn)的數(shù)據(jù)用小于8位的字節(jié)數(shù)來表示，不常用的數(shù)據(jù)則用超過8位的字節(jié)數(shù)來表示」 。

?

當(dāng)A和Q都用8位來表示時(shí)，原文件的大小就是100次 × 8位 + 3次 × 8位 = 824位，而假設(shè)A用2位，Q用10位表示，壓縮后的大小就是100次 × 2位 + 3次 × 10位 = 230位。

不過，有一點(diǎn)需要注意，

?不管是不滿8位的數(shù)據(jù)，還是超過8位的數(shù)據(jù)，最終都要 「以8位為單位保存到文件中」 。

?

這是因?yàn)榇疟P是以字節(jié)（8位）為單位來保存數(shù)據(jù)的。

用二叉樹實(shí)現(xiàn)哈夫曼編碼

哈夫曼算法是指，為 「各壓縮對(duì)象文件」 分別構(gòu)造最佳的編碼體系，并以該編碼體系為基礎(chǔ)來進(jìn)行壓縮。因此，用什么樣的編碼(哈夫曼編碼)對(duì)數(shù)據(jù)進(jìn)行分割，就要由各個(gè)文件而定。

用哈夫曼算法壓縮過的文件中，存儲(chǔ)著哈夫曼編碼信息和壓縮過的數(shù)據(jù)。

在哈夫曼算法中，通過借助 「哈夫曼樹」 構(gòu)造編碼體系，即使在不使用字符區(qū)分符號(hào)的情況下，也可以構(gòu)建能夠明確進(jìn)行區(qū)分的編碼體系。也就是說，利用哈夫曼樹后，就算表示各字符的數(shù)據(jù) 「位數(shù)」 不同，也能夠做成明確區(qū)分的編碼。

制作哈夫曼樹

自然界的樹是從根開始生枝長(zhǎng)葉，而哈夫曼樹是 「從葉生枝，然后再生根」 。

哈夫曼算法能夠大幅度提升壓縮比率

使用哈夫曼樹后，出現(xiàn) 「頻率越高的數(shù)據(jù)所占用的數(shù)據(jù)位數(shù)就越少」 ，而且數(shù)據(jù)的區(qū)分也可以很清晰的實(shí)現(xiàn)。

可逆壓縮和非可逆壓縮

• 「可逆壓縮」 ：能還原到壓縮前狀態(tài)的壓縮
• 「非可逆壓縮」 ：無法還原到壓縮前狀態(tài)的壓縮